Java - HashMap confusion about collision handling and the get() method

Question

I'm using a HashMap and I haven't been able to get a straight answer on how the get() method works in the case of collisions.

Let's say n > 1 objects get placed in the same key. Are they stored in a LinkedList? Are they overwritten so that only the last object placed in that key exists there anymore? Are they using some other collision method?

If they are placed in a LinkedList, is there a way to retrieve that entire list? If not, is there some other built in map for Java in which I can do this?

For my purposes, separate chaining would be ideal, as if there are collisions, I need to be able to look through the list and get information about all the objects in it. What would be the best way to do this in Java?

Thanks for all your help!

Answer 1

The documentation for Hashmap.put() clearly states, "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"

If you would like to have a list of objects associated with a key, then store a list as the value.

Note that 'collision' generally refers to the internal working of the HashMap, where two keys have the same hash value, not the use of the same key for two different values.

Answer 2

collision resolution for hashing in java is not based on chaining. To my understanding, JDK uses double hashing which is one of the best way of open addressing. So there's no list going to be associated with a hash slot.

You might put the objects for which the hash function resolves to the same key can be put in list and this list can be updated in the table/map.

package hashing;

import java.util.HashMap;
import java.util.Map;

public class MainAnimal {

    /**
     * @param args
     */
    public static void main(String[] args) {

        Animal a1 = new Animal(1);
        Animal a2 = new Animal(2);

        Map<Animal, String> animalsMap = new HashMap<Animal, String>();

        animalsMap.put(a1,"1");
        animalsMap.put(a2,"2");

        System.out.println(animalsMap.get(a1));

        Map<String, Integer> map = new HashMap<String, Integer>();
        map.put("a", 1);
        map.put("a", 2);// it overrides 1 and puts 2 there

        System.out.println(map.get("a"));       

    }

}


class Animal {

    private int index = 0;

    Animal(int index){
        this.index = index;
    }

    public boolean equals(Object obj){
        if(obj instanceof Animal) {
            Animal animal = (Animal) obj;
            if(animal.getIndex()==this.getIndex())
                return true;
            else
                return false;
        }
        return false;
    }

    public int hashCode() {
        return 0;
    }

    public int getIndex() {
        return index;
    }

    public void setIndex(int index) {
        this.index = index;
    }


}

In the above code, am showing two different things.

case 1 - two different instances resolving to same hashkey case 2 - two same instances acting as keys for two different entries.

Animal instances, a1 & a2 resolves to same key. But they are not overriden. Hashing mechanism probes through the hash slots and places the entries on different slots.

with the second case, keys resolve to same hash key and also the equals method satisfies. Hence overriding happens.

Now if in the animal class I override the equals method this way -

    public boolean equals(Object obj){
//      if(obj instanceof Animal) {
//          Animal animal = (Animal) obj;
//          if(animal.getIndex()==this.getIndex())
//              return true;
//          else
//              return false;
//      }
//      return false;
        return true;
    }

Overriding happens. The behavior is like using same instance. Since a1 and a2 are in the same bucket and equals return true as well.

Answer 3

Cite: "Let's say n > 1 objects get placed in the same key. Are they stored in a linked list? Are they overwritten so that only the last object placed in that key exists there anymore? Are they using some other collision method?"

Yes, if the hashmap contained something under this key, it will override it.

You can implement your own class to handle that or more simple use a HashMap> in where K is your Key Object and V the object value. Have in mind that with last solution when you do a map.get(K) will retrieve a List or the implementation that you choose (i.e: ArrayList) so all the methods of this implementation are available for you and perhaps fulfils your requirements. For example if you used Arraylist you have the size, trimToSize, removeRange, etc.

Answer 4

Are they overwritten so that only the last object placed in that key exists there anymore?

Yes, assuming you're putting multiple values with the same key (according to Object.equals, not Object.hashCode.) That's specified in the Map.put javadoc:

If the map previously contained a mapping for the key, the old value is replaced by the specified value.

If you want to map a key to multiple values, you're probably better off using something like Guava's ListMultimap, ArrayListMultimap in specific, which maps keys to lists of values. (Disclosure: I contribute to Guava.) If you can't tolerate a third-party library, then really you have to have a Map<Key, List<Value>>, though that can get a bit unwieldy.

Answer 5

Let's say n > 1 objects get placed in the same key. Are they stored in a linked list? Are they overwritten so that only the last object placed in that key exists there anymore? Are they using some other collision method?

There could be single instance for the same key so the last one overrides the prior one

Map<String, Integer> map = new HashMap<String, Integer>();
map.put("a", 1);
map.put("a", 2);// it overrides 1 and puts 2 there

chaining comes where there turns the same hash for different keys

---

See

• Java papers hash table working