Take the 2-minute tour ×

I am looking at the implementation of HashMap in Java and am stuck at one point.
How is the indexFor function calculated?

static int indexFor(int h, int length) {
   return h & (length-1);


share|improve this question
add comment

3 Answers

up vote 8 down vote accepted

It's not calculating the hash, it's calculating the bucket.


share|improve this answer
Can you please explain this calculation here ? –  gnreddy Jun 4 '12 at 9:48
Does this assume that length is a power of 2? –  LarsH Sep 14 '12 at 18:00
@LarsH Well, it would be far better if it was a power of 2, then you'd get a clean chop off of the high-order bits. As it happens, the implementation of HashMap starts with size 16 and does indeed multiply by two when resizing. It would still work if not a power of two, but you would want as many bits "on" as possible for length -1 to balance the spread between buckets –  Bohemian Sep 15 '12 at 2:07
add comment

The hash itself is calculated by the hashCode() method of the object you're trying to store.

What you see here is calculating the "bucket" to store the object based on the hash h. Ideally, to evade collisions, you would have the same number of buckets as is the maximum achievable value of h - but that could be too memory demanding. Therefore, you usually have a lower number of buckets with a danger of collisions.

If h is, say, 1000, but you only have 512 buckets in your underlying array, you need to know where to put the object. Usually, a mod operation on h would be enough, but that's too slow. Given the internal property of HashMap that the underlying array always has number of buckets equal to 2^n, the Sun's engineers could use the idea of h & (length-1), it does a bitwise AND with a number consisting of all 1's, practically reading only the n lowest bits of the hash (which is the same as doing h mod 2^n, only much faster).


     hash h: 11 1110 1000  -- (1000 in decimal)
   length l: 10 0000 0000  -- ( 512 in decimal)
      (l-1): 01 1111 1111  -- ( 511 in decimal - it will always be all ONEs)
h AND (l-1): 01 1110 1000  -- ( 448 in decimal which is a result of 1000 mod 512)
share|improve this answer
Does it make sense now, or should I elaborate more on the internals? –  Slanec Jun 4 '12 at 10:16
Very well explained. I'm impressed. –  Louis Wasserman Jun 4 '12 at 11:29
got it .... thanks –  gnreddy Jun 4 '12 at 11:39
I'm glad I could help. –  Slanec Jun 4 '12 at 11:50
Amazing explanation –  JavaDeveloper Oct 13 '13 at 20:08
add comment

It is calculating the bucket of the hash map where the entry (key-value pair) will be stored. The bucket id is hashvalue/buckets length.

A hash map consists of buckets; objects will be placed in these buckets based on the bucket id.

Any number of objects can actually fall into the same bucket based on their hash code / buckets length value. This is called a 'collision'.

If many objects fall into the same bucket, while searching their equals() method will be called to disambiguate.

The number of collisions is indirectly proportional to the bucket's length.

share|improve this answer
add comment

Your Answer


