indexFor in hashmap?

Question

Just trying to get my head around the workings of Java HashMap by looking at the code. When an element is added, the following happens:

1. the hashcode for key is got
2. a hash function is applied on the result
3. the method indexFor is applied on the result of 2. This gives the first entry in the appropriate bucket. The linked list in the bucket is then iterated over - the end is found and the element is added.

The implementation of indexOf is:

int indexOf(int h, int length) {
     return h & (length-1);
}

I can't understand the trick going on in the indexOf method. Can anyone explain it?

Thanks.

Answer 1

This works because Java HashMaps always have a capacity, i.e. number of buckets, as a power of 2. Let's work with a capacity of 256, which is 0x100, but it could work with any power of 2. Subtracting 1 from a power of 2 yields the exact bit mask needed to bitwise-and with the hash to get the proper bucket index, of range 0 to length - 1.

256 - 1 = 255
0x100 - 0x1 = 0xFF

E.g. a hash of 257 (0x101) gets bitwise-anded with 0xFF to yield a bucket number of 1.