Demystifying HashMap in Java: How it Works Under the Hood
How HashMap data structure works internally in Java
Hello guys, one of the popular topic of Java interview is Java collection framework and on that framework, HashMap is probably the most asked class. I have personally seen quetions like HashMap works? How get method of HashMap works, how put method of HashMap works, is HashMap thread-safe etc in my career many times.
In this article, I will try to share everything I know about HashMap so that you can answer such question with confidence.
To start with, HashMap is one of the most widely used data structures in Java, providing an efficient way to store and retrieve key-value pairs. It belongs to the Java Collections Framework and is an implementation of the Map interface.
It represent Hash table data structure, also known as dictionary in python or associative array in Perl. It allows you to map one value to other, so that you can get employee object by storing it against employeeId.
The beauty of this is that it allows get operation in constant time, which means it doesn’t matter how many records you need to store, you will also get the data in constant time. There are some edge cases also which we will discuss in this article
By the way, if you are new to Java programming language or want to improve Java skills then you can also checkout following best Java courses to get better:
- The Complete Java Masterclass (covers Java 17)
- Java Programming and Software Engineering Fundamentals Specialization Certificate on Coursera
- Java Programming Bootcamp: Zero to Mastery
- The Complete Java Programming Masterclass! [Karpado]
- CodeGym (learn Java by building Games)
These are my favorite online courses and platforms to learn Java from scratch and also build your Java skills. If you need more advanced courses to take your Java skill to next level you can also see following articles:
How HashMap works in Java?
As I said HashMap is a fundamental data structure in Java that enables efficient storage and retrieval of key-value pairs. As part of the Java Collections Framework, it utilizes hashing and a clever collision resolution mechanism to provide fast access to elements based on their unique keys.
The magic lies in the hash code generation from keys, which allows the HashMap to map each key-value pair to a specific index in an underlying array.
Understanding how HashMap works under the hood is essential for Java developers to harness its capabilities and build high-performance applications.
Now, let’s explore the inner workings of HashMap, unraveling its core concepts and mechanisms.
1. Overview of HashMap
HashMap is a part of the java.util package and falls under the category of hash table-based data structures. It allows you to store elements as key-value pairs, where each key is unique.
The HashMap class utilizes a hashing function to calculate the hash code for each key, and this hash code determines the index where the key-value pair is stored in an array.
2. Hashing and Hash Code
In HashMap, the hash code is an integer value generated from the key object. The hash code is calculated using the hashCode() method of the key object.
This hash code is then processed using a hash function to map it to a specific index in the underlying array. The goal is to evenly distribute the key-value pairs across the array to achieve efficient storage and retrieval.
3. Resolving Hash Collisions
Due to the nature of hashing, it is possible for two different keys to generate the same hash code, leading to a collision. HashMap uses a technique called chaining to handle such collisions.
Instead of directly storing the key-value pair at the computed index, each index of the array can store a linked list or a tree (depending on the JDK version and the number of elements with the same hash code).
The key-value pairs that generate the same hash code are added to this linked list or tree.
4. Load Factor and Rehashing
HashMap maintains a load factor, which represents the ratio of the number of elements to the size of the underlying array. When the load factor exceeds a certain threshold (typically 0.75), the HashMap automatically increases the size of the array, a process known as rehashing.
Rehashing involves creating a new larger array and rehashing all the key-value pairs to redistribute them across the new array, reducing the likelihood of collisions and ensuring efficient performance.
5. Retrieving Values
When you request a value associated with a specific key, the HashMap first calculates the hash code of the key and then uses it to find the appropriate index in the array. It then traverses the linked list or binary search tree (if present) at that index to find the correct key-value pair.
6. Inserting and Updating Values
When you insert a new key-value pair into the HashMap, it follows the same process as retrieval. The hash code of the key is calculated, and the key-value pair is added to the linked list or tree at the corresponding index. If a key already exists in the HashMap, its value is updated with the new value.
7. Removing Values
To remove a key-value pair from the HashMap, it first calculates the hash code of the key to locate the index. It then searches the linked list or tree at that index to find and remove the matching key-value pair.
8. Performance Considerations
HashMap provides O(1) constant time complexity for retrieval, insertion, and deletion on average.
However, in the worst case, when there are multiple collisions leading to long linked lists or trees, the performance can degrade to O(n), where n is the number of elements in the map. Hence, maintaining a good load factor is essential for optimal performance.
Conclusion
That’s all about how HashMap work under hood in Java. As I have said before, HashMap is a versatile and powerful data structure in Java, offering efficient storage and retrieval of key-value pairs. Its underlying implementation leverages hashing, chaining, and rehashing to provide constant-time operations in most scenarios.
As a Java developer, understanding the inner workings of HashMap will help you utilize this data structure effectively and make informed decisions when designing and optimizing your Java applications.
By the way, if you are new to Java programming language or want to improve Java skills then you can also checkout following best Java courses to get better:
- The Complete Java Masterclass (covers Java 17)
- Java Programming and Software Engineering Fundamentals Specialization Certificate on Coursera
- Java Programming Bootcamp: Zero to Mastery
- The Complete Java Programming Masterclass! [Karpado]
- CodeGym (learn Java by building Games)
These are my favorite online courses and platforms to learn Java from scratch and also build your Java skills. If you need more advanced courses to take your Java skill to next level you can also see following articles:
Other Programming and Development articles you may like
