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:

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:

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s