skip to content

How does HashMap compute a bucket index from a key, and why does it XOR the high bits of the hash?

level: seniorimportance: should knowfreq 50%

answer

  1. index = (capacity - 1) & hash, works because capacity is pow2
  2. Mask keeps only low bits -> high bits ignored
  3. spread: h ^ (h >>> 16) folds high 16 bits into low 16
  4. x % 2^n == x & (2^n - 1) (bitmask faster than modulo)
  5. null key -> hash 0 -> bucket 0; one shift = speed/quality trade-off

basics

~20 s

HashMap picks a bucket with (capacity - 1) & hash, a fast bitmask that works because capacity is a power of two. But that mask only looks at the low bits, so HashMap first mixes each key's high bits down by XOR-ing hash with (hash >>> 16). This spreads keys more evenly and avoids clustering.

solid answer

~50 s

Because capacity is always a power of two, HashMap maps a hash to a bucket with the bitmask (capacity - 1) & hash instead of a modulo, which is faster. The catch: that mask keeps only the lowest bits of the hash, so two keys whose hashes differ only in high bits would collide. To fix this, HashMap applies a spreading function: static int hash(Object key) returns key.hashCode() ^ (h >>> 16), XOR-ing the top 16 bits into the bottom 16. This cheaply folds high-bit entropy into the low bits that the mask actually uses, reducing collisions for hashCodes that vary mostly in their upper bits. It is a deliberate trade-off: one shift and one XOR, accepting slightly imperfect spreading in exchange for speed. The whole scheme depends on capacity being a power of two, which is why tableSizeFor rounds any requested capacity up to one.

code

java · 9 lines
java
// Simplified from java.util.HashMap (Java 8+)
static final int hash(Object key) {
    int h;
    // XOR the high 16 bits into the low 16 bits (the ones the index mask reads)
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

// Choosing the bucket (n = current capacity, a power of two):
// int index = (n - 1) & hash(key);   // bitmask == modulo for powers of two, but faster

go deeper

for a junior

Knows the key is hashed to choose a bucket; details of the bitmask/spread are not expected.

for a middle

Can state that the index uses a bitmask on a power-of-two capacity and that the hash is mixed before masking.

for a senior

Explains (n-1)&hash vs modulo, the power-of-two requirement, and exactly why h ^ (h>>>16) folds high bits into the low bits the mask uses.

for a principal

Discusses the speed/quality trade-off of the single-step spread, implications for custom hashCode quality, and how poor hashes interact with the masking scheme.

## The goal: turn a 32-bit hash into a bucket index A key's `hashCode()` is a 32-bit `int` (about 4 billion possible values). The table has only `capacity` buckets (e.g. 16). HashMap must fold the big hash down to a valid index in `0..capacity-1`. ## Why a bitmask instead of modulo The obvious way is `hash % capacity`. But `%` (integer division) is relatively slow. HashMap keeps **capacity a power of two**, and for powers of two the identity `x % 2^n == x & (2^n - 1)` holds. So it uses: ``` index = (capacity - 1) & hash ``` For capacity 16, `capacity - 1 = 15 = 0b1111`, so the `&` keeps the **lowest 4 bits** of the hash. This is a single fast AND instruction. (This is also the whole reason capacity must be a power of two; `tableSizeFor` rounds any requested capacity up to the next one.) ## The problem: the mask ignores high bits Because the mask keeps only the low bits, any difference in the **high** bits of two hashes is thrown away when choosing a bucket. Many real hashCode implementations vary mostly in their high bits (or have patterned low bits). With a small table, such keys would all collide into the same few buckets — defeating the point of hashing. ## The fix: the spread (perturbation) function Before masking, HashMap mixes the hash: ``` static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); } ``` - `h >>> 16` is an **unsigned right shift** by 16, moving the top 16 bits down into the bottom 16 positions (filling the top with zeros). - `h ^ (h >>> 16)` **XORs** those high bits into the low bits. Now the low bits — the ones the mask `(n-1) & hash` actually reads — carry information from the entire 32-bit hash, not just the original low half. Two keys that differ only in high bits will now usually differ in low bits too, so they spread across buckets instead of clustering. ## Why XOR, and why only one shift XOR is a cheap, reversible bit-mixing operation that combines both halves' entropy without bias. HashMap deliberately does **just one** shift-and-XOR rather than a stronger hash function: it is a speed/quality compromise. A perfect avalanche mix would cost more cycles than it is worth, given that most `hashCode()`s are already reasonable and the load factor keeps buckets short. The comment in the JDK source calls it spreading the impact of higher bits downward with a bounded cost. ## The null key Note `key == null` returns hash `0`, so the null key always maps to bucket index 0. ## Putting it together ``` spread = h ^ (h >>> 16); index = (capacity - 1) & spread; ``` This pairing — power-of-two capacity enabling a bitmask, plus a one-step high-bit spread to compensate for the mask's blindness to high bits — is the core of HashMap's fast, reasonably-uniform indexing.

  • Why must capacity be a power of two for (capacity-1)&hash to work as a modulo?
    For a power of two 2^n, the value 2^n - 1 is a mask of n low 1-bits, and x & (2^n - 1) equals x % 2^n. For non-powers-of-two the AND would not cover a contiguous range of indices, causing gaps and uneven distribution.
  • What problem does h ^ (h >>> 16) specifically address?
    The index mask only reads the low bits, so hashes differing only in high bits would collide. XOR-ing the high 16 bits into the low 16 makes the low bits reflect the whole hash, spreading such keys across buckets.

saying these in an interview costs you the question

  • Saying HashMap uses hashCode() % capacity (it uses the & bitmask)
  • Forgetting the spread step and claiming raw hashCode picks the bucket
  • Thinking the spread is a full cryptographic mix (it is one shift + XOR)
  • Not realizing the bitmask trick requires power-of-two capacity
  • Saying >>> is signed shift (it is unsigned, zero-filled)

context

resolving links…