This is article is about how hashmap works internally in java. It is very important to understand the concept of hashmap as hashmap comes into our day-to-day programming practice and it is the most favorite question on the interviewer during the interviews.
Original Article: https://www.java8net.com/2020/01/how-hashmap-works-internally-in-java.html
What is Hashmap and Hashing in java?
How Hashmap works Internally in Java is majorly dependent upon the Hashing Principle. So, Before going to learn how HashMap works internally in java, lets first understand what is HashMap and hashing.
HashMap :
A HashMap is a map used to store mappings of key-value pairs. Also, it works on the Principle of Hashing. To know more about the HashMap, visit this article: https://www.java8net.com/2020/01/hashmap-in-java.html
Hashing Principle :
Simply, Hashing is a method used to produce an integer value from an object and this integer value known as the hash value. In HashMap, the key object is used for Hashing.
Before understanding the internal working of HashMap, you must be aware of the hashCode() and equals() method.
hashCode() : hashCode() method is used to get the hash code of an object. This method is provided by Object class. You can override this in your class to provide your own implementation.
equals(): equals method is used to check that 2 objects are equal or not. This method is provided by Object class. You can override this in your class to provide your own implementation.
What is Buckets?:
The array of the node is called buckets. Each node has a data structure like a LinkedList. More than one node can share the same bucket. It may be different incapacity.
A single bucket can have more than one nodes, it depends on the hashCode() method. The better your hashCode() method is, the better your buckets will be utilized.
Hash Collision :
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.
How Hashmap Calculate the Index of Bucket in java?
To understand how HashMap works internally in Java, we must know about how the HashMap calculates the index of the bucket. Till 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.
Note: 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
index = hash(key) & (n-1)
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.
To know more about the internal working of the hashmap, read this blog: https://www.java8net.com/2020/01/how-hashmap-works-internally-in-java.html
Further Learning:
https://www.java8net.com/2020/02/sort-hashmap-by-key-and-by-value.html
https://www.java8net.com/2020/11/static-class-in-java.html
https://www.java8net.com/2020/02/treemap-in-java.html
https://www.java8net.com/2020/03/java-optional.html
https://www.java8net.com/2020/01/lambda-expression-java.html
https://www.java8net.com/2020/01/functional-interface-in-java.html
Top comments (0)