In this article, we will discuss the Internal Working of HashMap in Java and how hashmap’s get and put method works internally. As we know that HashMap is a key and value collection in java. The HashMap stores the data in key and value format. It provides the basic implementation of the Map interface of Java. We can put a value with using a key and also we can access this value using that key.
HashMap uses a technique called Hashing. Hashing is a technique to convert an object into an integer. The hashing is done by using the method hashCode(). This method is very important to maintain the performance of the HashMap.
A HashMap is an array of the node and these nodes are like a linked list’s node as the following:
Find and Break a Loop in a Linked list
How to Detect loop in a linked list
Find the nth node from the end of a singly linked list
Find the middle element in a linked list
How to Reverse linked list in Java
Delete given node from a singly linked list
Remove Duplicates from the Unsorted Singly Linked list
The singly linked list is palindrome without extra space
As we have discussed that Hashing is processed to convert a long string into a small string to represent the same string. In other words, the Hashing is a technique to convert an object into an integer number and this number is known as the hashcode of the object and you can generate this hashcode by using hashcode() method. Let’s see the following implementation of the hashcode() method for the class Key:
package com.dineshonjava.algo.map;
/**
* @author Dinesh.Rajput
*
*/
public class Key {
final int data = 112;
private String key;
public Key(String key) {
super();
this.key = key;
}
//index = hashCode(key) & (n-1).
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + data;
result = prime * result + ((key == null) ? 0 : (key.charAt(0)+"").hashCode());
System.out.println("hashCode for key: "+ key + " = " + result);
System.out.println("Index "+ (result & 15));
return result;
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
Key other = (Key) obj;
if (data != other.data)
return false;
if (key == null) {
if (other.key != null)
return false;
} else if (!key.equals(other.key))
return false;
return true;
}
}
In the above code, I am taking a class Key and override hashCode() method to show different scenarios. Here, overridden hashCode() method return a calculated hashcode. The hashCode() method is used to get the hashCode of an object. The hashCode() method of object class returns the memory reference of the object in integer form. But In HashMap, hashCode() is used to calculate the bucket and therefore calculate the index.
We have also overridden equals() method in the above code, equals method is used to check that 2 objects are equal or not. HashMap uses equals() to compare the key whether they are equal or not.
As we have said, HashMap stores elements in the array. Internally it uses array data structure. A bucket is an item of that array. This whole array considers as the buckets. This bucket is used to store nodes. It can store one or more than two nodes. Each node has a link to the next nodes if they store into the same bucket. In that case, a link list structure is used to connect the nodes.
Let’s see the following relationship between bucket and capacity is as follows:
capacity = number of buckets * load factor
If the hash code of two items is same then both items will be stored into the same bucket. That means node storage in the bucket depends on the hashCode() method. The better your hashCode() method is, the better your buckets will be utilized.
HashCode is used to decide the bucket in the HashMap array, so using the HashCode we create an index. What happens, if Hashcode of the key may be very large or may be in the range of integer and if we create arrays for such a range. That may be a reason of the OutOfMemoryException. That is why it uses an index to minimize the size of an array. An index is created by using the following calculation.
index = hashCode(key) & (n-1).
In the above formula, n is a number of buckets or the size of an array. In our example, I will consider n as default size that is 16.
Let’s see the how does HashMap work internally.
Step 1: Create an empty HashMap as the following
Map map = new HashMap();
The default size of HashMap is taken as 16 as the following empty array with size 16.
You can see the above image initially there is no element in the array.
Step 2: Inserting first element Key-Value Pair as the below:
map.put(new Key("Dinesh"), "Dinesh");
This step will be executed as the following:
{
int hash = 4501
Key key = {"Dinesh"}
Integer value = "Dinesh"
Node next = null
}
Let’s see the following diagram of the HashMap:
Step 3: Adding another element Key-Value Pair as the below:
map.put(new Key("Anamika"), "Anamika");
This step will be executed as the following:
{
int hash = 4498
Key key = {"Anamika"}
Integer value = "Anamika"
Node next = null
}
Let’s see the following diagram of the HashMap:
Step 4: (Case of Collision) Adding another element Key-Value Pair as the below:
map.put(new Key("Arnav"), "Arnav");
This step will be executed as the following:
{
int hash = 4498
Key key = {"Arnav"}
Integer value = "Arnav"
Node next = null
}
Let’s see the following diagram of the HashMap:
Step 5: Adding another element Key-Value Pair as the below:
map.put(new Key("Rushika"), "Rushika");
This step will be executed as the following:
{
int hash = 4515
Key key = {"Rushika"}
Integer value = "Rushika"
Node next = null
}
Let’s see the following diagram of the HashMap:
As we have seen how does HashMap’s put() method work internally? Let’s move to the next section and see how does HashMap’s get() method work internally.
Now we will fetch a value from the HashMap using the get() method. As the following, we are fetching the data for key {“Arnav”}:
map.get(new Key("Arnav"));
This step will be executed as the following:
Hope this article is able to give much information about the internal working of HashMap in Java.
Happy Learning with DineshonJava.
Strategy Design Patterns We can easily create a strategy design pattern using lambda. To implement…
Decorator Pattern A decorator pattern allows a user to add new functionality to an existing…
Delegating pattern In software engineering, the delegation pattern is an object-oriented design pattern that allows…
Technology has emerged a lot in the last decade, and now we have artificial intelligence;…
Managing a database is becoming increasingly complex now due to the vast amount of data…
Overview In this article, we will explore Spring Scheduler how we could use it by…