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.