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.image 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.

Comments

  1. Hi,

    Thanks for this Nice article just to add while discussing about HashMap its worth mentioning following questions which frequently asked in Java interviews now days like How HashMap works in Java or How get() method of HashMap works in JAVA very often. on concept point of view these questions are great and expose the candidate if doesn't know deep details.

    Javin
    Difference between FIX4.2 vs FIX4.4

    ReplyDelete
  2. Hey Javin,

    You are absolutely right, to answer such questions you need deep knowledge how HashMap works.

    but as per me, this post gives clear understanding :)

    ReplyDelete
  3. Thanks Yogesh, Nice explanation with the help of example.

    ReplyDelete
  4. For the Collison key .. how will you get other values in case a collison occur ... how to get value THREE and FIVE ?? is there a way to get next element in linked list (if collison occurs then a linked list of values is maintained , right ? )

    ReplyDelete
    Replies
    1. I case of hashCode collision, equals method is applied in same bucket with existing elements, if equals method return true, new value is applied on the old key value combination, if equals return false new entry is made with new key value in same bucket.
      --Sanjeev
      http://all-technicals.blogspot.in

      Delete
    2. When you call by respective key ?
      map.get(p3)
      map.get(p5)

      Delete
  5. Very easy to understand. Well explained. Thanks for sharing

    ReplyDelete
  6. Frankly this is the worst looking blog and worst looking code example I have ever encountered. It doesn't matter what's written if I have to hurt my eyes reading it.. maybe you should switch profession because coding clearly doesn't suit your character. :/

    ReplyDelete
    Replies
    1. There's a saying "if you've nothing nice to say - keep quite". Great explanation Yogesh Devatraj

      Delete
  7. Good Explanation

    ReplyDelete
  8. hashCode method must include all fields which are used in equals method.

    ReplyDelete
  9. Yogesh, thanks for explaining this with the small program. Now it is really clear to understand what exact Hash Collision is. There are plenty of blogs explaining how to prevent Hash Collision, but nobody practically explains very clearly what exactly Hash Collision means.

    Thanks,
    Prithwiraj
    http://sribasu.com

    ReplyDelete
  10. Wonderful Explanation
    https://47biz.com

    ReplyDelete
  11. https://turingsanat.com/product-category/network-equipment/

    ReplyDelete

  12. Nowadays email is much popular way in multiple medium of communication. Recuperate AT&T email secret phrase is straightforward through security questions. How about we have a look on the methodology of AT&T email secret phrase reset.
    Call +1-877-637-1326 AT&T password recovery technical support will settle your issues at the earliest opportunity. The administration of client care specialists are constantly accessible methods 24 X 7.

    ReplyDelete
  13. Nice explanation...
    https://47biz.com

    ReplyDelete
  14. Wonderful and Fantastic Explanation.
    https://www.greatminds-software.com/

    ReplyDelete

Post a Comment

Popular posts from this blog

Composite Design Pattern by example

State Design Pattern by Example

Eclipse command framework core expression: Property tester