HashMap Java example to avoid collision

Question

I am using HashMap in java to store key and Object <Key,Object>. And I read about hashmap collision and I am trying to avoid it by using linked list.

I did some search online, but I couldn't find an example how to do this.

Can somebody point me to an online resources that implement the hashmap with linked list?

Solution 1

The Java HashMap already handles collisions for you in this way. All you need to do is ensure you are overriding and implementing the key's hashCode() and equals() method.

Each hash code will map to a specific "bucket". Each bucket contains a linked list for the case of collisions.

The only way to avoid (or rather minimize) collisions is to create a hash function that creates the best possible distribution of values throughout the HashMap. Depending on the density of your HashMap and the quality of your hash code, collisions are almost inevitable, hence the need to override the two methods.

Edit: The OP asked for an example

To override the two methods:

public class MyObject {
  String var1;
  int var2;

  //...
  public boolean equals(Object obj) {
    if(obj == null) return false;
    if(this == obj) return true;      // Reference equality
    if(!(obj instanceof MyObject)) return false;
    MyObject myObj = MyObject(obj);
    return (var1.equals(myObj.var1)) && (var2 == myObj.var2); 
  }
  public int hashCode {
     return var1.hashCode() ^ var2;
  }
}

Solution 2

The collision only occurs if you use the same object as key, or different object as keys with the same hash code and equals.

For using correctly a HashMap, you should implement correctly in your key class the hashCode and equals method. Read the Object docs and this article.

If you want to store more than one object by key, you should create a HashMap of list.

This is a simple example:

HashMap<Object, List<Object>> map = new HashMap<Object, List<Object>>();
map.put(key, new LinkedList<Object>);
map.get(key).add(object);