HashMap hashCode collision by example

As we all know Hash is a part of Java Collection framework and stores key-value pairs. HashMap uses hash Code value of key object to locate their possible in under line collection data structure, to be specific it is nothing but array. Hash code value of key object decide index of array where value object get stored. As per hashcode – equals method implementation rules

• Objects that are equal according to the equals method must return the same hashCode value. &
• If two objects are not equal according to equals, they are not required to return different hashCode values.

As per above statement it is possible that two different object may have same hashcode values, this is called hashcode collision. To overcome this problem concept of bucket has been introduced. All the Value objects whose corresponding Key’s hashcode values are same , they fall under same bucket. Above diagram explains hash code collision. There are three key-value entries are shown , out of which second and third has same hashcode , that why they kept under same bucket.

To understand it in details , consider following example

  1: import java.util.*;
  2: class  TestCollison
  3: {
  4: 	public static void main(String[] args) 
  5: 	{
  6: 		
  7: 		HashMap map = new HashMap();
  8: 		Person p1 = new Person(1,"ABC");
  9: 		Person p2 = new Person(2,"DEF");
 10: 		Person p3 = new Person(1,"XYZ");
 11: 		Person p4 = new Person(1,"PQR");
 12: 		Person p5 = new Person(1,"PQR");
 13: 		System.out.println("Adding Entries ....");	
 14: 		map.put(p1,"ONE");
 15: 		map.put(p2,"TWO");
 16:     	map.put(p3,"THREE");
 17: 		map.put(p4,"FOUR");
 18: 		map.put(p5,"FIVE");
 19: 
 20: 		System.out.println("\nComplete Map entries \n" + map);
 21: 
 22: 		System.out.println("\nAccessing non-collided key");	
 23: 		System.out.println("Value = "+map.get(p2));
 24: 		System.out.println("\nAccessing collided key");	
 25: 		System.out.println("Value = " + map.get(p1));
 26: 	}
 27: }
 28: 
 29: 
 30: class Person 
 31: {
 32: 	private int id;
 33: 	private String name;
 34: 
 35: 	public Person(int id, String name) { this.id = id; this.name = name;}
 36: 
 37: 	public String getName() { return name;}
 38: 
 39: 	public int getId() { return id;}
 40: 
 41: 	public void setId(int id) { this.id = id;}
 42: 
 43: 	public void setName (String name) { this.name = name; }
 44: 
 45: 	public int hashCode(){ 
 46: 			System.out.println("called hashCode for ="+ id+"."+name);
 47: 			return id; 
 48: 		}
 49: 
 50: 	public boolean equals(Object obj ){ 
 51: 		System.out.println("called equals on ="+ id+"."+name +  "  to compare with  = "+ ((Person)obj).getId() + "."+ ((Person)obj).getName());
 52: 		boolean result = false;
 53: 		if (obj instanceof Person)
 54: 		{
 55: 			if( ((Person)obj).getId() == id  && ((Person)obj).getName().equals(name) )
 56: 				result = true;
 57: 		}
 58: 		return result;
 59: 	}
 60: 	public String toString() { return id+" - "+name;} 
 61: }

In this example we have defined class Person, it is being used as keys in map. I have intentionally implemented hashcode() method so that hashcode collision will occur.

In test class i have defined four instance of person class and added them to hahsmap as keys and a constant string as value. You can notice that instance p1,p3,p4 and p5 will have same hashcode value, as hashcode() method consider only ID. As a result when you put p3 instance to map , it lands under same bucket of instance p1. Same will be happened with p4 and p5 instance.

Have a look at the output of this program to understand in details.

  1: ---------- java ----------
  2: Adding Entries ....
  3: called hashCode for =1.ABC
  4: called hashCode for =2.DEF
  5: called hashCode for =1.XYZ
  6: called equals on =1.XYZ  to compare with  = 1.ABC
  7: called hashCode for =1.PQR
  8: called equals on =1.PQR  to compare with  = 1.XYZ
  9: called equals on =1.PQR  to compare with  = 1.ABC
 10: called hashCode for =1.PQR
 11: called equals on =1.PQR  to compare with  = 1.PQR 
 12: 
 13: Complete Map entries 
 14: {1 - PQR=FIVE, 1 - XYZ=THREE, 1 - ABC=ONE, 2 - DEF=TWO} 
 15: 
 16: Accessing non-collided key
 17: called hashCode for =2.DEF
 18: Value = TWO 
 19: 
 20: Accessing collided key
 21: called hashCode for =1.ABC
 22: called equals on =1.ABC  to compare with  = 1.PQR
 23: called equals on =1.ABC  to compare with  = 1.XYZ
 24: Value = ONE 
 25: 
 26: Output completed (0 sec consumed) 

Here you can see log trace of hashcode and equals method to understand HashMap’s behavior. When you put third entry to map , it calls equals method on all the keys which are already present in the same bucket to find duplicate keys , see line no 6. Same behavior can be notice while adding fourth entry, see line no 8 & 9.

Now consider fifth case where instance p5 is put against “FIVE” value. Instance p4 & p5 are equal as per equals() method implementation so it is a duplicate key, so map should replace existing value with new value. the same behavior you can find in output trace , see line no 11.

This example states that implementation of hashCode and equals methods are very important while using Maps collection.