Why Java HashMap Uses (n - 1) & hash Instead of % n

If you’ve ever dug into HashMap internals, one line probably stood out:

int index = (n - 1) & hash;

At first glance, it looks like a cryptic optimization compared to the more obvious:

int index = hash % n;

Why does Java choose bitwise AND over modulo?

This isn’t just about micro-optimization. It influences how HashMap is designed, how it resizes, and even how hash collisions are handled.

Let’s break it down.

The Problem: Mapping a Hash to an Array Index

A HashMap internally stores entries in an array:

table[0 ... n-1]

Given a key, we compute its hash and convert that hash into a valid array index. That means we need a function:

hash → [0, n-1]

Two obvious choices:

• hash % n
• (n - 1) & hash

When Are They Equivalent?

They produce the same result only when n is a power of 2.

n = 16  → 10000
n - 1 = 15 → 01111

Now:

hash % 16

is equivalent to:

hash & 0b1111

So effectively:

hash % 16 == hash & (16 - 1)

Why?

Because modulo with powers of two depends entirely on the lower bits, and bit masking extracts exactly those bits.

Why HashMap Uses (n - 1) & hash

1. It’s Faster

• % involves division → relatively slow
• & is a single CPU instruction → very fast

Since this runs on every get and put, this adds up significantly.

2. It Enforces a Smart Capacity Rule

HashMap always keeps capacity as a power of 2:

16, 32, 64, 128, ...

This is not random — it’s required for the bitmask trick to work correctly.

3. It Makes Resizing Extremely Efficient

This is the real reason. When resizing:

old capacity = n
new capacity = 2n

With modulo:

newIndex = hash % (2n)

→ Full recomputation required

With bitmask:

oldIndex = hash & (n - 1)
newIndex = hash & (2n - 1)

Only one extra bit gets considered.

So each entry either:

• stays in the same bucket
• OR moves to index + oldCapacity

This allows bucket splitting instead of full rehashing.

Example: Resize in Action

Assume:

old capacity = 16
new capacity = 32

Masks:

old mask = 01111
new mask = 11111

Take a hash:

hash = 10110110

Old index:

10110110
&00001111
---------
00000110 = 6

New index:

10110110
&00011111
---------
00010110 = 22

Notice:

22 = 6 + 16

So the entry either stays at 6 or moves to 22. No full recomputation. Just a simple decision.

The Tradeoff: Only Lower Bits Are Used

Bitmasking only uses lower bits of the hash. If your hash function is weak in lower bits, distribution breaks. Example bad pattern:

xxxxxxx0000

→ many keys collide into the same buckets

How Java Fixes This

Java applies a hash spreading step:

h ^ (h >>> 16)

This mixes high bits → into low bits

Result: better distribution and fewer collisions

Why Not Just Use %?

The merit of using % would will use full hash value plus that is less sensitive to poor lower bits. The problem is they are slower, no resize optimization and full rehashing isrequired

In practice, the performance and scaling wins of & outweigh the benefits of %.

Why Power-of-2 Capacity Matters

Bitmasking only works correctly when:

n = 2^k

Because:

(n - 1) gives a clean mask of k bits

Otherwise:

hash & (n - 1)

would produce uneven distribution.

Mental Model is that Think of it like this:

• % n → “fit value into range mathematically”
• & (n - 1) → “take the last k bits”

Where:

n = 2^k

So instead of doing division, we just say:

The last k bits decide the bucket.

Real-World Takeaways

• HashMap size is always a power of 2 for this optimization
• (n - 1) & hash is faster than % n
• It enables efficient resizing without full rehashing
• Good hash distribution is still critical
• Hash spreading is essential to avoid clustering

One-Line Summary

*(n - 1) & hash is a bitwise optimization of % n that only works when n is a power of two, making HashMap faster and enabling efficient resizing.*