Hash Table

A hash table finds things almost instantly by computing where they live instead of searching for them. A hash function turns each key into a bucket number, so to store or look up a key you jump *straight* to its bucket — no scan. It's the structure behind dictionaries, maps, and sets in nearly every language.

Hash, then bucket

The hash function maps a key to an integer; taking that modulo the number of buckets gives an index into the table's array. A good hash spreads keys *evenly* across buckets, so each holds only a few. Then a lookup is: hash the key, go to that bucket, and check what's there — close to constant time.

function hash(key, numBuckets) {
  let h = 0;
  for (const ch of String(key)) {
    h = (h * 31 + ch.charCodeAt(0)) | 0; // mix the characters
  }
  return Math.abs(h) % numBuckets;        // fold into a bucket index
}

Collisions — two keys, one bucket

Since many keys map into few buckets, two different keys will sometimes land in the same bucket — a collision. The common fix is chaining: each bucket holds a small list, and colliding keys are simply appended to it. A lookup hashes to the bucket, then walks its short chain to find the exact key.

buckets (size 5)              key % 5
  0: -> ("cat",3)
  1: -> ("dog",7) -> ("emu",9)   <- collision, chained
  2:
  3: -> ("ant",1)
  4:
lookup("emu"): hash -> bucket 1 -> walk chain -> found