How it works

The explanation, with examples you can run.

Hashing and collisions

A good hash function spreads keys evenly and is fast to compute. Even so, with more possible keys than slots, two keys will sometimes land in the same slot. There are two main ways to cope:

Separate chaining: each slot holds a short list of entries. Java's HashMap does this, and (since Java 8) turns a chain into a small balanced tree once it reaches 8 entries in a table of at least 64 slots.
Open addressing: all entries live in the array itself. On a collision the table probes other slots in a fixed sequence until it finds a free one. CPython's dict does this, with a probe sequence that mixes in the higher bits of the hash.

Either way the expected work per lookup depends on the load factor, entries divided by slots. Keep it bounded and each slot holds a constant number of keys on average. Java's HashMap resizes at 0.75 by default; CPython's dict resizes when it is two thirds full. Resizing allocates a table about twice as big and reinserts every key, because each key's slot depends on the table size. Like a dynamic array's growth, it is O(n) occasionally and O(1) amortised.

Here is a small chained table with a 0.75 limit, first with a real hash function and then with one that sends every key to the same place:

Your code

function fnv1a(str) {                    // a simple, decent string hash
  let h = 0x811c9dc5;
  for (let i = 0; i < str.length; i++) {
    h ^= str.charCodeAt(i);
    h = Math.imul(h, 0x01000193) >>> 0;
  }
  return h;
}

class HashMap {
  constructor(hash = fnv1a) {
    this.hash = hash;
    this.buckets = Array.from({ length: 8 }, () => []);
    this.size = 0;
    this.resizes = 0;
  }
  bucketFor(key) {
    return this.buckets[this.hash(key) % this.buckets.length];
  }
  set(key, value) {
    const bucket = this.bucketFor(key);
    const entry = bucket.find((e) => e[0] === key);
    if (entry) { entry[1] = value; return; }
    bucket.push([key, value]);
    if (++this.size / this.buckets.length > 0.75) this.grow();   // load factor limit
  }
  get(key) {
    const entry = this.bucketFor(key).find((e) => e[0] === key);
    return entry && entry[1];
  }
  grow() {
    const old = this.buckets.flat();
    this.buckets = Array.from({ length: this.buckets.length * 2 }, () => []);
    for (const [k, v] of old) this.bucketFor(k).push([k, v]);       // rehash everything
    this.resizes++;
  }
  longestChain() {
    return this.buckets.reduce((max, b) => Math.max(max, b.length), 0);
  }
}

const good = new HashMap();
for (let i = 0; i < 100_000; i++) good.set("user:" + i, i);
console.log("buckets", good.buckets.length, "resizes", good.resizes, "longest chain", good.longestChain());
console.log(good.get("user:4242"));

const bad = new HashMap(() => 42);        // every key gets the same hash
let t = performance.now();
for (let i = 0; i < 5_000; i++) bad.set("user:" + i, i);
console.log("all in one bucket:", bad.longestChain(), "long, took", (performance.now() - t).toFixed(0), "ms for 5,000 keys");

⌘/Ctrl + Enter

OutputNot run yet

Press Run to see what your code prints, in order.

Runs in this browser, in an isolated frame with no access to this page. console.log, info, warn and error are shown; code runs as a classic script, so use an async function for await.

With FNV-1a, 100,000 keys spread over 262,144 buckets after 15 resizes and no chain was longer than 4. With the constant hash every insert scans one ever-longer list, so 5,000 keys took tens of milliseconds in Node 22 (40 to 80 ms across runs), and doubling the keys roughly quadrupled the time. That quadratic blow-up is what hash flooding attacks exploit, by sending a server thousands of form fields whose names collide. Python randomises its string hash per process (SipHash, PEP 456) for exactly this reason; set PYTHONHASHSEED only when you need reproducible runs.

The contract on keys

A table finds a key by hash and then confirms with equality. So equal keys must produce equal hashes, and a key's hash must not change while it is in the table. In Java you override equals and hashCode together; in Python, __eq__ and __hash__; mutable lists can't be dict keys at all. JavaScript's Map compares objects by identity, so two different objects with the same contents are different keys.

What you give up

Hash tables have no useful order. JavaScript Map and Python dict iterate in insertion order because they keep a separate dense array of entries, but neither can give you "all keys between A and C" or "the smallest key" without a full scan. When you need ranges or ordering, use a sorted structure: a balanced tree, a B-tree, or a sorted array with binary search.

Check yourself

3 questions. Get them all right to finish this topic.

1.Why is a hash table lookup O(1) on average but O(n) in the worst case?
2.Why do Python and many web frameworks randomise string hashing per process?
3.You use a JavaScript object `{x: 1}` as a key in a Map, then look it up with a different object `{x: 1}`. What do you get?

0 of 3 right so far. Get all three to finish this topic.

Hash tables

How it works

Hashing and collisions

The contract on keys

What you give up

Check yourself

Go deeper