data structures - How java HashMap does chaining? how to access all collision values?

Question

I have read somewhere that HashMap uses chaining to resolve collisions. But if that is the case. how can i access all the elements with same key value.

For example :

HashMap<Integer, String> hmap = new HashMap<Integer, String>();
hmap.put(1, "1st value");
hmap.put(1, "2nd value");
hmap.put(1, "3rd value");
hmap.put(1, "4th value");

Now, if I do hmap.get(1) it returns “4th Value”

if Indeed it does chaining like

Key values 1 “4th Value” ---> “3rd Value”--->”2nd Value”----> “1st Value”

How can I get the other values?

hmap.get(1) only returns the 1st value.

My second question is,

if it does linear chaining. How can I remove any one value for a key. suppose I want to remove “4th value” from my hashmap and want to keep all other values for same key, how can i do it?

if I do

hmap.remove(1);

, it removes the complete chain.

Answer 1

HashMap cannot store multiple values for the same key.

Chaining is used to resolve hash collisions, i.e. situations when different keys have the same hash. So, it's not about storing multiple values with the same key, it's about multiple values whose keys have the same hashes.

Data structure that can store multiple values for the same key is called a multimap. Unfortunately, there is no built-in implementation of multimap in JRE.

If you need a multimap, you can maintain a Map of Lists (as suggested by matsev), or use an existing multimap implementation from a third-party library, such as Google Guava.

See also:

• Collision resolution