CODEWITHSUNDEEP
javadictionary
Chethan
Chethan

Reputation: 311

Java - what is returned when two keys map to same value?

In Java, I understand if two keys maps to one value , linear chaining occurs due to collision.

For Example:

    Map myMap= new HashMap();   //Lets says both of them get mapped to same bucket-A and
    myMap.put("John", "Sydney");//linear chaining has occured.
    myMap.put("Mary","Mumbai"); //{key1=John}--->[val1=Sydney]--->[val2=Mumbai]

So when I do:

myMap.get("John");   // or myMap.get("Mary")

What does the JVM return since bucket-A contains two values? Does it return the ref to "chain"? Does it return "Sydney"? Or does it return "Mumbai"?

Upvotes: 1

Views: 4518

Answers (5)

pgras
pgras

Reputation: 12770

Looking at your example what confuses you is that you think values are chained for a given key. In fact Map.Entry objects are chained for a given hashcode. The hashCode of the key gives you the bucked, then you look at the chained entries to find the one with the equal key.

Upvotes: 0

Boris the Spider
Boris the Spider

Reputation: 61158

Your keys are different.

First some terminology

  • key: the first parameter in the put
  • value: the second parameter in the put
  • entry: an Object that holds both the key & the value

When you put into a HashMap the map will call hashCode() on the key and work out which hash bucket the entry needs to go into. If there is something in this bucket already then a LinkedList is formed of entries in the bucket.

When you get from a HashMap the map will call hashCode() on the key and work out which hash bucket to get the entry from. If there is more than one entry in the bucket the the map will walk along the LinkedList until it finds an entry with a key that equals() the key supplied.

A map will always return the Object tied to that key, the value from the entry. Map performance degrades rapidly if hashCode() returns the same (or similar) values for different keys.

You need to use java generics, so your code should really read

Map<String, String> myMap = new HashMap<String, String>();

This will tell the map that you want it to store String keys and values.

Upvotes: 1

Ajay George
Ajay George

Reputation: 11875

Linear chaining happens when your keys have the same hashcode and not when two keys map to one value.

So when I do: myMap.get("John"); // or myMap.get("Mary")

map.get("John") gives you Sydney

map.get("Mary") gives you Mumbai

What does the JVM return since bucket-A contains two values?

If the same bucket contains two values, then the equals method of the key is used to determine the correct value to return.

It is worthwhile mentioning the worst-case scenario of storing (K,V) pairs all having the same hashCode for Key. Your hashmap degrades to a linked list in that scenario.

Upvotes: 5

Perception
Perception

Reputation: 80603

The hashCode of your method determines what 'bucket' (aka list, aka 'linear chain') it will be put in. The equals method determines which object will actually be picked from the 'bucket', in the case of collision. This is why its important to properly implement both methods on all object you intend to store in any kind of hash map.

Upvotes: 4

Andres Olarte
Andres Olarte

Reputation: 4380

From my understanding, the Map first resolves the correct bucket (identified by the hashcode of the key). If there's more than one key in the same bucket, the equals method is used to find the right value in the bucket.

Upvotes: 0

Related Questions