How HashMap Works Internally in Java
How HashMap Works Internally in Java
Take a look at this article that explains how Hashmap works in Java, including how it calculates the index of a bucket and how other internals work.
Join the DZone community and get the full member experience.Join For Free
In this article, we are going to see how HashMap internally works in JAVA. Also, we will have a look at what Java 8 made changes on the internal working of Hashmap to make it faster.
A HashMap is a map used to store mappings of key-value pairs. To learn more about the HashMap, visit this article: HashMap in Java
HashMap in Java works on hashing principles. It is a data structure which allows us to store object and retrieve it in constant time O(1) provided we know the key. In hashing, hash functions are used to link key and value in HashMap.
How Hashmap Calculates the Index of a Bucket in Java
To understand how HashMap works internally in Java, we must know about how the HashMap calculates the index of the bucket. Until now, we know the internal structure of HashMap, that HashMap maintains an array of the bucket. But when we store or retrieve any key-value pair, HashMap calculates the index of the bucket for each and every operation. The Key object is used to calculate the index of the bucket. By using this key, the hash value is calculated using the
hash(key) private method of HashMap.
hash(key) method is a private method of HashMap that returns the hash value of the key, also if the hash value is too large then converts it into a smaller hash value.
But what will happen, if the hash value of Key Object returns the integer that is greater than the size of the array i.e., hash(key) > n, then
ArrayOutOfBoundsException could be raised. To handle this situation, HashMap reduces the hash value between 0 and n-1 using an expression :
Index Calculating Expression:
Now, this index value is generated is used by HashMap to find bucket location and can never generate any Exception as the index value always from 0 to n-1.
put() Method Does
Let’s note down the internal working of put method in hashmap.
First of all, the key object is checked for null.
If the key is null, the value is stored in
table position, because hashcode for null is always 0.
Then on next step, a hash value is calculated using the key’s hash code by calling its
hashCode() method. This hash value is used to calculate the index in the array for storing the Entry objects. JDK designers well assumed that there might be some poorly written
hashCode() functions that can return very high or low hash code value. To solve this issue, they introduced another
hash() function and passed the object’s hash code to this hash() function to bring hash value in the range of array index size.
indexFor(hash, table.length) function is called to calculate the exact index position for storing the Entry object.
How Collisions Are Resolved
Here comes the main part. Now, as we know that two unequal objects can have the same hash code value, how two different objects will be stored in the same array location called a bucket.
The answer is LinkedList. If you remember, the Entry class had an attribute "
next." This attribute always points to the next object in the chain. This is exactly the behavior of the LinkedList.
So, in case of collision, Entry objects are stored in a linked list form. When an Entry object needs to be stored in a particular index, HashMap checks whether there is already an entry. If there is no entry already present, the entry object is stored in this location.
If there is already an object sitting on a calculated index, its next attribute is checked. If it is null, and the current entry object becomes the next node in LinkedList. If the next variable is not null, the procedure is followed until next is evaluated as null.
What if we add another value object with the same key as entered before? Logically, it should replace the old value. How it is done? Well, after determining the index position of the Entry object, while iterating over LinkedListd on the calculated index, HashMap calls equals method on the key object for each entry object.
All these entry objects in LinkedList will have similar hashcode but
equals() method will test for true equality. If
key.equals(k) will be true then both keys are treated as the same key object. This will cause the replacement of value objects inside the entry object only.
Visit the original article.
Published at DZone with permission of Shubham Bansal . See the original article here.
Opinions expressed by DZone contributors are their own.