How does HashMap compute a bucket index from a key, and why does it XOR the high bits of the hash?
answer
- index = (capacity - 1) & hash, works because capacity is pow2
- Mask keeps only low bits -> high bits ignored
- spread: h ^ (h >>> 16) folds high 16 bits into low 16
- x % 2^n == x & (2^n - 1) for non-negative x
- null key -> hash 0 -> bucket 0; one shift = speed/quality trade-off
basics
~20 sHashMap picks a bucket with (capacity - 1) & hash, a bitmask that works because capacity is a power of two. The mask reads only low bits, so hash() first XORs each hash with its own top 16 bits, which reduces collisions.
solid answer
~50 sBecause capacity is always a power of two, HashMap maps a hash to a bucket with the bitmask (capacity - 1) & hash: one AND, no division, and never a negative index, which Java's % could give for a negative hash. The catch: that mask keeps only the lowest bits of the hash, so two keys whose hashes differ only above the mask would collide. To reduce 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. That lets bits 16 and up change the index, though a small table reads only a few of them. It is a deliberate trade-off: one shift and one XOR, because many sets of hashes are already well distributed and tree bins handle large collisions. tableSizeFor keeps capacity a power of two by rounding any requested value up.
code
java · 18 linespublic class SpreadDemo {
// The same body as java.util.HashMap.hash at JDK 27
static int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
public static void main(String[] args) {
int n = 16; // current capacity, a power of two
int highBitsOnly = 3 << 16;
System.out.println((n - 1) & highBitsOnly); // 0: the raw mask ignores bit 16 and up
System.out.println((n - 1) & hash(highBitsOnly)); // 3: the spread brought those bits down
System.out.println((n - 1) & hash(null)); // 0: the null key
System.out.println(-17 % n); // -1: a modulo can go negative
System.out.println((n - 1) & -17); // 15: the mask cannot
}
}
go deeper
Knows the key is hashed to choose a bucket; details of the bitmask/spread are not expected.
Can state that the index uses a bitmask on a power-of-two capacity and that the hash is mixed before masking.
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.
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 `%` needs an integer division, and in Java its result can be negative when the dividend is, so a negative hash would give a negative index (`-17 % 16` is `-1`). HashMap keeps **capacity a power of two** instead. For a non-negative `x` the identity `x % 2^n == x & (2^n - 1)` holds, and for a negative `x` the mask still gives a valid index (`-17 & 15` is `15`). So it uses: ``` index = (capacity - 1) & hash ``` For capacity 16, `capacity - 1 = 15 = 0b1111`, so the `&` keeps the **lowest 4 bits** of the hash, with a single AND. (This is why capacity must be a power of two; `tableSizeFor` rounds any requested capacity up to one, and the resize split relies on the same property.) ## 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. Some sets of hashes vary only in those high bits, and the source says they "will always collide" without a fix; its example is `Float` keys holding consecutive whole numbers in small tables. ## 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 16 bits also carry the top 16, so bits above the mask can change the index that `(n-1) & hash` produces. The reach has a limit, because each low bit picks up just one high bit: at capacity 16 the index depends on bits 0-3 and 16-19 and on nothing else. Both sides show on JDK 27: - Hashes `i << 16` for `i` from 1 to 8 fill eight buckets of a 16-slot table, where the raw mask would put them all in bucket 0. - Hashes `i << 20` stay in bucket 0, because bits 20 and up do not reach the low 4 bits. - The `Float` keys 1.0 to 8.0 also stay in bucket 0 at capacity 16, and separate into six buckets at capacity 256. ## Why XOR, and why only one shift XOR is a cheap bit-mixing operation, and `h ^ (h >>> 16)` is reversible, so distinct hash codes stay distinct after it. HashMap deliberately does **just one** shift-and-XOR rather than a stronger hash function. The source comment describes a transform "that spreads the impact of higher bits downward", names a "tradeoff between speed, utility, and quality of bit-spreading", and gives two reasons for going cheap: many common sets of hashes "are already reasonably distributed", and "we use trees to handle large sets of collisions in bins". So it XORs "in the cheapest possible way to reduce systematic lossage". JDK 7's update line mixed harder, with several shifts and XORs. ## 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 reduce 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-negative x, and is still a valid index for a negative one. 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 lets those bits change the index, spreading many such keys across buckets, though a small table reads only a few of them.
- 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)
- Claiming the spread makes every bit of the hash affect the index at any table size
- HashMap one-XOR hash spreading
- Java 1.8
Assumes JDK 27; hash() has had this one-XOR form since Java 8 and reads the same at JDK 25. JDK 7's update line mixed with several shifts.
context
- Chapter 15. Expressionsdocs.oracle.com
- HashMap.java at jdk-27-gagithub.com