This week's book giveaway is in the Servlets forum.
We're giving away four copies of Murach's Java Servlets and JSP and have Joel Murach on-line!
See this thread for details.
The moose likes Java in General and the fly likes HashMap Internal Working Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of Murach's Java Servlets and JSP this week in the Servlets forum!
JavaRanch » Java Forums » Java » Java in General
Bookmark "HashMap Internal Working " Watch "HashMap Internal Working " New topic
Author

HashMap Internal Working

Vaibhav G Garg
Ranch Hand

Joined: Sep 23, 2011
Posts: 140
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

Joined: Jan 03, 2004
Posts: 6109
    
    6

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

Joined: Sep 23, 2011
Posts: 140
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

Joined: Jan 03, 2004
Posts: 6109
    
    6

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

Joined: Sep 23, 2011
Posts: 140
Thanks Jeff. It clarifies the doubt.
Navnish Agarwal
Greenhorn

Joined: Feb 10, 2014
Posts: 3
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
Bartender

Joined: Sep 06, 2012
Posts: 1000
    
  16
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

Joined: Oct 13, 2005
Posts: 37907
    
  22
Afraid I found that link hard to read.
I see you are new: welcome to the Ranch
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: HashMap Internal Working
 
Similar Threads
how hashmap identify the duplicate values? (i need internal logic)
Online material on Hashcode and Equals method
Advice on building HashMap
Searching in a Map
Regarding hashcode method for String order