Hash Spreading: Secondary Hashing
What you'll learn: How HashMap applies an additional transformation to hashCode() values to distribute keys more evenly across buckets.
The Problem with Raw Hash Codes
In the previous lesson, you saw how HashMap uses hashCode() % array.length to map keys to bucket indices. However, Java's HashMap doesn't actually use the raw hashCode() directly—it applies secondary hashing (also called hash spreading) first.
Why? Because many objects produce hash codes that cluster in certain patterns. For example, consecutive Integer objects have consecutive hash codes (1, 2, 3...). When you mod these by the array length, you might get poor distribution, leaving some buckets empty while others overflow.
How Hash Spreading Works
Before calculating the bucket index, HashMap passes your key's hashCode() through an additional bit-manipulation function that "spreads" the bits around. This mixing process takes patterns in the original hash code and redistributes them more uniformly.
Think of it like shuffling cards: even if the original hash codes are sequential (like a sorted deck), the secondary hash scrambles them so they land in different buckets (like a well-shuffled deck).
The exact bit operations involve XOR shifts that move high-order bits down to influence the low-order bits—the ones that matter most when calculating index = hash % arrayLength.
Why This Matters
Without hash spreading, even well-intentioned hashCode() implementations can lead to clustering, causing multiple keys to pile into the same bucket. This degrades HashMap's O(1) performance toward O(n) as buckets become long chains.
Key Takeaway: HashMap applies secondary hashing to your key's hashCode() value before mapping it to a bucket index, ensuring more uniform distribution and better performance even when hash codes have patterns.