aspose file tools*
The moose likes Beginning Java and the fly likes If two different objects have same hashcode, how HashMap will retrieve these two objects? Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of Java 8 in Action this week in the Java 8 forum!
JavaRanch » Java Forums » Java » Beginning Java
Bookmark "If two different objects have same hashcode, how HashMap will retrieve these two objects?" Watch "If two different objects have same hashcode, how HashMap will retrieve these two objects?" New topic
Author

If two different objects have same hashcode, how HashMap will retrieve these two objects?

agilemanoj kumar
Ranch Hand

Joined: Mar 07, 2008
Posts: 70
Hi,

I have weird question.

As we know, when we put key/value pair in hashmap, hashmap stores it using hashcode.
Suppose, Hashmap stores two different key/value pairs in it using same hashcode. When we call get method on these two different keys, what value will be returned from hashmap?

--
Thanks,
Manoj


Manoj Kumar
Unnar Björnsson
Ranch Hand

Joined: Apr 30, 2005
Posts: 164
You get the value associated with the key you supplied, even though the key/value pair share the same hashcode it doesn't mean that they are equal, although the reverse is true
agilemanoj kumar
Ranch Hand

Joined: Mar 07, 2008
Posts: 70
How will I get the value associated with the key?
Suppose, my code is written like below:

Hashmap hm = new Hashmap();
hm.put("a","aValue"); // Suppose hashcode created for key "a" is 209
hm.put("b","bValue"); // Here hashcode created for key "b" is 209 as well.

Now, I want to retrieve value associated to key "b". I will call hm.get("b"). Since, hashmap searches key/value pair based on hashcode of key. Hashmap will find 209 hashcode for key "b". Since, same hashcode is found for key "a", Hashmap may return value "aValue" instead of expected value "bValue".

So, here is my question, I want to retrieve value associated with key. How will I do that?
Note: I have flexibility to override hashcode, so that I can return same hashcode for two different keys.
Hunter McMillen
Ranch Hand

Joined: Mar 13, 2009
Posts: 492

well what values is it returning to you? A or B?

Hunter


"If the facts don't fit the theory, get new facts" --Albert Einstein
agilemanoj kumar
Ranch Hand

Joined: Mar 07, 2008
Posts: 70
Actually, I have never tried. I am just curious to know, how JVM will behave in such scenario?
Hunter McMillen
Ranch Hand

Joined: Mar 13, 2009
Posts: 492

I dont know, I have never encountered this issue, but If I did I would try it and see what the JVM did.

Hunter
Unnar Björnsson
Ranch Hand

Joined: Apr 30, 2005
Posts: 164
Hashmap hm = new Hashmap();
hm.put("a","aValue"); // Suppose hashcode created for key "a" is 209
hm.put("b","bValue"); // Here hashcode created for key "b" is 209 as well.


Remember that keys along with their associative values are stored in a linked list node in the bucket and the keys are essentially compared in hashmap using equals() method not by hashcode. If a.equals(b) returns true bValue will replace aValue and bValue will be returned, if a.equals(b) returns false another node will be created in the bucket list, so when you call get("b") you will get bValue since a.equals(b) is false.
Greg Charles
Sheriff

Joined: Oct 01, 2001
Posts: 2774
    
  10

When two unequal objects have the same hash value, this causes a collision in the hash table, because both objects want to be in the same slot (sometimes called a bucket). The hash algorithm must resolve such collisions. Reaching back into fading memories of my college algorithms course, I remember three basic ways of doing this:

1. Look for the next empty slot in the hash table and put the object there. Pros: easy to implement, cons: can lead to clustering of objects and degrade performance, capacity may be exceeded
2. Have a secondary hash function to use when there's a conflict: Pros: usually fast, cons: must write a second hash function and may still get collisions, and capacity may be exceeded
3. Make a linked-list of objects from the conflicted slot of the hash table. Pros/cons: usually fast for decent hash function and load factors, but can degrade to linear search in worst case

I think the Java hash classes use the third method, but they might use a combination approach. The key to good hashing though is to make sure the hash table has a big enough capacity and to write good hash functions. A hash table that only has as many buckets as objects it is holding will probably have conflicts. Usually you want the hash table to be about twice as big as the number of objects it stores. Java's HashMap will grow as needed, but you can give it a starting capacity and load factor if you want.

The hash function is up to the programmer. You could just return 0 for all objects, but that will mean the hashing (both storage and retrieval) will become O(n) instead of O(1) ... or in lay terms, it will be dog slow.
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: If two different objects have same hashcode, how HashMap will retrieve these two objects?
 
Similar Threads
About hascode()....
Overriding Hash()
equals() and hashCode()
Duplicate entries in HashSet
which Collection?