Java Hash Collision in HashMap

How does get(Key key) method works internally in HashMap:

Here are steps, which happens, when you call get() method with key object to retrieve corresponding value from hash based collection

a) Key.hashCode() method is used to find the bucket location in backing array. (Remember HashMap is backed by array in Java) Though hashcode() is not used directly, but they are passed to internal hash() function.

b) In backing array or better known as bucket, key and values are stored in form of a nested class called Entry. If there is only one Entry at bucket location, than value from that entry is returned. Pretty straightforward right?

Things get little tricky, when Interviewer ask second question, What happens if two keys has same hashCode? If multiple keys has same hashCode, than during put() operation collision had occurred, which means multiple Entry object stored in a bucket location. Each Entry keep track of another Entry, forming a linked list data structure there. Now, if we need to retrieve value object in this situation, following steps will be followed :

1) Call hashCode() method of key to find bucket location.

2) Traverse thought linked list, comparing keys in each entries using keys.equals() until it return true.

So, we use equals() method of key object to find correct entry and than return value from that.

Example

package algo.hashmap;

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

public class HashCollision {

	public static void main(String[] args) {

		Map<MyInnerClass, String> myMap = new HashMap<MyInnerClass, String>();
		myMap.put(new MyInnerClass("AB", "CD"), "First");
		
		//Same hashCode same equals
		myMap.put(new MyInnerClass("AB", "CD"), "First");
		
		//Same hashCode different equals
		myMap.put(new MyInnerClass("ABC", "D"), "Second");
		
		System.out.println(myMap);
	}
}

class MyInnerClass {
	private String StrA;
	private String StrB;

	public MyInnerClass(String strA, String strB) {
		super();
		StrA = strA;
		StrB = strB;
	}

	@Override
	public int hashCode() {
		return (StrA + StrB).length();
	}

	@Override
	public boolean equals(Object obj) {
		if (StrB.length() == StrA.length()) {
			return true;
		}
		return false;
	}
}

Same hashCode Same equals :


public static void main(String[] args) {

		Map<MyInnerClass, String> myMap = new HashMap<MyInnerClass, String>();
		myMap.put(new MyInnerClass("AB", "CD"), "First");
		
		//Same hashCode same equals
		myMap.put(new MyInnerClass("AB", "CD"), "First");
		
		//Same hashCode different equals
		//myMap.put(new MyInnerClass("ABC", "D"), "Second");
		
		System.out.println(myMap);
	}

HashCollisionSameEquals

Same hashCode different equals


public static void main(String[] args) {

		Map<MyInnerClass, String> myMap = new HashMap<MyInnerClass, String>();
		myMap.put(new MyInnerClass("AB", "CD"), "First");
		
		//Same hashCode same equals
		//myMap.put(new MyInnerClass("AB", "CD"), "First");
		
		//Same hashCode different equals
		myMap.put(new MyInnerClass("ABC", "D"), "Second");
		
		System.out.println(myMap);
	}

HashCollisionDifferentEquals

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s