Working of HashMap Put Method

The following two tabs change content below.
Prasad Kharkar is a java enthusiast and always keen to explore and learn java technologies. He is SCJP,OCPWCD, OCEJPAD and aspires to be java architect.

Latest posts by Prasad Kharkar (see all)

Continuing with understanding of hashmaps in java, let us understand in depth how hashmap operations work. In this article we will study the working of HashMap put method.

Working of HashMap Put Method:

Before going into depth of hashmap put method, please read what are hashcodes and significance of equals and hashcode methods.

After reading above articles, you’ve known now for user defined objects, we must override equals and hashcode methods for objects to become good hashing keys. Let us consider we have a Bike class and we are making below assumptions.

  • Bike has a field manufacturer which describes the manufacture of bike.
  • Bike has a field engineCapacity which is the capacity of bike’s engine.
  • hashCode() method is overridden so that it returns only engineCapacity.
  • equals() method is overridden so that bikes are equal if manufacturer and engineCapacity is equal.

Now, we know that HashMaps use buckets i.e. hashcode and some objects are placed into it which have same hashcode. How does it work internally? Let us try to understand it.

Here is our Bike class.

Bike.java

Note that for simplicity, for hashCode, we are simply returning the engineCapacity of Bike so that all bikes with same engineCapacity will fall into same bucket. i.e. they will have same hashcode.

Let us create a Map and add bikes into it.

What have we done here?

  • Created a bike cbr250r with manufacturer as Honda and engineCapacity as 250.
  • Created a bike fireblade with manufacturer as Honda and engineCapacity as 1000.
  • Created a bike ninja250r with manufacturer as Kawasaki and engineCapacity as 250

Now, because of our hashCode() implementation, cbr250r and ninja250r will have same hashCode. Let us understand working of hashmap put method when first bike is put into the map.

  • When bikes.put(cbr250r, null); is invoked, a table of type Entry is created with initial capacity = 16 as mentioned in previous article. So an array of Entry elements is created with its index from 0 to 15.
  • The hash value of cbr250r is calculated based on which the index of array of type Entry is decided. Let us say index value is 10.
  • Now a new node is created which holds the key as cbr250r, if the bucket is currently not referring to any node, it will refer to this newly created node. The structure of HashMap will be something like below
After adding cbr250r

After adding cbr250r

So at the end of bikes.put(cbr250r, null);  operation, a node is created with cbr250r object which is being referred by 10th element in the array of Entry objects.

Now, when we add fireblade using bikes.put(fireblade, null); very similar operations will occur and it will be another entry in the array as its hashcode will be different. So HashMap will look like below after adding fireblade.

fireblade added

fireblade added

 

Now comes the tricky part. We are going to perform bikes.put(ninja250r, null); , this is what happens under the hood.

  • hash value for ninja250r is calculated based on our hashCode() implementation, which is 250.
  • Now, the index for corresponding hash is determined.
  • As cbr250r has the same hashcode, the index in array of Entry objects will be the same for ninja250r also.In our case, the index is 10
  • Now it is checked whether the array element at index 10 i.e. table[10] is already referring to some linked list or not. If yes, the list is traversed till the end and newly put object is added to end of the linked list.
  • So ninja250r will be added at the end of list referred by table[10].

The diagram at the end of above operation will be as below.

Ninja 250r added

Ninja 250r added

I hope this article helped understand the working of hashmap put method. In next article, we will learn how get method works while finding the objects.

 

 

Share Button

2 comments for “Working of HashMap Put Method

Leave a Reply

Your email address will not be published. Required fields are marked *