Why HashMap Uses (n - 1) & hash and Why Capacity Is Always Power of 2

If you are learning Java HashMap internals, one line that often confuses beginners is:

index = (n - 1) & hash;

Many people ask:

• Where is the power of 2 here?

• Why not use % (modulo)?

• Why does HashMap care so much about powers of 2?

In this article, we’ll explain everything in very simple terms.

---

What Is n in (n - 1) & hash?

In this formula:

index = (n - 1) & hash;

n is the capacity of the HashMap, meaning the number of buckets.

Important rule:

HashMap capacity is ALWAYS a power of 2

Examples:

• 16 → 2⁴

• 32 → 2⁵

• 64 → 2⁶

• 128 → 2⁷

So the power of 2 is hidden inside n.

---

Why HashMap Capacity Must Be Power of 2

HashMap calculates bucket index using bitwise AND (&), not modulo (%).

This works correctly only when n is a power of 2.

Let’s understand this with an example.

---

Example: Capacity = 16 (Power of 2)

Binary values:

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

Now suppose the hash value is:

hash = 10110101

Apply bitwise AND:

  10110101
& 01111
-----------
  00101  → index = 5

What happened here?

• (n - 1) created a bitmask

• The bitmask ensures the index is always between 0 and 15

• Every bucket gets a fair chance to be used

This is fast and efficient.

---

What If Capacity Is NOT Power of 2? (Important Interview Trap)

Suppose:

n = 10
n - 1 = 9 → 1001

Now:

hash = 10110101
& 1001
-------
 1001 → index = 9

Problems:

• Many bucket indexes are never used

• Keys cluster in fewer buckets

• Collisions increase

• Performance degrades

That’s why HashMap never allows non-power-of-2 capacity internally.

---

Why HashMap Does NOT Use % (Modulo)

You may wonder:

index = hash % n;

Why not use this?

Reasons HashMap avoids modulo:

1. % is slower than bitwise operations

2. & is much faster at CPU level

3. Power-of-2 capacity makes modulo unnecessary

4. Better performance under heavy load

Interview answer:

HashMap avoids modulo and uses bitwise AND for faster index calculation.

---

What If We Pass Any Capacity Manually?

Example:

new HashMap<>(20);

Internally:

• HashMap converts 20 to 32

• Nearest power of 2 is used

So actual internal capacity becomes:

32

This is done automatically.

Interview point:

HashMap internally adjusts capacity to the nearest power of 2.

---

How This Reduces Collisions

HashMap also improves hash distribution using this step:

hash = h ^ (h >>> 16);

Together with:

index = (n - 1) & hash;

This ensures:

• Even distribution of keys

• Better use of all buckets

• Fewer collisions

• Faster get() and put() operations

---

Final Interview-Ready Explanation

You can say this confidently in interviews:

HashMap capacity is always a power of 2.
Because of that, HashMap uses (n - 1) & hash instead of modulo to calculate bucket index.
This is faster and ensures uniform key distribution.

---

One-Line Summary

Power of 2 → Bitmask → Fast index calculation → Fewer collisions