Learn about HashMap internal working, Hashing, Re-Hashing, Node usage in HashMap, and Node structure in Java.
Table of Contents
HashMap node structure
To define the map’s entries, HashMap uses the Node<K,V> class, which is a static inner class. It is not incorrect to state that each element in the HashMap is a node.
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
....
}
How does HashMap work internally in Java?
What is Bucket? Multiple key-value pairs can be stored in a bucket. Bucket uses a simple linked list to store objects in HashMap. HashMap uses multiple buckets, each bucket in HashMap refers to a singly linked list of nodes.
You may have the basic idea about the hash function and hashCode. HashMap internally uses the hashCode of the object that we add and then the hash function uses this hashCode. Hash function finds the index by using hashCode and at that index the new entry is added.
Hash function finds the index and checks if the key is already available with the same hashCode in the bucket. If the hashCode matches, the keys are equalized using the equals() method. If equals() returns true, the value of that key in the node is overwritten; otherwise, a new node is created and added to the bucket’s singly linked list.
If the key is not available with the same hashCode in the bucket, the new node is added to the identified bucket.
Bucket Index calculation in HashMap
For each operation, such as store, retrieve, and so on, the HashMap creates a bucket index. The key object is used to calculate the bucket index when we save or retrieve an entry in the HashMap.
Bucket index plays a very important role in the internal working of the HashMap operation. Let’s look at the following formula for bucket index creation.
index = (n-1) & hashCode(key)
By using above formula index value is generated, and HashMap uses it to locate the bucket .In the this formula n is the size of the array or bucket size.
HashMap used (n-1) to handle ArrayOutOfBoundsException in the calculation above. Because an ArrayOutOfBoundsException is raised if the generated hash value exceeds the array’s size, (n-1) reduces the index value and is always between 0 and (n-1).
The following is an example program for bucket index generation.
Disclaimer: This program (BucketIndexGeneration.java) is designed to demonstrate how the Bucket Index is created. Java may not generate the bucket index in the same manner. This is only to help the user understand how Bucket Index works.
import java.util.HashMap;
import java.util.Map;
public class BucketIndexGeneration {
private static final int DEFAULT_INITIAL_HASH_MAP_SIZE = 16;
public static void main(String[] args) {
Map<String, Integer> marksMap = new HashMap<>(DEFAULT_INITIAL_HASH_MAP_SIZE);
String key1 = "Java";
marksMap.put(key1, 75);
int hash1 = key1.hashCode();
int index1 = bucketIndex(hash1);
System.out.println("Entry 1: HashCode: " + hash1 + " Bucket Index : " + index1);
String key2 = "Database";
marksMap.put(key2, 70);
int hash2 = key2.hashCode();
int index2 = bucketIndex(hash2);
System.out.println("Entry 2: HashCode: " + hash2 + " Bucket Index : " + index2);
String key3 = "HTML";
marksMap.put(key3, 85);
int hash3 = key3.hashCode();
int index3 = bucketIndex(hash3);
System.out.println("Entry 3: HashCode: " + hash3 + " Bucket Index : " + index3);
String key4 = "C#";
marksMap.put(key4, 80);
int hash4 = key4.hashCode();
int index4 = bucketIndex(hash4);
System.out.println("Entry 4: HashCode: " + hash4 + " Bucket Index : " + index4);
}
static final int bucketIndex(int hash) {
return (DEFAULT_INITIAL_HASH_MAP_SIZE - 1) & hash;
}
}
Entry 1: HashCode: 2301506 Bucket Index : 2 Entry 2: HashCode: 1854109083 Bucket Index : 11 Entry 3: HashCode: 2228139 Bucket Index : 11 Entry 4: HashCode: 2112 Bucket Index : 0
How does HashMap calculate bucket index internally in Java?
HashMap Hash collision in java
How do hash collisions happen and how are they resolved? When the hash function returns the same bucket location for two different keys, collisions occur. In other words, hash collision is a situation where the calculated bucket index of the two keys is the same.
The bucket index of Entry 2 and Entry 3 is the same in the above program and image, which is 11.
In this scenario, HashMap uses the equals() method to determine whether the keys are equal. If the current key and the previous key are same the previous value is replaced with the current value.
If the keys are not the same then connects the node to the existing node . As a result, index 11 will be used to hold both node (Entry 2 and Entry 3).
What is rehashing in HashMap?
The process of re-calculating the hash code of previously stored items is known as rehashing. When the items in the map (bucket array) surpasses the threshold value, a new size of bucket array is created with a capacity that is about twice as large.
Rehashing is a concept that is completely dependent on the threshold value of the HashMap.
threshold = capacity * (load factor of 0.75).
Load Factor of HashMap: 0.75 Default Initial Capacity: 16 Threshold Value = Load Factor of HashMap * Default Initial Capacity Theshhold Value = 0.75 * 16 = 12
When the hash map receives the 13th key-value pair, the size of the bucket array is increased
New Capacity: 16*2 = 32.
Theshhold Value = Load Factor * New Capacity Theshhold Value = 0.75 * 32 = 24
What is Java 8 improvement in HashMap internal working?
As we know, singly-linked lists were used to store nodes. But this is before Java 8. But after Java 8, some modifications have been made to the HashMap implementation to improve performance.
When the number of items in a hash bucket reaches a specific threshold, bucket switches from linked list to balanced tree.
static final int TREEIFY_THRESHOLD = 8;
What if two different keys have the same hashcode?
If the hashcode of two different objects is same then equals() method is used to compare both the objects.
import java.util.HashMap;
import java.util.Map;
public class BucketIndexGeneration {
private static final int DEFAULT_INITIAL_HASH_MAP_SIZE = 16;
public static void main(String[] args) {
Map<String, Integer> marksMap = new HashMap<>(DEFAULT_INITIAL_HASH_MAP_SIZE);
String key = "Angular";
marksMap.put(key, 80);
int hash = key.hashCode();
int index = bucketIndex(hash);
System.out.println("Entry 1: HashCode: " + hash + " Bucket Index : " + index);
key = "Angular";
marksMap.put(key, 78);
hash = key.hashCode();
index = bucketIndex(hash);
System.out.println("Entry 2: HashCode: " + hash + " Bucket Index : " + index);
System.out.println(marksMap);
System.out.println(marksMap);
}
static final int bucketIndex(int hash) {
return (DEFAULT_INITIAL_HASH_MAP_SIZE - 1) & hash;
}
}
Entry 1: HashCode: 806118850 Bucket Index : 2
Entry 2: HashCode: 806118850 Bucket Index : 2
{Angular=78}
You can see that Entry 1 and Entry 2 have the same HashCode in the example above. In this situation, HashMap uses equals() methods internally, and if both keys are still the same, the previous value is replaced with the current value.
The map has only one entry. The value 80 is replaced by the value 78.
Recommended Articles
- Java 8 interview questions
- Java stream collect to map example
- Sequential Vs Parallel stream
- Concurrent collection with examples in java
- Example of Comparable vs Comparator
