Collisions & Load Factor
Overview
A hash collision occurs when two distinct keys mathematically produce the exact same array index. The Load Factor is the ratio of stored elements to total array slots (N / Capacity). As the load factor increases, collisions become highly probable.
Because the universe of possible keys is infinitely larger than the physical array, collisions are a mathematical certainty (the Pigeonhole Principle). How a hash table resolves these collisions dictates whether it maintains O(1) performance or degrades to a catastrophic O(N).
Where used: Language runtime engineering: deciding when a dictionary must resize its underlying array, Security: defending against hash-flooding Denial of Service (DoS) attacks
Why learn this
- Senior engineering interviews frequently ask how Hash Maps work 'under the hood', specifically demanding explanations of collision resolution strategies.
- It explains why inserting into a Hash Map is 'amortized' O(1): occasionally, the table gets too full, crosses a load factor threshold, and must undergo an expensive O(N) resize and rehash.
- Understanding the degradation of hash tables prepares you for real-world system failures.
Aha moment
# Python dictionaries double in size when they reach a 2/3 load factor.
initial_capacity = 8
items_inserted = 5
load_factor = 5 / 8 # 0.625. Getting close to 0.66!
# The 6th insertion triggers an O(N) resize.
# The dictionary creates a new array of size 16 and rehashes everything.Prediction: The dictionary will wait until it holds 8 items before resizing.
Common guess: Arrays resize when they are completely full.
Hash tables intentionally waste memory to buy speed. If a hash table waits until it is full to resize, the collision rate skyrockets and performance plummets. Resizing early guarantees that there is always empty space, keeping probes short and lookups O(1).
Common mistakes
- Believing good hash functions prevent collisions: No matter how perfect a hash function is, collisions are unavoidable if you put more items in the table than there are slots. Collisions are a structural reality, not a cryptographic failure.
- Assuming all languages handle collisions the same way: Java uses 'Separate Chaining' (linked lists/trees hanging off the array). Python uses 'Open Addressing' (jumping to a new empty slot in the array). The behaviors and performance tradeoffs are radically different.
Glossary
- Pigeonhole Principle
- A mathematical rule stating that if you have more items than containers, at least one container must hold multiple items.
- cryptographic failure
- A flaw where a security algorithm is broken or manipulated by an attacker.
- load factor threshold
- A specific fullness level that triggers a data structure to resize itself.
Recall questions
- What is a hash collision?
- What is the formula for the Load Factor of a hash table?
- What is the difference between Separate Chaining and Open Addressing?
Understanding checks
A malicious user realizes your web server uses a basic Hash Map for HTTP parameters. They send a single request with 10,000 parameters carefully crafted to all hash to the exact same bucket. If your language uses basic Separate Chaining, what happens to your server?
The server experiences a Denial of Service (DoS). The 10,000 parameters form a massive linked list in one bucket. Looking up parameters degrades to O(N) time, locking up the CPU.
This is a real-world 'Hash Flooding' attack. To fix this, Java 8 started upgrading long linked lists into Red-Black Trees (capping worst-case time at O(log N)), and Python added cryptographic salting to randomize hashes.
An open-addressed hash table has 10 slots and currently holds 9 elements. What happens to the performance of inserting the 10th element compared to inserting the 1st?
It will be catastrophically slow. The algorithm must probe almost the entire array, hitting 9 filled slots before finally finding the 1 empty slot.
Open addressing falls apart as the load factor approaches 1.0. This is why hash tables strictly monitor their load factor and automatically double their array size (rehashing) long before they actually get full.
Practice tasks
Preallocate capacity
If you know in advance that you are going to load exactly 1,000,000 records into a Java HashMap (which has a default load factor threshold of 0.75), what should you set the initial capacity to in order to avoid ANY expensive O(N) resizes?
Continue learning
Previous: Hash Tables