Internal Working of HashMap in Java

What is a HashMap?

A map contains key and value pairs. Java has the Map interface, and HashMap is a hashtable-based implementation of this interface. The HashMap class of Java is almost the same as Hashtable, except that it is unsynchronized and permits nulls. 

HashMap provides constant-time performance for basic operations such as insertion and deletion. 

Before understanding the internal working of HashMap, you will first understand the hashCode() and equals() methods.

• equals()
  The equals() method is used to compare two objects. It returns true if the objects are equal. By default, it checks if the memory addresses of the two objects are the same. We override the equals() method to provide custom logic. The overridden equals() should follow some standard properties:
  • Reflexive: An object must be equal to itself.
     
  • Symmetric: If the first_object is equal to the second_object, then the second_object must be equal to the first_object.
     
  • Transitive: If the first_object equals the second_object and the second_object equals the third_object. Then the first_object must be equal to the third_object.
     
  • Comparison with null: equals() should return false if compared to a null object, and it should handle null parameter checks.
     
• hashCode()
  The hashCode() method returns the hash code of an object. By default, it returns the memory reference of an object in integer form. Definition of the hashCode() method is public native hashCode(). It indicates the implementation of hashCode() is native because Java has no direct method to fetch the object's reference. You can also override the default hashCode() method. 
  
  In HashMap, hashCode() is used to calculate the bucket and therefore calculate the index. 
  Note: The hash code of the null key is 0.
   
• Buckets:
  In a HashMap, the array is divided into multiple buckets used to store nodes. A bucket can hold numerous nodes forming a linked list or a balanced tree in case of collisions. Buckets are different in capacity. The relation between bucket and capacity is shown below: 
  
  Depending on the hashCode() method, a bucket can have multiple nodes.

How does HashMap implementation work in Java?

In Java, HashMap is implemented using an array of buckets, where each bucket is essentially a linked list of key-value pairs. The process works as follows:

• Hashing: When you insert a key-value pair into the HashMap, Java computes the hash code of the key using the hashCode() method. The hash code is then used to determine the index (bucket) where the key-value pair will be stored in the array.
• Bucket Indexing: The hash code is used to calculate the index of the array where the key-value pair will be stored. Java applies a hash function to the hash code to ensure that it maps to a valid index in the array.
• Collision Handling: Since multiple keys may hash to the same index, collisions can occur. In the event of a collision, the key-value pairs are stored in the same bucket as a linked list. This means that multiple key-value pairs can exist within the same bucket.
• Retrieval: When you want to retrieve a value associated with a key, Java calculates the hash code of the key, determines the bucket index, and then traverses the linked list (if any) in that bucket to find the key-value pair with the matching key.
• Resize: As elements are added to the HashMap, it may reach a certain threshold (load factor) where it needs to be resized to maintain performance. When resizing occurs, the array of buckets is expanded, and all key-value pairs are rehashed and redistributed into the new array based on their updated hash codes.

Insert Key, Value pair in HashMap

The HashMap in Java is a data structure that stores entries in key-value pairs, and we can access them using an index of another type. It means a corresponding value is stored in a hashmap for every unique key. You can access the value using the key. If you try inserting a duplicate key, the new value will replace the previous one for the specific key. The keys need to be unique, whereas values need not be unique.
Let's see some examples of how to add these pairs and how we can access the values using the corresponding keys.

Example

Now, we will write a program that shows how to create a hashmap and insert key-value pairs.

Code:

import java.util.HashMap;

public class CodingNinjas {
    public static void main(String[] args) {
        // Create a HashMap
        HashMap<String, String> hashMap = new HashMap<>();

        // Insert key-value pair
        hashMap.put("Kanishk", "Writer");
        hashMap.put("Ayush", "Writer");
        hashMap.put("Muskan", "Writer");
        hashMap.put("Shivani", "Writer");

        System.out.println(hashMap);

        String Kanishk_Pos = hashMap.get("Kanishk");
        System.out.println("Kanishk's position is: " + Kanishk_Pos);

    }
}

Output:

{Shivani=Writer, Muskan=Writer, Kanishk=Writer, Ayush=Writer}
Kanishk's position is: Writer

In the above example, we created a class named 'CodingNinjas.' Under void main(), we created a HashMap named 'hashMap' with String-String pair as key-value pair. We inserted key-value pairs in our hashmap using the 'put()' function respectively. Now it does two actions. First, it prints the whole hashmap, and later, using the 'get()' function, it finds the key 'Kanishk' value and stores it in a variable named 'Kanishk_Pos.' Then it displays the value stored in the variable.

Calculating Index

With the help of the hashCode() function, we calculate the index. The following are the steps you need to follow to calculate the index:

1. Calculate the hash code for the key to calculate the index using the hashCode() method.
    
2. After calculating the hash code, use the modulo operator (%) to obtain the remainder when dividing the transformed hash code by the size of the array. This ensures that the resulting index is within the valid range of bucket indices.
    

Once the index is calculated, use it to store the key-value pair, or you can also use it to retrieve the pair. The following code will help you understand better.

Code:

import java.util.HashMap;
import java.util.Map;

public class CodingNinjas {
    public static void main(String[] args) {
        HashMap<String, String> hashMap = new HashMap<>();
        
        hashMap.put("Kanishk", "Writer");
        hashMap.put("Ayush", "Writer");
        hashMap.put("Muskan", "Writer");
        hashMap.put("Shivani", "Writer");

        for (Map.Entry<String, String> entry : hashMap.entrySet()) {
            String key = entry.getKey();
            int hashCode = key.hashCode();
            int index = hashCode % hashMap.size();
            System.out.println("Key: " + key + ", Index: " + index);
        }
    }
}

Output:

Key: Muskan, Index: 0
Key: Ayush, Index: 2
Key: Kanishk, Index: 2
Key: Shivani, Index: 3

Handling hash collisions in Java

“A collision in a HashMap is a state in which two or more keys produce the same hash value and point to the same bucket or index.” Let's understand it with the help of an example.

Code:

import java.util.HashMap;
import java.util.Map;

public class CodingNinjas {
    private String name;

    public CodingNinjas(String name) {
        this.name = name;
    }

    @Override
    public int hashCode() {
        int result = 0;
        for (int i = 0; i < name.length(); i++) {
            result += name.charAt(i);
        }
        return result;
    }

    public static void main(String[] args) {

        HashMap<CodingNinjas, String> hashMap = new HashMap<>();


        hashMap.put(new CodingNinjas("kanishk"), "Writer");
        hashMap.put(new CodingNinjas("Muskan"), "Writer");
        hashMap.put(new CodingNinjas("vaibhvi"), "Writer");
        
        for (Map.Entry<CodingNinjas, String> entry : hashMap.entrySet()) {
            CodingNinjas key = entry.getKey();
            int hashCode = key.hashCode();
            int index = (hashCode % hashMap.size());
            System.out.println("Key: " + key.name + ", Index: " + index + ", Hash Code: " + hashCode);
        }
    }
}

Output:

Key: kanishk, Index: 1, Hash Code: 745
Key: vaibhvi, Index: 1, Hash Code: 745
Key: Muskan, Index: 2, Hash Code: 623

As you can see in the above output, "kanishk" and "vaibhvi" have the same hash value and point to the same index, i.e., 1. This is a case of hash collision.

In cases like these, we check via equals() if the two keys are the same; if the keys are the same, then replace the value with the new value. Otherwise, connect the node objects via a linked list; both are stored at the same index. Before discussing the new HashMap, we should know the structure of a node.

{
 Hash code = ....
 Key =...
 Value =...
 Next Node =...
}

Now the hashmap for the above example becomes:

get() method in HashMap

We already saw the usage of the 'get()' method earlier in this blog, but here we will discuss it in detail. 

The 'get()' retrieves the value for a particular key from the HashMap. The syntax for it is as follows:

Hashmap_name.get(key_name);

Now let's discuss how the 'get()' method gets the value.

1. Calculate the hash code of the key.
    
2. Calculate the index by using the index method.
    
3. Go to index and compare the first element's key with the given key. If both are equals, return the value; otherwise, check for the next element if it exists.
    
4. If the next node is null, then return null.
    
5. If the next node is not null, traverse to the second element and repeat process three until the key is not found or the next is not null.

Handling resizing in Java

When the number of elements in a HashMap reaches a certain threshold (determined by its load factor), resizing occurs to maintain performance. Resizing involves creating a new array of buckets (typically double the size of the original array) and rehashing all existing key-value pairs into the new array. This process ensures that the elements are evenly distributed across the array, reducing collisions and maintaining the efficiency of the HashMap.

Adding key-value pairs to the HashMap in Java

When adding a key-value pair to a HashMap in Java, the following steps are typically followed:

1. Compute the hash code of the key using the hashCode() method.
2. Use the hash code to determine the index (bucket) where the key-value pair will be stored in the array.
3. If the bucket is empty, add the key-value pair directly.
4. If the bucket is not empty due to a collision, add the key-value pair to the end of the linked list in that bucket.

Retrieving values from the HashMap

To retrieve a value associated with a key from a HashMap in Java:

1. Compute the hash code of the key using the hashCode() method.
2. Use the hash code to determine the index (bucket) where the key-value pair is stored in the array.
3. Traverse the linked list (if any) in that bucket to find the key-value pair with the matching key.
4. Return the value associated with the key if found, otherwise return null to indicate that the key is not present in the HashMap.

Removing key-value pairs from the HashMap

To remove a key-value pair from a HashMap in Java:

1. Compute the hash code of the key using the hashCode() method.
2. Use the hash code to determine the index (bucket) where the key-value pair is stored in the array.
3. Traverse the linked list (if any) in that bucket to find the key-value pair with the matching key.
4. If the key is found, remove the key-value pair from the linked list.
5. If the linked list becomes empty after removing the key-value pair, set the bucket to null to free up memory.

Must Read Array of Objects in Java

Frequently Asked Questions

What is HashMap implementation in Java?

HashMap in Java is implemented using an array of buckets, each containing a linked list of key-value pairs. Keys are hashed to determine their bucket location.

What is the implementation theory of HashMap?

HashMap employs hashing to index key-value pairs, handling collisions with linked lists. Resizing occurs to maintain performance by redistributing elements into larger arrays.

How do you implement a HashMap?

Implement a HashMap in Java using an array-based structure, hashing keys to determine bucket locations, and handling collisions with linked lists.

How HashMap is implemented in Java 8?

Java 8 HashMaps use an array of buckets, but they optimize with tree structures for better performance. Additionally, Java 8 introduces the concept of balanced trees to handle collision resolution more efficiently.

Conclusion

HashMap is a very efficient data structure because of its constant i.e. O(1) insertion, deletion, and searching time complexity. This article describes how to Implement a hashmap in Java, but it should not be the end of your practice.

Understanding how to use hashmaps can be extremely beneficial because hashmap-related questions, such as Pair sum, Check duplicate, Count distinct substrings, Maximum frequency number, and many more. 

Do check out The Interview guide for Product Based Companies as well as some of the Popular interview problems from top tech companies like Amazon, Adobe, Google, Uber, Microsoft, etc.

Refer to our guided pathways on Code studio to learn more about DSA, Competitive Programming, JavaScript, System Design, etc. Enroll in our courses, and use the accessible sample exams and questions as a guide. For placement preparations, look at the interview experiences and interview package.

Happy Coding!