How HashMap Works Internally in Java: A Detailed Explanation

HashMap is one of the most frequently used data structures in Java programming. It is an implementation of the Map interface and is used to store key-value pairs. In this article, we’ll explore how HashMap works internally and the major concepts associated with it.

Images credits goes to www.geeksforgeeks.org

What is HashMap?

HashMap is a class in Java’s Collections framework. It is used to store key-value pairs, where each key is unique. It allows the insertion, retrieval, and deletion of elements in constant time on average. HashMap is based on the Hash table data structure, which uses a hash function to map keys to their corresponding values.

How does HashMap work?

HashMap works by using a hash function to map keys to their corresponding values. The hash function takes the key as input and returns an integer value. This integer value is called the hash code of the key. The hash code is used to calculate the index at which the value is stored in an array. The index is calculated by taking the hash code modulo the size of the array.

When a new key-value pair is added to the HashMap, the key is first passed through the hash function to generate its hash code. The hash code is then used to calculate the index where the value should be stored in the array. If there is no element present at that index, the key-value pair is added to the HashMap. If there is an element present at that index, a collision occurs.

       // Creating an empty HashMap
        HashMap<Integer, String> hash_map = new HashMap<Integer, String>();
  
        // Mapping string values to int keys
        hash_map.put(10, "Hello");
        hash_map.put(20, "world");
        hash_map.put(30, "!!");
  
        // Displaying the HashMap
        System.out.println("Initial Mappings are: " + hash_map);
  
        // Inserting existing key along with new value
        String returned_value = (String)hash_map.put(20, "All");
  
        // Verifying the returned value
        System.out.println("Returned value is: " + returned_value);
  
        // Displaying the new map
        System.out.println("New map is: " + hash_map);

Handling Collisions

Collisions occur when two keys have the same hash code, and hence, the same index in the array. When a collision occurs, a linked list is created at that index. The new key-value pair is added to the end of the linked list. When retrieving a value, the hash function is used to calculate the index of the key. If there is a linked list at that index, the linked list is traversed until the key is found.

Resizing the Array

As more key-value pairs are added to the HashMap, the array might become full, and it might not be possible to add any more elements. To handle this situation, the HashMap automatically resizes the array when its size reaches a certain threshold. Resizing involves creating a new array with a larger size and rehashing all the elements from the old array into the new array.

Iterating over HashMap

Iterating over a HashMap involves iterating over each key-value pair in the map. There are two ways to iterate over a HashMap. One is to use the keySet() method to get a Set of all the keys in the HashMap, and then use a for-each loop to iterate over the keys and retrieve their corresponding values. The other way is to use the entrySet() method to get a Set of all the key-value pairs in the HashMap, and then use a for-each loop to iterate over the pairs.

 Iterator it = mp.entrySet().iterator();
    while (it.hasNext()) {
        Map.Entry pair = (Map.Entry)it.next();
        System.out.println(pair.getKey() + " = " + pair.getValue());
        it.remove(); // avoids a ConcurrentModificationException
    }

Performance of HashMap

HashMap provides constant time complexity for insertion, deletion, and retrieval of elements on average. However, in the worst case scenario, when all the keys have the same hash code, the performance of HashMap can degrade to linear time complexity.

Conclusion

HashMap is an essential data structure in Java programming. It uses a hash function to map keys to their corresponding values and allows constant time insertion, deletion, and retrieval of elements. In case of collisions, linked lists are used to store the values. The HashMap automatically resizes its array when it becomes full. By understanding how HashMap works internally, you can use it more efficiently and effectively in your Java programs.

We hope this article has helped you understand how HashMap works internally in Java. If you have any questions or suggestions, please feel free to leave a comment below.