Home > Java > Java – HashMap in-detail explanation

Java – HashMap in-detail explanation

HashMap works based on hashing algorithm, As per Java doc HashMap has below four constructors,

Constructor Description
HashMap​()
Constructs an empty HashMap with the default initial capacity (16) and the default load factor (0.75).
HashMap​(int initialCapacity)
Constructs an empty HashMap with the specified initial capacity and the default load factor (0.75).
HashMap​(int initialCapacity,
float loadFactor)
Constructs an empty HashMap with the specified initial capacity and load factor.
HashMap​(Map<? extends K,? extends V> m)
Constructs a new HashMap with the same mappings as the specified Map.

Let’s write simple java program, to examine how Map works internally

  1. Create a simple Map and add one key and value to it

public static void main(String[] args) {

Map<Integer, String> map = new HashMap<>();

map.put(1, "Java");

}

We just created Simple Map, which takes key as Integer and Value as String, and added “1” as Key and “Java” as value. By using eclipse debug feature, lets see what’s inside the map

HashMap-one

It created 16 blocks(0-15) and inserted 1st block with key as Integer “1” and Value as String “Java”. Please check the red box, rest all boxes initialized with  null.

2. Add second key and value to the same map

public static void main(String[] args) {

Map<Integer, String> map = new HashMap<>();

map.put(1, "Java");

map.put(2, "Angular");

}

lets see the map in eclipse debug again

HashMap-two

Now the map contains two keys (1,2) and two values (“Java”, “Angular”) as expected, but the keys are added exactly at 1st block and 2nd block respectively, why?

because as we know Map works based on hashing algorithm, whenever we insert key to map, it calls the Object#hashcode() method, based on the value of hashCode(), it will insert the key into that block.

In above case, Integer class overrides the hashCode with its primitive int value, thats why (1,java) got stored in 1st block and (2,Angular) got store in 2nd block.

3. Lets do the same experiment with our own Class

Create a simple Employee class like below

private static class Employee{
int id;
String name;

Employee(int id, String name){
this.id = id;
this.name = name;
}
}

Use this class as Key to the map and examine the same way


public static void main(String[] args) {
Map<Employee, String> map = new HashMap<>(10);
map.put(new Employee(1, "Ramesh"), "Java");
map.put(new Employee(2, "Sathish"), "Angular");
}

We have added two keys as Employee objects and Values as just strings, lets see in which block the keys got stored this time

HashMap-three

This time, it stored in 8th block and 14th block(why? simple answer because of hashCode of Employee objects), to confirm this, lets override hashCode() of Employee to constant value and check the map. If our analysis correct it has to store all the key’s in the same block.

Update Employee class accordingly

private static class Employee{
int id;
String name;
Employee(int id, String name){
this.id = id;
this.name = name;
}
@Override
public int hashCode() {
return 10;
}
}

We dont need to change anything to our map, lets see now where the keys got stored

HashMap-four

Yes, only 10th block got filled with two objects, why? because both employee objects returned the same hashCode (i.e 10). But how does Map recognized those two objects are not duplicate? As we know internally Map#Key is an entrySet(java.util.Set) it called equals method to verify whether the key is duplicate or not.

While retrieving the value from Map also, first it will check the hashCode of the given key and based on that it will go to that block, after finding the block it will call equals() to get the exact value.

So overriding the hashCode() to constant is not at all recommendable. and when we override the hashCode() we should not forget to override the equals() method as well(i.e hashCode()/equals() contract).

 

 

Advertisements
Categories: Java
  1. No comments yet.
  1. No trackbacks yet.

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

%d bloggers like this: