Hash tables

The idea in one line

A good hash spreads keys evenly across the array and is cheap to compute. It does not have to be cryptographic — it has to be fast and fair.

const index = hash(key) % buckets.length;
buckets[index];                 // one step, whatever the key

Collisions are not an edge case

Chaining is what most teaching implementations and many standard libraries use; open addressing with linear probing is what the fastest ones use, because probing neighbouring slots stays inside the cache line.

Load factor is the whole performance story

When the load factor crosses a threshold — usually around 0.75 — the table allocates twice as many buckets and rehashes every entry, because the index depends on the bucket count. That one insert costs O(n), and amortised over the inserts between resizes it is O(1) each, by the same doubling argument as a growable array.

So the honest statement is: O(1) average, O(n) worst case, amortised O(1) on insert. The worst case is real — every key colliding — and it is what a hash-flooding attack deliberately causes, which is why modern runtimes seed their hash functions randomly at startup.

load factor = entries / buckets

0.25   almost every lookup is one step
0.75   the usual resize threshold
0.95   chains are long, probes are long — lookups degrade sharply
1.5    you have written a linked list with extra steps

What the language gives you

Use Map when the keys are not string literals you wrote yourself: it takes any value as a key, reports its size in O(1), iterates in insertion order and has no prototype to collide with. A plain object is a hash table with a legacy interface attached to it.

And the in operator on an array is not this: arr.includes(x) is a linear scan. Converting a list you test against repeatedly into a Set is the single most common real-world application of this lesson.

const m = new Map();          // any key, including objects; keeps insertion order
m.set(key, value); m.get(key); m.has(key); m.delete(key); m.size;

const s = new Set();          // membership only
s.add(x); s.has(x);

const o = {};                 // string and symbol keys only; prototype chain; slower

Writing a hash

Math.imul matters: plain * on large integers loses precision in a double, and the hash stops being well distributed. A hash that ignores order (adding the character codes) makes every anagram collide, which is a memorable way to discover why the multiply is there.

function hash(text) {
  let h = 2166136261;                  // the FNV offset basis
  for (let i = 0; i < text.length; i++) {
    h ^= text.charCodeAt(i);
    h = Math.imul(h, 16777619);        // the FNV prime, with 32-bit multiplication
  }
  return h >>> 0;                      // as an unsigned 32-bit number
}