Primary and Secondary Clustering Effects
What You'll Learn
You'll understand how clustering patterns differ between linear probing and other open addressing methods, and why they impact hash table performance.
The Clustering Problem
When collisions occur in open addressing, clustering happens: occupied slots group together, making future insertions slower because they must probe through longer chains of filled slots.
There are two types:
Primary Clustering (Linear Probing's Weakness)
Primary clustering occurs in linear probing when consecutive occupied slots form long "runs." Because linear probing checks the next slot (h(k) + 1, h(k) + 2, etc.), any collision within or near a cluster extends it further.
Analogy: Imagine a parking lot where everyone parks in the next available spot moving right. Once a busy section forms, it grows faster because everyone who hashes near it gets stuck probing through the entire jam.
Effect: Keys with different hash values end up competing for the same probe sequence, exponentially degrading performance as load factor increases.
Secondary Clustering (Quadratic Probing's Issue)
Secondary clustering is subtler. In quadratic probing and early versions of double hashing, keys that hash to the same initial position follow the same probe sequence.
Analogy: Multiple cars arrive at the same full parking spot. They all follow the identical backup route (spots +1², +2², +3²...), creating a smaller, pattern-based cluster.
Effect: Better than primary clustering because keys with different hash values don't interfere, but keys with the same hash still collide repeatedly.
Double Hashing: The Solution
Proper double hashing uses a second hash function to vary the probe step size per key, so even keys hashing to the same slot follow different probe paths, essentially eliminating secondary clustering.
Key Takeaway: Primary clustering (linear probing) causes large consecutive runs where any nearby hash creates interference; secondary clustering (quadratic probing) creates smaller, pattern-based clusters for keys sharing the same initial hash; double hashing avoids both by personalizing each key's probe sequence.