Hash Table Insert

Insert a key into a separate-chaining hash table, prepending to the bucket selected by the hash.

Time O(1) avg Space O(n) Hash Table insert

How it works

Insert a key into a separate-chaining hash table, prepending to the bucket selected by the hash.

Implementation

function hashInsertOp(state, value) {
  const bucketHead = state.bucketHead;
  const nodeKey = state.nodeKey;
  const nodeNext = state.nodeNext;
  const numBuckets = state.numBuckets;
  const bucket = value % numBuckets;
  probeSlot(bucket);
  let current = bucketHead[bucket];
  while (current !== -1) {
    compareKeys(current, value);
    if (nodeKey[current] === value) {
      reportFound(current);
      return;
    }
    current = nodeNext[current];
  }
  const id = nodeKey.length;
  nodeKey[id] = value;
  nodeNext[id] = bucketHead[bucket];
  bucketHead[bucket] = id;
  insertNode(id, value, bucket);
  finish(id);
}