How does the add method in HashMap determine where a key goes in a HashMap? Like, if I was trying to put "S","T","A","C","K" into the HashMap of size 10, how does it determine where each letter goes?
Asked
Active
Viewed 147 times
1
-
Object's `hashCode()` method – Sotirios Delimanolis Apr 03 '13 at 18:08
-
1It hashes it. I'm pretty sure that if you Google for it you'll find a good Wikipedia article or three on hashtables, et al. – Hot Licks Apr 03 '13 at 18:10
-
disagree that the content in the previous question is a satisfactory answer to this question. – Affe Apr 03 '13 at 18:30
1 Answers
4
The least significant bits of the object's hash code are used to select a bucket. Note there is no such thing as a java.util.HashMap of size 10, the size must be a power of 2 so that the bits can be masked to choose a bucket. If you pass 10 to the constructor, you will get a HashMap with 16 buckets back.
So, reducing to 8 bits for clarity, if "S" returns hashcode 123 java will do
01111011 & 00001111 -> 00001011
and put S in bucket 11.
The real Hash Map also applies a secondary hash function that shifts bits rightward to make sure there is data with some entropy in the least significant bits so that things have a good chance of being distributed evenly even if their hashCode function isn't that great.
Affe
- 47,174
- 11
- 83
- 83