HashingHashing

Hash Table (separate chaining)

An array of buckets indexed by a hash of the key, giving expected O(1) insert, lookup, and delete.

Learn Hash Table →
a
∅
0
∅
1
∅
2
∅
3
∅
4
∅
5
∅
6
bucket 0
∅
0
bucket 1
∅
0
bucket 2
∅
0
bucket 3
∅
0
bucket 4
∅
0
bucket 5
∅
0
bucket 6
∅
0
1/41Empty table with m = 7 buckets. Colliding keys share a bucket as a linked chain, so the table never "fills up" — only the chains grow.
Hashed bucketChain node comparedMatchInserted / removed
PseudocodeLearn Hash Table →
1h = key % m
2insert: scan bucket[h]; if key present: done, else append to the chain
3search: scan bucket[h] comparing each key
4delete: scan bucket[h]; unlink the matching node
Variables
m7
size0
load0.00
Complexity
access O(1)
search O(1)
insert O(1)
delete O(1)
Speed