Map behaviour with duplicate key

Question

HashMap normally replace it value with latest one. But a article i read mentioned it as it keeps a linked list if duplicate values add.

Read the "What will happen if two different objects have same hashcode"

But i did not find even ConcurrentHashMap not maintain such a list?

What collection maintain duplicates in a list and if so how to identify the relevant object using get("key") method?

Are you asking how to store multiple values for one key, or how to resolve hash collisions in a hash based map? — jlordo, Jan 17 '13 at 09:58
in `HashMap` the `key` elements are divided into groups called bucket (for example, initially 16 buckets). Elements in the same bucket have some common in their hashcode (simplified, but imagine that the last 4 bits are the same). So, you can see that many keys may exist in the same bucket. If you want to find a value, you select the bucket based on the hashcode of the Key, the iterate through the elements. When two keys have the same hashcode, then `equals()` is called to check the exact match. If no match, two different entries will be stored, otherwise it will overwrite the value. — gaborsch, Jan 17 '13 at 10:53
So that bucket which having multiple object will store it as a linked list right? — FrankD, Jan 17 '13 at 11:40
Also both key object and value object store as an Entry object in that bucket right? So that bucket is a collection of Entry objects right? List — FrankD, Jan 17 '13 at 11:42
Yes, that's true. Actually Entry objects refer to each other, always pointing to the next Entry (or null if no more elements in the chain) — gaborsch, Jan 17 '13 at 14:03

score 2 · Accepted Answer · edited May 23 '17 at 10:24

The "List" is actually a re-implementation of linked list object structure. This is the Entry class what HashMap uses to store the keys and values:

static class Entry<K,V> implements Map.Entry<K,V> {
    final K key;
    V value;
    Entry<K,V> next;  <-- This one refers to the next element
    int hash
..
}

So, there is no explicit implementation of LinkedList.

The article was discussing what will happen is two keys have the same hashcode. Then it will store both key-value pairs, of course. If the two keys are equal() to each other, then it will replace the value.

How HashMap works in details: see my answer on this question: Best practices on what should be key in a hashtable

score 1 · Answer 2 · answered Jan 17 '13 at 10:06

Here's how hashmaps (generally) work:

Hashmaps keep a collection of buckets in which to put things. When you insert something, a hash function is applied to the key you're inserting on. The resulting "hash" dictates which bucket to put your data in. It's possible for two different keys to hash to the same bucket. This means that when you insert the second item that hashes to bucket 10, for example, the java implementation must add your new item to the end of the linked list that keeps track of items in bucket 10.

Just because two items are stored in the same bucket (linked list) doesn't mean they have the same key. It just means their keys happen to hash to the same value (or equivalent values modulo the number of hash buckets, to be precise).

score 0 · Answer 3 · edited May 23 '17 at 10:24

0

The "concurrent" in ConcurrentHashMap refers to thread-safety, and has nothing to do with storing multiple values for one key.

You can probably find solutions for your problem here: HashMap with multiple values under the same key

edited May 23 '17 at 10:24

Community

1
1

answered Jan 17 '13 at 10:08

Cephalopod

14,632
7
51
70

score 0 · Answer 4 · answered Jan 17 '13 at 10:20

0

enter image description here

Here as you can see the array is the hashcodes, if two objects A2 and B2 have same hashcodes then they are added to the same bucket.

But if objects A2 and A3 have same hashcode and return true on equals() then the object A2 will be replaced by A3.

answered Jan 17 '13 at 10:20

Narendra Pathai

41,187
18
82
120

Map behaviour with duplicate key

4 Answers4