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

[agilemanoj kumar]

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

[Unnar Björnsson]

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]

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]

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

Hunter

[agilemanoj kumar]

Actually, I have never tried. I am just curious to know, how JVM will behave in such scenario?

[Hunter McMillen]

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]

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]

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.