Imagine labeling grocery shelves by the first letter of each item. Apples fit in the A slot, but avocados need that same slot. A hash collision happens when distinct keys produce the same hash value or table position. section 5.7
A collision becomes dangerous if the new value overwrites the old one: asking for apples could return the price of avocados. A simple workaround stores several key-value pairs in a linked list attached to the shared slot. section 5.7
Collisions affect hash-table performance in predictable ways:
- A small linked list adds only a little searching when retrieving a value. section 5.7
- A heavily crowded slot can make the table behave like a long list, producing O(n) operations in the worst case. section 5.8
- A good hash function spreads keys across the array, while a low load factor reduces crowding. section 5.10 section 5.8
The A-slot traffic jam
With alphabetic placement, apples and avocados both map to the A slot. Bananas use a separate slot. The A slot therefore needs a linked list containing both entries; finding bananas remains quick, while finding apples requires searching that chain. section 5.7
You usually use a language’s built-in hash table rather than implementing collision handling yourself. Still, recognizing collisions explains why a good hash function and sensible load factor matter. section 5.8 section 5.11
