• Post Reply Bookmark Topic Watch Topic
  • New Topic

How does HashMap locate the correct value when multiple values are in the same bucket?  RSS feed

 
Faz Ali
Greenhorn
Posts: 21
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi All,

From what i've learned so far HashMap maps key/value pairs and uses the hashCode() of the key to determine how to store the value. Therefore if the hashCode is pooly implemented (code example of a poor one is below), this allows for the possibility of multiple values landing in the same bucket (if they have the same hashCode).
The above makes perfect sense but the part I don't understand is, if there are multiple items in a bucket, how does the HashMap return the element associated with supplied key when searching through this one bucket contianing multiple items. - How does it know what it's looking for?
From what I've read it uses the equals() method but on what? - The only thing I can think of is both the key/value pair being stored in the bucket as opposed to just the value but I am unsure if this is the case. Confirmation on this would be great.

The following code demonstrates my example of having multiple items in same bucket yet the HashMap returns the correct value:

 
Paul Clapham
Sheriff
Posts: 22509
43
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Each bucket contains a set of keys, so when the Map implementation is looking through the bucket, it's looking for whatever key was given to it. Or more precisely, it's looking for an object which is equal to the key it was given. That's why your key objects have to implement equals() correctly.
 
Paul Clapham
Sheriff
Posts: 22509
43
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
By the way: the code

can be expressed more concisely like this:
 
Campbell Ritchie
Marshal
Posts: 55772
163
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
. . . and beware: the instanceof keyword is only reliable in the equals() method when you are in a final class. I would suggest this
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!