Cairn
data structures · separate chaining · O(1) average get/put/delete

↩ back to Hash-Based

Hash Table

Every structure on this site so far finds things by comparing: binary search halves a range, a binary search tree walks left or right, a linked list walks node by node. A hash table skips comparing almost entirely. It turns a key into a number — the hash — and uses that number as a direct index into an array of buckets. Look up the same key later, get the same number, land on the same bucket. No searching required to find the right neighborhood; only within it.

That "which bucket" step is O(1), but two different keys can hash to the same bucket — a collision — and with a fixed number of buckets, collisions are certain to happen eventually, not a rare edge case. The demo below uses separate chaining: each bucket holds a small list of every key that landed there, so a collision just means comparing against the handful of keys sharing that bucket instead of searching the whole table.

Try it

Put a key/value pair, get a key back out, or delete one. The log line shows the hash computed and which bucket it lands in — watch what happens when two different keys land on the same one. Keep putting new keys and watch the stats line above the table: once entries divided by buckets crosses 0.75, the table doubles its bucket count and rehashes everything that's in it — put just one more distinct key on top of the sample below (6 entries in 8 buckets already sits right at the threshold) to see it happen.

Loaded a sample table (8 buckets). Try "lion" — it shares bucket 4 with two other keys.

Core operations

Reference implementation

class HashTable {
  #buckets;
  #size = 0;

  constructor(numBuckets = 8) {
    this.#buckets = Array.from({ length: numBuckets }, () => []);
  }

  #hash(key, numBuckets = this.#buckets.length) {
    let h = 0;
    const s = String(key);
    for (let i = 0; i < s.length; i++) {
      h = (h * 31 + s.charCodeAt(i)) >>> 0; // >>>0 keeps it a positive 32-bit int
    }
    return h % numBuckets;
  }

  #resize() {
    const bigger = Array.from({ length: this.#buckets.length * 2 }, () => []);
    for (const bucket of this.#buckets) {
      for (const [key, value] of bucket) {
        bigger[this.#hash(key, bigger.length)].push([key, value]);
      }
    }
    this.#buckets = bigger;
  }

  put(key, value) {
    const bucket = this.#buckets[this.#hash(key)];
    const existing = bucket.find(entry => entry[0] === key);
    if (existing) { existing[1] = value; return; }
    bucket.push([key, value]);
    this.#size++;
    if (this.#size / this.#buckets.length > 0.75) this.#resize();
  }

  get(key) {
    const bucket = this.#buckets[this.#hash(key)];
    const entry = bucket.find(entry => entry[0] === key);
    return entry ? entry[1] : undefined;
  }

  has(key) {
    const bucket = this.#buckets[this.#hash(key)];
    return bucket.some(entry => entry[0] === key);
  }

  delete(key) {
    const bucket = this.#buckets[this.#hash(key)];
    const i = bucket.findIndex(entry => entry[0] === key);
    if (i === -1) return false;
    bucket.splice(i, 1);
    this.#size--;
    return true;
  }
}

The multiply-by-31 in #hash is the standard trick for folding a string into a number: it's the same scheme Java's String.hashCode() uses, chosen because 31 is odd and prime, which spreads similar strings across different buckets better than an even or composite multiplier would. #resize doubles the bucket count and reinserts every key, since a key's bucket depends on numBuckets — the old bucket assignments don't carry over, every entry has to be rehashed against the new count. Verified against a plain-object reference model over 50,000 randomized interleaved put/get/delete/has trials (small key spaces to force frequent collisions and repeated resizes), checking every get/has result after every operation and that the load factor never exceeds 0.75 after a put returns, plus edge cases (delete on an empty table, delete a key twice, put the same key twice with different values, a deliberately-collided pair of keys, enough sequential inserts to force several resizes in a row) — see /tmp/ht_test.js, scratch, not committed.

Pitfalls

Resizing isn't free — it's just infrequent. Doubling the bucket count and rehashing every entry is an O(n) pass, not O(1). The demo above still calls put "O(1) average" and that's true amortized over many calls — most puts just append to a bucket, and the occasional expensive rehash gets averaged out over all the cheap ones between it and the last one — but the one put that crosses the 0.75 threshold is genuinely slower than its neighbors, a real (if brief) pause a latency-sensitive system would feel. Measured directly against the exact hash/resize logic shown in the reference implementation above (instrumented with a work counter, nothing about the algorithm changed): 100,000 sequential puts trigger 15 resizes, and the costliest one — put #98,305, growing the table from 131,072 to 262,144 buckets — does 98,305 units of rehash work by itself, where an ordinary put does 1. That one put is a 98,305x spike, not a "genuinely slower" that stays vague. This is the same amortized-vs-per-call distinction the queue page's array-backed implementation runs into with its occasional compacting pass, just triggered by a growing table instead of a growing dead prefix. Pick a size and run it yourself below:

Pick a size and click Measure — it runs that many distinct puts through the exact hash/resize logic above, instrumented to count real rehash work, and reports every resize it triggers.

A bad hash function defeats the whole point. If hash mapped every key to bucket 0, the table above would still be correct — every get would still return the right value — just no faster than a linked list, since every operation would scan one giant chain. Collisions aren't a bug to eliminate (they're mathematically guaranteed once there are more possible keys than buckets); a good hash function just spreads them thin instead of piling them into a few buckets.

Mutating a key after it's inserted. The bucket a key lives in is decided once, at insert time, from whatever the key's value was then. In a language where keys can be mutable objects, changing the object after inserting it doesn't move it to the bucket matching its new hash — the entry just becomes unreachable by any key that would hash correctly now. This is why languages that let you use custom objects as hash keys generally expect them to be treated as immutable once inserted.

Where hash tables show up

Measuring the memory claim

"A hash table spends more memory than a tree holding the same entries" sounds like a flat rule, but nothing on this site had ever actually counted it. The comparison below isn't against the plain Binary Search Tree — that page only guarantees O(log n) on average, not worst case, so it's not the tree the Complexity section's own worst-case claim below means — it's against an AVL tree, extended with one extra field per node so it holds a key and a value the same way this page's own [key, value] chain entries do (the real shipped AVL class is a set, one orderable value per node — adding a second field for the associated payload is the only change). Counting real reference-sized slots, the same convention Fenwick Tree's own memory comparison against Segment Tree uses (array/field counts, not a full JS-engine byte audit): this table's buckets array contributes one slot per bucket, each stored entry contributes one slot inside its own bucket's array plus two more inside its [key, value] pair, so n entries across B buckets cost B + 3n slots total. The extended AVL node (key, value, left, right, height) costs a fixed 5n.

Pick a size and click Compare — it grows the bucket array with the exact doubling/0.75-load-factor logic above, up to that many entries, then counts real reference slots on both sides.

Because B only ever doubles, it isn't a tight 1.33n — it ranges from 1.33n (load factor just at the 0.75 limit, right before the next resize) up to 2.67n (right after one, load factor freshly halved to 0.375). At n = 98,304, B = 131,072 and the table costs 425,984 slots against the AVL tree's 491,520 — the table uses 13.33% fewer. One more entry triggers a resize to B = 262,144: at n = 98,305 the table costs 557,059 slots against the tree's 491,525 — now 13.33% more. Same two structures, same single extra entry, opposite verdict — "generally spends more memory" was never true in one direction; it oscillates around rough parity depending on how recently the table last resized, narrowest right after a resize and widest right before the next one.

Complexity

Time: put, get, and delete are all O(1) amortized average — "average" because a reasonable hash function is assumed to spread keys thinly across buckets, and "amortized" on top of that because keeping the load factor bounded means resizing occasionally, and any single put that triggers a resize actually costs O(n) (the "resizing isn't free" pitfall above walks through that call specifically). Worst case is still O(n) if every key collides into a single bucket regardless of resizing, since that one chain degrades to a linear scan no matter how many total buckets exist. Compare to an AVL tree, which guarantees O(log n) worst case with no hash function required — the trade is a probabilistic O(1) against a guaranteed O(log n). Space: O(n) for n entries, plus the unused capacity sitting in empty or underfull buckets — see Measuring the memory claim above: that slack oscillates to within about 13% of a comparable tree's own fixed per-node cost, rather than sitting one-directionally above it.

That O(n) space is the cost of storing every key so get has something to hand back. If all that's ever needed is "have I seen this key?" with no value to retrieve, a Bloom filter answers the same question in a fixed number of bits chosen up front — no keys stored at all — at the cost of occasionally answering yes when the true answer is no.

Growing this table always means the O(n) full rehash the Complexity section above prices out — every key gets reinserted, whether or not its own bucket ever overflowed. Extendible hashing avoids that by growing a small directory of bucket pointers instead of one big array, splitting only the bucket that actually overflowed and leaving everything else untouched — the trade that matters once a rehash means moving records on disk rather than just in memory.

Everything on this page hashes a key to a bucket within one table. A different question — which server owns a key, when the servers themselves can come and go — needs the buckets to be far more stable than a fixed array's % numBuckets allows; see consistent hashing for how that's done.

Chaining also isn't the only way to resolve a collision. Cuckoo hashing gives every key exactly two candidate slots across two separate tables instead of an unbounded chain in one, trading this page's average-case O(1) for a worst-case O(1) guarantee on get — at the cost of a trickier insert that can occasionally evict its way into an unresolvable cycle and force a full rehash. Robin Hood hashing is a third option, splitting the difference: it keeps chaining's single table and one hash function but adds a rule that bounds how unlucky any one key's probe length can get, without chaining away this page's worst-case risk the way cuckoo hashing does. Hopscotch hashing is a fourth: like cuckoo hashing it gives get a hard worst-case bound, but like Robin Hood hashing it keeps a single table and one hash function, using a per-slot bitmap to bound every key's distance from home instead of a second table to bound the number of candidate slots. See Choosing a Hash Table Collision Strategy for the full four-way comparison.