HashMap in Java

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:

• Java

Java

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);

    }
}

You can also try this code with Online Java Compiler

Run Code

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:

• Java

Java

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);
        }
    }
}

You can also try this code with Online Java Compiler

Run Code

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:

• Java

Java

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);
        }
    }
}

You can also try this code with Online Java Compiler

Run Code

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

Methods in Java HashMap

Frequently Asked Questions

How hashCode() and equals() are used in HashMap?

hashCode() is used to determine the bucket for storing a key-value pair, while equals() ensures that keys are compared correctly within that bucket, allowing for retrieval or replacement of entries.

What is the difference between HashMap and LinkedHashMap?

HashMap does not maintain any order of keys, while LinkedHashMap maintains the insertion order or access order of keys. This makes LinkedHashMap ideal when predictable iteration order is needed.

What is the time complexity of basic operations in a HashMap?

The time complexity for basic operations like get(), put(), and remove() in a HashMap is O(1) on average, but it can degrade to O(n) in worst-case scenarios due to hash collisions.

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.

Recommended Articles

• Pair sum, Check duplicate
• Count distinct substrings
• Maximum frequency number