Hash Tables

Fifty thousand users are loaded in memory and a login form is holding one email address. With a plain array, finding the matching user means comparing that email against entry after entry until one matches. It works. It also means that when the email belongs to the last user in the list — or to nobody at all — you have touched all fifty thousand records to answer a single question, and every new signup makes that worse.

A hash table removes the search. Instead of asking where a key might be, it computes where the key must be, directly from the key itself. Picture a mailroom wall of numbered pigeonholes and one rule that turns any name into a hole number: to leave a note for Ada you apply the rule, walk to hole 2, and drop it in. To collect Ada’s mail you apply the same rule and open the same hole. Nobody ever reads the other holes.

From key to slot

That rule is the hash function. It takes a key of any size — a string, a URL, a pair of numbers — and returns a fixed-size integer. Two properties make it useful. It is deterministic within a single run: ask it for the same key twice and both answers match. Across runs that guarantee usually disappears, because many runtimes seed their hashing randomly at startup — for reasons covered below — which is why a hash value is something to compute and use, never something to store or send. And it scatters: keys that look almost identical should produce integers that do not.

The integer is far too large to use as an array position, so the table takes it modulo the number of buckets — the numbered holes — it currently owns. Hash the key, take the remainder, and you have an index into an ordinary array, computed in a number of steps that has nothing to do with how many entries the table holds. That is the whole trick, and everything below is a consequence of it.

Here are five keys going into the five buckets of the table sketched further down, each bucket number computed by that sketch’s multiply-by-31 hash taken modulo five.

Collisions and chains

Watch bucket 2 on the fourth step. “rat” hashes into a bucket that “cat” already occupies — a collision — while bucket 1 never receives anything at all. Neither of those is a bug. A hash function maps an unbounded set of keys onto a small set of buckets, so two keys sharing a bucket is not bad luck; with more possible keys than buckets it is arithmetically unavoidable.

The usual answer is chaining: a bucket holds a short list rather than a single entry, and a colliding key is appended to it. A lookup then hashes once to find the bucket and walks that list comparing whole keys, because the hash alone cannot tell “cat” from “rat” — it throws information away by design. The other main family, open addressing, keeps one entry per slot and probes forward for the next free slot on collision; it packs more tightly and reads faster from cache, at the price of fiddly deletion. Chaining is easier to see, so it is what the sketch below does.

The cost, honestly

The headline is O(1): lookup time does not grow with the number of entries. That claim rests on two conditions, and both are worth stating out loud.

The first is that the hash spreads keys evenly. If every key lands in one bucket, a lookup degenerates into scanning a single long list — O(n), the exact thing you were avoiding, now with a hash computation on top. This is not only a theoretical worry. When an attacker controls the keys, they can submit thousands chosen to collide and turn a cheap request handler into a CPU sink, which is why modern runtimes hash with a random seed chosen at run time (per process for Python’s SipHash-based string hashing, per map for Rust’s default hash map) rather than a fixed, predictable function.

The second condition is that chains stay short, which means the table has to grow. Load factor — entries divided by buckets — is the number that governs this. When it crosses a threshold, often around 0.75, the table allocates a larger array and rehashes every existing key into it. That single insert costs O(n). Averaged over all the cheap inserts that led up to it, the cost per insert is still constant, and that is precisely what amortized O(1) claims: not “always fast”, but “fast on average, with an occasional expensive step you can see coming”.

Put numbers on “on average”. A table that starts with 8 buckets and doubles whenever the next insert would push the load factor past 0.75 rehashes 6 entries, then 12, then 24. By 1,000 entries it has resized eight times and moved 1,530 entries in all: about one and a half extra moves per insert. Each resize moves only six more entries than every earlier resize put together, so that figure never reaches two, however large the table grows.

Two more properties are worth knowing before you reach for one. A hash table has no order of its own — iteration follows bucket layout, which is arbitrary — so languages that guarantee insertion order (JavaScript’s Map, Python’s dict) maintain a separate sequence alongside the buckets to provide it. And a key must not change after it is stored: mutate it and its hash changes with it, so the table starts looking in a different bucket and the entry becomes unreachable. That is the reason hash keys are expected to be immutable.

The mechanism fits in about twenty lines — a hash, an array of buckets, and chaining on collision:

type Entry<V> = { key: string; value: V };

class HashTable<V> {
  private readonly buckets: Entry<V>[][] = Array.from({ length: 5 }, () => []);

  private bucketFor(key: string): number {
    let hash = 0;
    for (let i = 0; i < key.length; i += 1)
      hash = (hash * 31 + key.charCodeAt(i)) | 0;
    return Math.abs(hash) % this.buckets.length;
  }

  set(key: string, value: V): void {
    const bucket = this.buckets[this.bucketFor(key)]!;
    const existing = bucket.find((entry) => entry.key === key);
    if (existing) existing.value = value;
    else bucket.push({ key, value });
  }

  get(key: string): V | undefined {
    return this.buckets[this.bucketFor(key)]!.find(
      (entry) => entry.key === key,
    )?.value;
  }
}

Two things are missing on purpose. It never resizes — five buckets forever — so chains grow without limit and lookups slide toward O(n) as it fills, which is also what makes it small enough to trace by hand: run it over the five keys above and you get the diagram. And multiplying by 31 is a decent scattering hash for short strings but a poor one under adversarial input. A production table fixes both; the shape stays exactly this.

class HashTable<V> {
  private buckets: Entry<V>[][] = Array.from({ length: 5 }, () => []);
  private size = 0;

  get bucketCount(): number {
    return this.buckets.length;
  }

  private bucketFor(key: string): number {
    let hash = 0;
    for (let i = 0; i < key.length; i += 1)
      hash = (hash * 31 + key.charCodeAt(i)) | 0;
    return Math.abs(hash) % this.buckets.length;
  }

  set(key: string, value: V): void {
    const existing = this.buckets[this.bucketFor(key)]!.find(
      (entry) => entry.key === key,
    );
    if (existing) {
      existing.value = value;
      return;
    }
    if ((this.size + 1) / this.buckets.length > 0.75) this.resize();
    this.buckets[this.bucketFor(key)]!.push({ key, value });
    this.size += 1;
  }

  get(key: string): V | undefined {
    return this.buckets[this.bucketFor(key)]!.find(
      (entry) => entry.key === key,
    )?.value;
  }

  private resize(): void {
    const old = this.buckets;
    this.buckets = Array.from({ length: old.length * 2 }, () => []);
    for (const bucket of old) {
      for (const entry of bucket)
        this.buckets[this.bucketFor(entry.key)]!.push(entry);
    }
  }
}

const table = new HashTable<number>();
['cat', 'dog', 'fig', 'rat', 'owl'].forEach((key, i) => table.set(key, i));
console.log(table.bucketCount, table.get('rat')); // 10 3