Hash Table — Separate Chaining

A hash table with separate chaining maps each key to a bucket via a hash function — here h(k) = k mod capacity — and resolves collisions by keeping a linked list of every key that landed in that bucket. Operations run in O(1) on average; a collision just makes one bucket's list slightly longer, leaving every other bucket untouched.

Picture an apartment building's mailbox wall. The hash function is the rule "your apartment number mod the number of boxes" — instant, no searching. The catch: several tenants can share box 2. Separate chaining shrugs and stacks all their envelopes in that one box. Finding your mail means jumping straight to your box, then riffling through a handful of envelopes. That riffle is the entire cost of a collision.

How Separate Chaining Works

The table is an array of capacity buckets, each holding a list of keys. Every operation starts the same way: compute h(k) = k mod capacity, jump to bucket h(k), and work only inside that one chain. The other buckets might as well not exist — that locality is the whole trick.

insert(k) walks the chain comparing each node's key against k. If it finds a match, it stops and changes nothing — this table has set semantics, so inserting a key that's already present is a deliberate no-op, not an update. If the walk reaches the end without a match, the new key is prepended to the head of the chain. With a real linked list, prepending is O(1): no shifting, no scanning back. (The displayed Python uses chain.insert(0, ...) on an array-backed list, which secretly pays O(chain length) to shift elements — fine for a five-node teaching chain, but a production chaining table uses an actual linked list with a head pointer.)

get(k) walks the same chain and returns the position of the match, or -1 if it falls off the end. delete(k) walks until it matches, splices that one node out, and returns True; the rest of the chain reconnects around the gap. No tombstones, no shifting other entries, no disturbance to any other bucket — compare that to open addressing, where deletion requires careful bookkeeping so later probes don't break.

Notice that all three operations share one skeleton: hash, walk, decide. Separate chaining handles collisions by barely handling them — it converts a global problem (two keys want the same slot) into a local one (a short linear search inside one box).

Separate Chaining Step by Step

The player starts you with the default table: 5 empty buckets, so h(k) = k mod 5. Walk this sequence and you'll see every behavior the structure has.

1. insert(7) → hash(7) = 7 % 5 = 2. Bucket 2 is empty, so the walk ends immediately and 7 is prepended: bucket 2 is now [7].
2. insert(12) → hash(12) = 12 % 5 = 2. Same box, different tenant — your first collision. The cursor checks [2][0] = 7, which is not 12, reaches the end of the chain, and prepends: bucket 2 is [12, 7]. Note the order — newest at the head.
3. insert(3) → hash(3) = 3 % 5 = 3. Bucket 3 is empty; prepend gives [3]. The collision in bucket 2 didn't slow this down by a nanosecond.
4. insert(17) → hash(17) = 17 % 5 = 2. Now the walk earns its keep: [2][0] = 12 ≠ 17, [2][1] = 7 ≠ 17, end of chain, prepend. Bucket 2 is [17, 12, 7].
5. get(12) → hash(12) = 2. The cursor riffles through the envelopes: [2][0] = 17, no; [2][1] = 12, match — found at position 1. Two comparisons, even though the table holds four keys.
6. delete(12) → hash(12) = 2. Same walk: 17 misses, 12 matches at depth 1, and the node is spliced out. Bucket 2 closes up to [17, 7].

A get or delete for a key that isn't there — say get(22), which also hashes to 2 — walks the whole chain, falls off the end, and reports not found. The cost of a miss is the full chain length, which is exactly why you want chains short.

One honesty note: the player refuses to grow any chain past 6 nodes, announcing that the insert "would exceed visualization depth 6 (no real limit)." That cap exists purely so chains fit on the 1920×1080 canvas — a real separate-chaining table has no maximum chain length whatsoever. Chains grow as long as collisions demand; they just get slow.

In the animation, buckets stack vertically and each chain extends rightward as linked nodes. The cursor glides node to node as it compares, the matched node flashes green, and a prepended key slides in at the chain's head — the canvas is showing you the hash, the walk, and the commit as three distinct beats.

Time and Space Complexity

Let α = n / capacity be the load factor — the average chain length under a well-behaved hash function.

The average time complexity is really O(1 + α): one hash computation plus an expected walk of α nodes. Keep α a small constant (chaining tolerates α around 1.0 comfortably, where open addressing wants well under that) and it collapses to O(1). The worst case is every key crowding into one bucket — the table degenerates into a single linked list, and every operation pays O(n). This is rare by accident but achievable on purpose: hash-flooding attacks feed a server keys chosen to collide, which is why serious runtimes randomize their hash seeds.

Space is O(n + m) for n entries and m buckets: the bucket array costs m no matter what, and the n chain nodes are distributed across it.

Edge Cases

• Duplicate insert — the walk finds the key and returns without changing anything. Set semantics; a key/value dict would update in place at that same moment instead.
• Operating on an empty bucket — insert prepends immediately; get and delete fall off a zero-length chain and report not found. No special-casing needed.
• Delete of an absent key — full walk, end of chain, return False. The table is untouched.
• All keys colliding — legal, correct, and slow. The structure quietly becomes a linked list wearing a hash table's badge.

Common Mistakes

• Comparing n to capacity like it's open addressing. A chaining table with 1000 buckets and 5000 entries averages 5 nodes per chain — perfectly serviceable. Load factor thresholds for chaining sit near 1.0, not 0.75.
• Never resizing. If capacity stays fixed while keys pour in, every box overflows with envelopes and each lookup is a long riffle. Resize when α creeps past a small constant.
• Skipping the duplicate check on insert. Prepend blindly and the same key exists twice: get finds whichever copy sits earlier, delete removes only one, and your table's contract is now a coin flip.
• Trusting k mod capacity in production. It's perfect for a visualization, but keys sharing a common factor with capacity pile into a fraction of the buckets. Real tables scramble bits first (MurmurHash, SipHash, Python's seeded hash).
• Treating chaining and open addressing as interchangeable. Chaining is simpler, deletes cleanly, and shrugs at high load factors, but pays in pointer chasing and cache misses; open addressing keeps one contiguous array that modern CPUs adore at moderate load. Choose by memory behavior, not habit.