HashMap Hash Spreading

Java HashMap mixes higher hash-code bits into lower bits so that bucket selection uses more information from the key's hash. This helps distribute keys more evenly when the table uses a power-of-two capacity.

A Java `HashMap` first obtains a key's hash code and then applies a spreading operation before choosing a bucket. In the common implementation, the spread value is `h ^ (h >>> 16)`, which combines the upper 16 bits with the lower 16 bits.

Bucket selection can then use a bit mask such as `(n - 1) & hash` when the table length `n` is a power of two. Because this mask primarily examines the low-order bits, spreading moves some information from higher bits into positions that affect the bucket index.

Without spreading, two hash codes that differ mainly in their upper bits can select the same bucket when their relevant low bits are identical. Spreading does not make poor hash functions good, but it can reduce this particular source of clustering.

The operation is inexpensive: it uses a right shift and XOR rather than computing a completely new hash. The exact implementation is an implementation detail of the Java version, so interview answers should distinguish the general idea from a particular JDK implementation.

Key points

• Hash spreading mixes high hash bits into low bits.
• A common Java `HashMap` spread operation is `h ^ (h >>> 16)`.
• Power-of-two table sizes make low hash bits especially important for bucket selection.
• Spreading can reduce collisions caused by hash codes differing mainly in higher bits.
• Spreading cannot compensate for a fundamentally poor or highly colliding `hashCode()` implementation.

Interview questions

What does `h ^ (h >>> 16)` do?

It takes the hash value `h`, shifts it right by 16 bits without sign extension, and XORs that shifted value with the original. The shifted high bits therefore affect positions in the lower half of the result. This is useful because those lower positions can influence bucket selection. It is a cheap mixing operation rather than a full rehash.

Why does HashMap need hash spreading?

HashMap bucket selection can depend heavily on the low-order bits of a hash value when the table length is a power of two. If a key type produces hashes whose useful variation is concentrated in higher bits, different keys may cluster into the same buckets. Hash spreading mixes some higher-bit information into lower bits before bucket selection. This can improve distribution without requiring an expensive new hash function.

How does hash spreading relate to bucket selection?

For a table whose length is a power of two, a common bucket-index calculation is based on `(n - 1) & hash`. The mask selects particular low-order bits of the hash. Hash spreading first incorporates information from higher bits into those positions, so variation that would otherwise be ignored can influence the selected bucket. This can reduce avoidable clustering.

Does hash spreading prevent collisions?

No. Hash spreading can reduce certain patterns of clustering, but it cannot guarantee unique bucket assignments. Multiple keys can still have the same hash code or can produce spread values that select the same bucket. HashMap handles such collisions using its collision-resolution mechanisms. The quality of the key's `hashCode()` remains important.