Compare four collision-handling strategies: linear probing, chained hashing, cuckoo hashing, and extendible hashing.
Linear Probe
Chained
Cuckoo
Extendible
Occupied
Tombstone
Active/Probing
0
Entries
0%
Load
0
Probes
Linear probing: on collision, scan forward for the next empty slot. Deletions use tombstones.
Configuration
Insert
Delete
Lookup
Algorithm
hash(key) % N → slot i Insert: if slot[i] empty → put
else probe i+1, i+2, ... Delete: find key, mark 🪦 Lookup: probe until found
or empty (not tombstone)
Each slot → linked list of entries
0
Entries
0
Max Chain
Chained hashing: each bucket holds a linked list. No load factor crisis—just longer chains.
Configuration
Insert
Delete / Lookup
Algorithm
bucket = hash(key) % N Insert: append to bucket list Delete: unlink from list Lookup: scan bucket list
+ No tombstones needed
+ Can grow indefinitely
- Pointer overhead
- Cache unfriendly
Two tables, two hash functions — always O(1) lookup
0
Entries
0
Evictions
Table 1 (hash₁)
Table 2 (hash₂)
Cuckoo hashing: two hash functions, two tables. Lookup is always exactly 2 probes. Insertions may evict existing keys.
Configuration
Insert
Lookup
Algorithm
Insert(key):
1. h1 = hash1(key) % N
2. If T1[h1] empty → done
3. Evict T1[h1] → x
4. Try T2[hash2(x)]
5. Repeat until empty or
cycle detected → rehash
Lookup: Check T1[h1(k)]
AND T2[h2(k)]
→ Always exactly 2 probes!
Dynamic: double directory on overflow, split only the full bucket
1
Global Depth
0
Entries
2
Buckets
Directory
Buckets
Extendible hashing: directory doubles only when needed. Multiple directory entries can point to the same bucket.
Configuration
Insert
Algorithm
Global depth = g
Dir entry = low g bits of hash
Insert:
1. Find bucket via low g bits
2. If bucket not full → insert
3. Else split bucket:
a. If local=global: double dir
b. Increment local depth
c. Rehash bucket entries