Course contentsShow
← Java
Lesson 1104 of 2,87026. Map ImplementationsFree lesson

Index Calculation: Hash to Bucket Mapping

The algorithm HashMap uses to convert a hash code into a valid array index using bitwise operations.

Index Calculation: Hash to Bucket Mapping

What you'll learn: How HashMap converts a hash code into a valid array index using efficient bitwise operations.

The Challenge

You've learned that hashCode() returns an integer that can be any value—positive, negative, or even Integer.MIN_VALUE. But HashMap's internal array has a fixed size (say, 16 buckets). How does HashMap transform an arbitrary hash code into a valid array index between 0 and 15?

The Naive Approach (and Why It's Not Used)

You might think: "Just use the modulo operator!" Something like index = hashCode % arrayLength. This works, but modulo division is relatively slow, especially when performed millions of times.

The Clever Solution: Bitwise AND

HashMap uses a bitwise trick that only works when the array length is a power of two (16, 32, 64, etc.):

index = (arrayLength - 1) & hash

Why this works: When arrayLength is 16, arrayLength - 1 equals 15, which in binary is 0000...001111 (four 1-bits). The bitwise AND operation (&) keeps only the lower bits of the hash code, effectively masking it to produce a value from 0 to 15.

Example

  • Hash code: 349527 (binary ends with ...010111)
  • Array length: 16
  • Mask: 16 - 1 = 15 (binary: 1111)
  • Result: 349527 & 15 = 7

The element goes into bucket 7.

Why Powers of Two Matter

This is why HashMap always maintains an array whose length is a power of two—it enables this ultra-fast index calculation using a single bitwise operation instead of expensive division.

Key Takeaway: HashMap converts hash codes to bucket indices using (arrayLength - 1) & hash, a bitwise AND operation that's much faster than modulo division and only works because HashMap keeps array sizes as powers of two.