Understanding HashMap

HashMap is one of the most widely used collection class. If we do not understand how Hash Map internally works, it can be very difficult to answer the has map related interview questions. In this blog I will be explaining in details about Hash Map and how it works internally so that it can be easier for us to answer the questions asked in the interview as well as for our better understanding.

But before we move into the details of Hash Map there are couple of things that we need to understand beforehand. These concepts will come handy when explaining the internal working of a Hash Map. The two things that i want to explain here is equals() and ==. equals() method is basically used to compare the logical equality of two objects whereas == is used to compare two object references (address). Suppose I have a class Employee with three attributes - name, age and sex.

package com.sanjiv.collection;

public class Employee{

private String name;
private int age;
private String sex;

public Employee(String name, int age, String sex){
this.name=name;
this.age=age;
this.sex=sex;
}

public String getName() {
return name;
}

public void setName(String name) {
this.name = name;
}

public int getAge() {
return age;
}

public void setAge(int age) {
this.age = age;
}

public String getSex() {
return sex;
}

public void setSex(String sex) {
this.sex = sex;
}
}

Now suppose i create two objects of Employee class, say emp1 and emp2 with same attribute value.

emp1 = new Employee("Chander",35,"Male");
emp2 = new Employee("Chander",35,"Male");

As emp1 and emp2 creates two objects they are pointing to two different memory location in the  heap and thus the emp1==emp2 returns false. Which is quite understandable. But if I say-

emp1 = new Employee("Chander",35,"Male");
emp2=emp1;

This will return true as emp2 is assigned the reference to emp1 and thus both of them are pointing to the same memory location.

Now lets say -

emp1 = new Employee("Chander",35,"Male");
emp2 = new Employee("Chander",35,"Male");

Logically these two objects are equal, so when i call emp1.equals(emp2) it should return true. But surprisingly it retruns false. The reason for this is that i have not overridden the equals() method and thus it inherits the default behavior of  equals() method from Object class which does a == check, and == will check for the address that they are pointing to and thus returns false. This is not the case when u call the same equals() method on String objects or say any other Wrapper Classes object as they all have overridden the equals() method to do a logical comparison rather than inheriting the default behavior and compare the memory address.

Now lets get back to HashMap. A hash map works on the hashing technique and hashing is basically a value returned by the hashcode() method of hash map class. At the moment think of hash code as a memory location in the heap which is used to store objects. As we all know map is used to store key,value pairs, lets say we create and Employee object and use it as a key inside our map. Here i am mapping employee key to the city(value) where he/she lives. In the below code Employee Chander lives in city Pune.

Employee emp1 = new Employee("Chander",35,"Male");

Map map = new HashMap();
map.put(emp1,"Pune");


Now lets say we want to search the same Employee if it exists in the map or not.

Employee searchEmp =new Employee("Chander",35,"Male");
map.get(searchEmp);

But surprisingly we are not able to find this employee in the hash map although it exists there. Lets try to explain what is happening behind the scene and explain the behavior. Basically we are doing put and get operation on the has map and each time when put or get is called it calls the hashcode() method to determine where in the memory to put/get the object from. So when we first called the put method suppose the hascode() for emp1 returned a memoery address of 1000X and the object was stored at 1000X memory location. Then to search the key we called the get() method but this time the hashcode method for searchEmp returned 2000X memory address. and there was no object found at that memory address and thus it returned the value false. So for two identical objects the hash code should always be identical to fetch them from the map. If we don't override the hascode() method our has map will be inconsistent.

Now lets override the hascode() method and see how it goes. I am intentionally returning the same hashcode for each and every object that will be created for the Employee class so that they all fall in the same bucket or memory address (linked list is used internally which will point to the next object in the list).


public int hashCode(){
return 100;
}

Strangely it still returns false. The reason being i have not overridden the equals() method. So once the get() method is able to identify the bucket it calls the equals() method to compare the object stored  in the map with the object that we have passed it as parameter. And as I have not overridden the equals() method it calls the default implementation given in the Object class which as explained earlier does == check. And a == check will compare the memoery address of searchEmp and the object stored in the map. Both of them certainly have two different memory locations.

Now lets override the equals() method as well.


public boolean equals(Object obj){
if(obj instanceof Employee ){
Employee emp =  (Employee)obj;
if((this.name==emp.name)&&(this.age==emp.age)&&(this.sex==emp.sex))
return true;

}
return false;
}

Now the map returns true. First it identifies the memory location by calling he hashcode() method and then compares both the objects using the equals() method. The equals() check if all the attribute values are equal or not if it is equal it returns true.So, basically fetching the object from hash map is a two step process. First identify the memory location where it can be stored and then compare the stored value in the map with the value we are searching for.

An efficient implementation of  hashCode() will return distinct code for each distinct object and thus only one object will be stored in each bucket which will require less number of comparision and faster search of keys in the has map. In my case all objects fall in the same bucket which will require more comparision and less efficient hash map.

There is contract between hashcode and equals method. If you override equals you must override hashcoe and vice-versa.

Hash Map does not allow duplicate key, so if you insert the same key it will replace the value corresponding to that key. The follwoing code will replace the value corresponding to the emp1 key from Pune to Mumbai.

map.put(emp1,"Pune");
map.put(emp1,"Mumbai");

I have tried to keep it simple and still explain the concept of Hash Map. Hope it helps the readers in understanding the basic concept. There is still a lot to discuss about but for basic understanding i hope this helps.

Let me know your views.

Thanks for reading.