indexFor in hashmap?
hashmap, java
Solution
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.
Problem
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: - the hashcode for key is got - a hash function is applied on the result - 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.