CODEWITHSUNDEEP
javadata-structurescollections
Rajesh Pantula
Rajesh Pantula

Reputation: 10241

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

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.

Upvotes: 7

Views: 19182

Answers (5)

Rishu
Rishu

Reputation: 11

If you store an existing key in the HashMap then it will override the old value with the new value and put() will return the old value

      System.out.println(hmap.put("1",1st value));
      System.out.println(hmap);  // o/p "1st value"

Upvotes: 0

axtavt
axtavt

Reputation: 242686

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:

Upvotes: 17

joschi
joschi

Reputation: 13101

You're obviously looking for a data structure like Guava's MultiMap which allows exactly what you want: Having multiple values per key.

Java's HashMap does not do chaining, as the documentation for put(K, V) clearly states:

public V put(K key, V value)

Associates the specified value with the specified key in this map. If the map previously contained a mapping for the key, the old value is replaced.

Upvotes: 0

hirikarate
hirikarate

Reputation: 3275

I don't think HashTable allows duplicate keys. You should read this What happens when a duplicate key is put into a HashMap?

Upvotes: 0

matsev
matsev

Reputation: 33759

From the documentation of HashMap.put(K, V):

Associates the specified value with the specified key in this map. If the map previously contained a mapping for the key, the old value is replaced.

What you can do is to put a List as your value, e.g.

HashMap<Integer, List<String>> hmap = new HashMap<Integer, List<String>>();
List<String> list = hmap.get(1);
if (list == null) {
    list = new ArrayList<String>();
    hmap.put(1, list);
}
list.add("1st value");
list.add("2nd value");
// etc

Upvotes: 3

Related Questions