8

Please describe the reason if you know. I Googled it, but didn't find well explained answers.

Is it for making index of bucket positive when your hashCode is negative?

Eran
  • 387,369
  • 54
  • 702
  • 768
niiraj874u
  • 2,180
  • 1
  • 12
  • 19

1 Answers1

9

For HashMap, the index in the array that stores the entries of the Map is calculated this way (where h is calculated from the hashCode of the key):

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

Where length is the length of the array.

This only works when length is a power of 2. If length wasn't power of 2, you would have to change this code to the less efficient return h % length.

Eran
  • 387,369
  • 54
  • 702
  • 768
  • @w00te The code of HashMap is available. You just have to look at the code. – Eran Dec 02 '14 at 14:17
  • @w00te Here's one place you can read the code - http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/6-b14/java/util/HashMap.java – Eran Dec 02 '14 at 14:18
  • What is wrong if I don't take size as power of two ? What is the benefit of having power of two ? – niiraj874u Dec 02 '14 at 14:20
  • @Eran Thanks; I'm surprised it was so well commented in the JDK code :) – John Humphreys Dec 02 '14 at 14:22
  • @niiraj874u If you specify an initial HashMap capacity that is not a power of 2, HashMap would change the capacity to the closest power of 2 higher than the capacity you specified. The code above only works when `length` is power of 2. – Eran Dec 02 '14 at 14:23
  • @Eran, Thanks for your response. My question is why author of HashMap has decided to keep it power of 2 ? Can you explain me this by some example ? – niiraj874u Dec 02 '14 at 14:29
  • @niiraj874u bit-wise and operator (`&`) is faster than modulus operator (`%`). That's it. – Eran Dec 02 '14 at 14:31
  • But why we take length 16 why not 15 or 20 ? – niiraj874u Dec 02 '14 at 14:48
  • @niiraj874u 15 and 20 are not powers of 2. – Eran Dec 02 '14 at 15:06
  • `&` is faster than `%`, but they're equivalent -- _only_ for powers of two. So using power-of-two table sizes allows you to use `&` instead of `%`, which is faster. – Louis Wasserman Dec 02 '14 at 19:42
  • But why then is `HashTable` different – Raedwald Dec 03 '14 at 11:07
  • @Raedwald HashTable is older than HashMap, and is probably less efficient. I don't know why they chose 11 as the initial capacity, but HashTable class doesn't contain the code that requires a power of two. – Eran Dec 03 '14 at 11:13