• Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

HashMap Internal Working

 
Vaibhav G Garg
Ranch Hand
Posts: 143
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I am unable to understand the internal working of a Hashmap. I know that it uses hashcode() and equals methods to get the data from the hashmap.

Suppose we have a map with the following keys/values and their corresponding hashcodes:

1 => a hashcode = 3
2 => b hashcode = 5
3 => c hashcode = 3
4 => d hashcode = 2
5 => e hashcode = 2

Now, if I want to extract the value of keys 1&3 or keys 4&5, how it will get the corresponding values. Since both the hashcodes are similar so it can go to the bucket where the hashcode will be 3 or 2 respectively but how it will identify the exact key and corresponding value.
 
Jeff Verdegan
Bartender
Posts: 6109
6
Android IntelliJ IDE Java
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
The hashCode is used to determine which bucket to look in. Then it does a linear search on the elements in that bucket, using the equals() method to determine if each one matches. When it finds a match, that's the element we're seeking. If it gets to the end of the bucket without equals() returning true, then the element is not present.
 
Vaibhav G Garg
Ranch Hand
Posts: 143
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Jeff Verdegan wrote:The hashCode is used to determine which bucket to look in. Then it does a linear search on the elements in that bucket, using the equals() method to determine if each one matches. When it finds a match, that's the element we're seeking. If it gets to the end of the bucket without equals() returning true, then the element is not present.


Thanks Jeff! So, does it mean that the hashcode and equals methods are used for figuring out the exact match for KEY only. Once, we find out the KEY for the map, then how does it locate the value corresponding to that KEY?
 
Jeff Verdegan
Bartender
Posts: 6109
6
Android IntelliJ IDE Java
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Vaibhav G Garg wrote:
Jeff Verdegan wrote:The hashCode is used to determine which bucket to look in. Then it does a linear search on the elements in that bucket, using the equals() method to determine if each one matches. When it finds a match, that's the element we're seeking. If it gets to the end of the bucket without equals() returning true, then the element is not present.


Thanks Jeff! So, does it mean that the hashcode and equals methods are used for figuring out the exact match for KEY only.


Yes.

Once, we find out the KEY for the map, then how does it locate the value corresponding to that KEY?


Look at the docs for the interface Map.Entry. It's actually an Entry that's stored in the buckets, not just a key. The Entry wraps both key and value. It will be something like this:


When the map is searching for a key, it finds the right bucket, then for each Map.Entry in that bucket, it calss getKey() and looks at the hashCode and equals() for that key. If they match, then it call's that Entry's getValue() method to get the value.





 
Vaibhav G Garg
Ranch Hand
Posts: 143
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thanks Jeff. It clarifies the doubt.
 
Navnish Agarwal
Greenhorn
Posts: 3
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I think whatever doubt you have regarding how hashmap works in java are answered here http://javahungry.blogspot.com/2013/08/hashing-how-hash-map-works-in-java-or.html
 
Chan Ag
Rancher
Posts: 1089
14
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Navnish Agarwal wrote:I think whatever doubt you have regarding how hashmap works in java are answered here http://javahungry.blogspot.com/2013/08/hashing-how-hash-map-works-in-java-or.html


I think his questions are already answered. And I think this topic is already resolved.
 
Campbell Ritchie
Sheriff
Posts: 48652
56
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Afraid I found that link hard to read.
I see you are new: welcome to the Ranch
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic