Skip to main content

How does a hash map work internally in Java?


Hash map work internally in Java


Image result for hash map internal working flow


























Basically, HashMap is an array of Entry class, a static inner class defined in HashMap is as below:
static class Entry implements Map. Entry {
final K key;
V value;
Entry next;
final int hash;
//getters and setters
}
Each element in Hashmap stores in it a key, its value, a reference to next entry in case hash value is the same for two entries, in that case, a linked list will be formed.
Default initial capacity of a HashMap is 16 i.e a HashMap is initialized with a default 16 sized array.
Now, let us see what happens when we put an element into HashMap.
Following is the code for put method in hashmap:
public V put(K key, V value) {
if (key == null)
return putForNullKey(value);
int hash = hash(key.hashCode());
int i = indexFor(hash, table.length);
for (Entry e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(hash, key, value, i);
return null;
}
private V putForNullKey(V value) {
for (Entry e = table[0]; e != null; e = e.next) {
if (e.key == null) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(0, null, value, 0);
return null;
}

Lets decode the above lines of code;

1)As the HashMap allows values to be stored with null keys in the map, firstly we check if key is null or not.
2)If key is null,putForNullKey method is called and null key value is placed at 0th position of array.
for (Entry e = table[0]; e != null; e = e.next) {//As each element with same hashvalue forms linked list in a hashmap array, we iterate the element using a for loop.If e==null, we add the new element.

3)If key is not null, we need to find the index in the array where we will store our element and this is done using hashing.
int hash = hash(key.hashCode());//We calculate a unique hash corresponding to each element.
int i = indexFor(hash, table.length);//Passing the hash and array length we find the position in array to store the element.
static int indexFor(int h, int length) {
return h & (length-1);
}
As you can see we do & operation between array length and hash value and thus a location is found from 1to16, so suppose hash value is 00000000 00010000 & 00000000 00010000, will give an index of 16.
4)Next we check if an element entry exists at above found index if it doesnt exist we add the new element entry but if an entry element already exists at the index position , here comes the linkedlist into the picture.
5)In the if condition if (e.hash == hash && ((k = e.key) == key || key.equals(k))) , we compare the hash value and a comparison with the equals method written for the object or for the same references.
6)If the above condition is true, the old value is replaced with the new value.
7)If the 5th condition is false, we iterate the linked list until we find the exact key location and put the entry element.

Comments

Popular posts from this blog

JDK 25: The new features in Java 25

 Java Development Kit (JDK) 25, scheduled for release in September 2025, is set to introduce several significant enhancements. Here's an overview of the notable features: 1. Stable Values API (Preview): This feature introduces stable values—objects holding immutable data treated as constants by the Java Virtual Machine (JVM). By allowing greater flexibility in initialization timing compared to final fields, stable values aim to improve application startup times. They enable performance optimizations akin to constant-folding, previously exclusive to JDK code, and ensure thread-safe, single-time initialization. This decouples the creation of stable values from their initialization without significant performance penalties.  2. Removal of 32-bit x86 Port: JDK 25 plans to eliminate both the source code and build support for the 32-bit x86 port, which was deprecated in JDK 24. Maintaining this port has become less beneficial, especially with the challenges in keeping it updated wit...

what is circuit breaker in microservice

   A circuit breaker is a design pattern used in microservice architecture to improve the resilience and fault tolerance of the system. In a microservice architecture, multiple services work together to deliver a business function. When a service is not available, the downstream services depending on it may start to fail as well, leading to a cascading failure. A circuit breaker helps prevent cascading failures by monitoring the status of the dependent services. If a dependent service is not responding, the circuit breaker trips and redirects the traffic to a fallback mechanism, such as a cache or a default response. The circuit breaker periodically attempts to reconnect to the dependent service, and once it's available, it resumes directing traffic to it. The circuit breaker pattern helps prevent failures from spreading across the system, improves the availability of the overall system, and can help reduce the load on dependent services.

Java RoadMap