Hash Table Lookup

Find a key in a separate-chaining hash table by scanning the bucket chosen by the hash function.

Time O(1) avg Space O(1) Hash Table lookup

How it works

Find a key in a separate-chaining hash table by scanning the bucket chosen by the hash function.

Implementation

function hashLookupOp(state, target) {
  const bucketHead = state.bucketHead;
  const nodeKey = state.nodeKey;
  const nodeNext = state.nodeNext;
  const numBuckets = state.numBuckets;
  const bucket = target % numBuckets;
  probeSlot(bucket);
  let current = bucketHead[bucket];
  while (current !== -1) {
    visitNode(current);
    compareKeys(current, target);
    if (nodeKey[current] === target) {
      reportFound(current);
      return;
    }
    current = nodeNext[current];
  }
  reportNotFound();
}