Internal Working of HashMap

A HashMap is a data structure that allows for fast retrieval of data based on a key. In Java, it is implemented as a hash table, which is an array of linked lists. The basic idea behind a hash table is to use a hash function to map keys to indices in the array, and then store the values at those indices.

Here is a brief overview of how a HashMap works internally:

1. When a HashMap is created, an underlying array is created with a default capacity (usually 16). The array is initially empty, and each element is set to null.
2. When a key-value pair is added to the HashMap, the key is first hashed using the hashCode() method. The hash code is used to calculate an index in the array using the indexFor() method.
3. If the array element at the calculated index is null, a new Entry object (which contains the key-value pair) is created and added to the array. If the array element is not null, it means that there is already an Entry object at that index.
4. In this case, a linear search is performed on the linked list at that index to check if the key already exists. If it does, the value associated with that key is updated. If it does not, a new Entry object is added to the end of the linked list.
5. If the number of Entry objects in the HashMap exceeds a certain threshold (called the load factor), the underlying array is resized (doubled in size by default) and all the existing Entry objects are rehashed and placed into the new array.
6. When a key is used to retrieve a value from the HashMap, the key is first hashed and the index is calculated. If there is no Entry object at that index, it means that the key is not in the HashMap. If there is an Entry object, a linear search is performed on the linked list at that index to find the Entry object with the matching key.
7. Once the Entry object is found, the value associated with that key is returned.
8. When an Entry object is removed from the HashMap, the key is first hashed to find the index in the array. Then, the linked list at that index is searched to find the Entry object with the matching key. If it is found, it is removed from the linked list. If the linked list becomes empty as a result, the array element is set to null.

Overall, a HashMap provides fast retrieval of data based on a key by using a hash function and an underlying array of linked lists. The hash function and load factor can be tuned to achieve a good balance between performance and memory usage.

Copyright © 2023

All Rights Reserved
Developed by VIJAY RATHOD