Hash table with chaining
mediumA collision is not an error - with more keys than buckets it is unavoidable. Chaining keeps a list per bucket, so lookup costs O(1 + α) where α is the average chain length.
O(1 + α)Worst O(n)Space O(n + m)Saved in this browser - no sign-up, nothing sent anywhere.
How hash table with chaining works
A hash table is an array of m buckets plus a rule for picking one: index = h(k) mod m. Computing that index costs the same no matter how many keys are stored, so the jump to the right bucket is O(1). Chaining answers the obvious follow-up - what happens when two keys pick the same bucket - by keeping a list per bucket and appending.
The whole game is the load factor α = n/m, which is exactly the average chain length. With a hash that spreads keys evenly, a lookup computes one index and then scans about α entries, so it costs O(1 + α). Hold α near 0.75 by resizing and chains average under one entry; let 1000 keys pile into 8 buckets and every lookup wades through 125.
Reach for chaining when deletions are frequent or the load is unpredictable: removing a key just unlinks it from its chain, no tombstones, and the table keeps working - merely slower - even past α = 1. This module implements the textbook variant: h(k) = k mod m, one list per bucket, and an update in place when the key already exists.
Step by step
- Start with m = 7 empty buckets. Insert 10: h(10) = 10 mod 7 = 3, bucket 3 is empty, so 10 lands alone - the ideal case.
- Insert 15: 15 mod 7 = 1, another empty bucket. Two keys across seven buckets puts α at 0.29 - lookups average about one comparison.
- Insert 24: 24 mod 7 = 3, but bucket 3 already holds 10. That is a collision; 24 is appended to the chain and nothing else moves.
- Look up 24: compute 24 mod 7 = 3, jump straight to bucket 3, scan the chain - 10 is not 24, the next entry matches. Two comparisons.
- Look up 30: 30 mod 7 = 2 and bucket 2 is empty, so 30 is definitely absent. One index computation, zero comparisons.
- Delete 10: find it in bucket 3 and unlink it. The chain shrinks to just 24 - no tombstone, no shifting, every other bucket untouched.
Complexity
| Average time | O(1 + α) |
|---|---|
| Worst case time | O(n) |
| Space | O(n + m) |
Every key hashing to one bucket turns the table into a linked list.
Reference implementation
Python
class ChainedHashTable:
def __init__(self, m=8):
self.buckets = [[] for _ in range(m)]
self.n = 0
def _index(self, key):
return hash(key) % len(self.buckets)
def put(self, key, value):
b = self.buckets[self._index(key)]
for i, (k, _) in enumerate(b):
if k == key:
b[i] = (key, value) # update in place
return
b.append((key, value)) # collision: same bucket
self.n += 1
def get(self, key):
for k, v in self.buckets[self._index(key)]:
if k == key:
return v # O(chain length)
raise KeyError(key)JavaScript
class ChainedHashTable {
constructor(m = 8) {
this.buckets = Array.from({ length: m }, () => []);
this.n = 0;
}
#index(key) {
let h = 2166136261; // FNV-1a
for (const ch of String(key)) {
h ^= ch.charCodeAt(0);
h = Math.imul(h, 16777619);
}
return (h >>> 0) % this.buckets.length;
}
put(key, value) {
const b = this.buckets[this.#index(key)];
const hit = b.find((e) => e[0] === key);
if (hit) { hit[1] = value; return; }
b.push([key, value]);
this.n++;
}
get(key) {
return this.buckets[this.#index(key)].find((e) => e[0] === key)?.[1];
}
}Worth noticing
A collision is not an error
Two keys landing in the same bucket is normal and expected - with m buckets and more than m keys it is unavoidable. Chaining simply keeps a list per bucket, so the table degrades gracefully instead of failing.
Load factor is the only number that matters
α = n/m is the average chain length, so an average lookup costs O(1 + α). Keep α around 0.75 and lookups are effectively constant. Let it reach 10 and every lookup scans ten entries.
The worst case is still O(n)
If every key hashes to the same bucket, the table becomes one linked list. That is not hypothetical - hash-flooding attacks deliberately craft such keys, which is why production hash functions are seeded with a random value at process start.
Why m should be prime
Set m to 8 and insert 4, 8, 12, 16, 20: they all land in even buckets, and half the table sits empty. A prime modulus has no common factors to conspire with patterns in the keys.
Common pitfalls
- Using a table size that shares factors with the keys: with m = 8, the keys 4, 8, 12, 16, 20 fill only even buckets while half the table sits empty. A prime m breaks such patterns.
- Skipping the resize policy. Nothing fails when α climbs - the table just degrades linearly, and a lookup at α = 10 quietly scans ten entries where it used to scan one.
- Hashing on mutable state. Mutate a key after inserting it and h(k) points at a different bucket, so the entry is still in the table but no lookup will ever find it.
- Exposing an unseeded hash to user input. Hash-flooding attacks craft keys that all land in one bucket, turning every operation into an O(n) list scan - production hashes are seeded at process start.
- Forgetting the update check on insert. put must first scan the chain for an existing key, or the same key gets stored twice and delete only removes one copy.
Where it is used
- Java's HashMap resolves collisions by chaining, converting a bucket's list to a red-black tree once it exceeds 8 entries.
- Frequency maps in interview problems - two-sum, group-anagrams, and first-unique-character all lean on O(1) average insert and lookup.
- Symbol tables in compilers and interpreters, where identifiers arrive in unpredictable numbers and deletions accompany scope exits.
- Deduplication passes - seen-sets over URLs, IDs, or rows - where each membership test must stay constant time at millions of entries.
Frequently asked questions
What is the time and space complexity of a hash table with chaining?
Average O(1 + α), where α = n/m is the average chain length, and O(n) in the worst case when every key hashes to one bucket and the table becomes a linked list. Space is O(n + m): n stored entries plus m bucket heads.
What is a good load factor for a hash table?
Around 0.75 for chaining - the default Java's HashMap ships with. It keeps average chains below one entry while wasting little memory. Chaining still functions above 1.0, just proportionally slower, which is why the threshold is a tuning choice rather than a hard limit.
What happens when two keys hash to the same bucket?
Both are stored in that bucket's list, and lookups scan the list comparing actual keys. Collisions are guaranteed by the pigeonhole principle whenever n exceeds m, so the design question is never how to avoid them - it is how to keep chains short.
Is chaining or open addressing better?
Chaining tolerates high load factors and deletes cleanly; open addressing stores everything inline, which is far kinder to CPU caches but needs tombstones and an early resize. Standard libraries split on it - Java chose chaining, Python and Rust chose open addressing.