CODEWITHSUNDEEP
javacollections
hitesh
hitesh

Reputation: 378

How map enters the duplicate key internally?

I am quite confused , when map encounters duplicate key - it enters the same bucket so do it check for the same key and replace with new value .

And what happens when different key with same bucket is inserted.

Does it checks for key and where does it store its key?

Upvotes: 0

Views: 102

Answers (4)

arshajii
arshajii

Reputation: 129517

I'm assuming you're talking about HashMap. Let's look at the source:

386     public V put(K key, V value) {
387         if (key == null)
388             return putForNullKey(value);
389         int hash = hash(key.hashCode());
390         int i = indexFor(hash, table.length);
391         for (Entry<K,V> e = table[i]; e != null; e = e.next) {
392             Object k;
393             if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
394                 V oldValue = e.value;
395                 e.value = value;
396                 e.recordAccess(this);
397                 return oldValue;
398             }
399         }
400 
401         modCount++;
402         addEntry(hash, key, value, i);
403         return null;
404     }

So what's happening here is that the put() method hashes the key and visits the corresponding bucket. It then loops over the entries1 contained there and, if it finds an entry whose key equals the given key, it replaces that entry's value with the given value, i.e.:

if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
    V oldValue = e.value;
    e.value = value;
    e.recordAccess(this);
    return oldValue;
}

If no such entry is found, we just add a new entry to the bucket normally, i.e.:

modCount++;
addEntry(hash, key, value, i);
return null;

1 Entry is the class that contains the key-value pair.

Upvotes: 2

Kakarot
Kakarot

Reputation: 4252

A map does not allow duplicate keys. If an element with the same key is inserted the Old value will be replaced with the new one.

For example : Say my map is as follows : 

Key     Value   Bucket
A       Val1    1
B       Val2    2
C       Val3    1

Bucket Structure : 

Bucket 1 :  A -> C
Bucket 2 :  B

When someone tries to enter another element (C, Val6) where C is the key; then the map structure will be as follows after insertion : 

Key     Value   Bucket
A       Val1    1
B       Val2    2
C       Val6    1

So the Value is replaced in the Map.

Bucket Structure : 

Bucket 1 :  A -> C
Bucket 2 :  B

Now to address the second part of your question : When different key with the same value is entered in the same bucket it is just added to the bucket (Internally each bucket might be like a ArrayList where elements are added at the end of the list).

For example : Lets assume we are adding the following pair (D, Val 7)to the above Map and assume the Key D maps to bucket 1. Then the map structure will be as follows after the insertion : 

 Key     Value   Bucket
 A       Val1    1
 B       Val2    2
 C       Val6    1
 D       Val7    1

Bucket Structure : 

Bucket 1 :  A -> C -> D
Bucket 2 :  B

Upvotes: 1

erickson
erickson

Reputation: 269737

A HashMap "bucket" is a linked list. Each element of the list contains the key, the value, the hash of the key and a pointer to the next element in the list.

So, when a hash collision occurs, the hash table iterates over each entry in the bucket. It compares entry hash to the insertion key hash, and the entry key to the insertion key. If they are both equal, it replaces the value. If it gets through the whole bucket without a match, it adds an entry to the bucket.

Upvotes: 0

ucsunil
ucsunil

Reputation: 7494

When a duplicate key is entered, it simply replaces the value of the previous key with the new value. When a different key is entered into the same bucket, it first checks to see if this is a duplicate and if it's not, then it adds the key and it's corresponding value.

Upvotes: 0

Related Questions