Loading...
Hash tables, functions, collision resolution, and applications
Section 3 of 4
Strategies for handling when different keys hash to the same index
A collision occurs when two different keys produce the same hash value. Even with perfect hash functions, collisions are inevitable due to the pigeonhole principle.
α = n/m (elements/table size)
Each slot contains a linked list of all elements that hash to that slot
Average: O(1 + α), Worst: O(n)
// Insertion
table[h(key)].add(key, value)// Linear: h(k, i) = (h(k) + i) % m
// Quadratic: h(k, i) = (h(k) + i²) % m
// Double: h(k, i) = (h₁(k) + i×h₂(k)) % m| Method | Search | Insert | Delete | Space |
|---|---|---|---|---|
| Chaining | O(1 + α) | O(1) | O(1 + α) | Higher |
| Linear Probing | O(1) | O(1) | O(1)* | Lower |
| Quadratic Probing | O(1) | O(1) | O(1)* | Lower |
| Double Hashing | O(1) | O(1) | O(1)* | Lower |
* Requires lazy deletion for open addressing