Mastering HashMap in Java: How It Works Internally, Handling Hash Collisions, and Java 8 Improvements

Tweet

HashMap is one of the most commonly used data structures in Java. It is a part of the Java Collections Framework and is used to store key-value pairs. In this blog post, we will dive into how HashMap works internally, what hash collisions are, and explore some enhancements introduced in Java 8.

How HashMap Internally Works

At its core, a HashMap uses a data structure called an array to store key-value pairs. Each key is associated with a specific index in the array through a process called hashing. Here's a simplified overview of how it works:

1. Hashing: When you put a key-value pair into a HashMap, the HashMap first calculates a hash code for the key. This hash code is an integer value that represents the key and is used to determine the index where the key-value pair will be stored in the array.

2. 
   

3. Index Calculation: The hash code is then processed to calculate an index within the array. This is typically done by taking the hash code modulo the size of the array. The result is the index where the key-value pair will be stored.

4. 
   

5. Handling Collisions: Hashing is not always perfect, and different keys may produce the same hash code. When two keys produce the same hash code and attempt to be stored at the same index in the array, a collision occurs.

6. 
   

7. Collision Resolution: HashMap employs various techniques to handle collisions. The most common approach is to use a linked list or a more efficient data structure called a red-black tree to store multiple key-value pairs at the same index. This allows HashMap to store and retrieve key-value pairs even when they produce the same hash code.

8. 
   

9. Load Factor: To maintain efficiency, HashMap dynamically resizes its array when the number of stored key-value pairs exceeds a certain threshold, known as the load factor. This ensures that the HashMap remains efficient in terms of both space and time complexity.

Example:

import java.util.HashMap;

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

        // Create two keys with the same hash code
        Key key1 = new Key("John");
        Key key2 = new Key("Doe");

        // Put key-value pairs into the HashMap
        hashMap.put(key1, "Value 1");
        hashMap.put(key2, "Value 2");

        // Retrieve the value using one of the keys
        String value = hashMap.get(key1);

        // Display the retrieved value
        System.out.println("The value for key1 is: " + value);
    }
}

class Key {
    private String name;

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

    // Override hashCode and equals methods
    @Override
    public int hashCode() {
        // A simple example of generating a hash code
        // All keys will have the same hash code to create a collision
        return 1;
    }

    @Override
    public boolean equals(Object obj) {
        // Custom equality check based on the name field
        if (this == obj)
            return true;
        if (obj == null || getClass() != obj.getClass())
            return false;
        Key otherKey = (Key) obj;
        return name.equals(otherKey.name);
    }
}

In this example:

1. We create a HashMap to store key-value pairs.
2. We define a custom class Key, which is used as the keys in the HashMap. The Key class has a name field.
3. Inside the hashCode method of the Key class, we return a constant value of 1. This means that all instances of Key will have the same hash code, intentionally creating a hash code collision.
4. We also override the equals method in the Key class to compare two Key objects based on their name field.
5. We create two Key instances, key1 and key2, with different names but the same hash code.
6. We put these keys and their corresponding values into the HashMap.
7. Finally, we retrieve the value associated with key1 using hashMap.get(key1). Despite the collision, we can still retrieve the correct value associated with key1 because the equals method is used to distinguish between keys with the same hash code.

This example demonstrates how HashMap handles hash code collisions by relying on the equals method to compare keys when their hash codes are the same.

What is a Hash Collision?

A hash collision occurs when two or more different keys produce the same hash code, causing them to be mapped to the same index in the HashMap's internal array. When a collision happens, HashMap needs to find a way to differentiate between these keys and store or retrieve their associated values correctly.

Java 8 Enhancements in java.util.HashMap

Handling Collisions Efficiently

In previous versions of Java, when multiple key-value pairs with the same hash code collided, they were stored in a linked list at the corresponding bucket in the HashMap. This could lead to performance issues in scenarios where many collisions occurred because the time complexity for operations on linked lists is O(n).

In Java 8, a more efficient approach was introduced. When the number of key-value pairs with the same hash code exceeds a certain threshold (typically 8), the linked list in the bucket is transformed into a balanced tree, specifically a red-black tree. This enhancement significantly improves the time complexity for operations on these key-value pairs from O(n) to O(log n).

Benefits of Red-Black Trees

Red-black trees are a type of self-balancing binary search tree. They ensure that the height of the tree remains balanced, which means that operations like insertion, deletion, and search have a time complexity of O(log n) on average. This is a significant improvement over the linear time complexity of linked lists for large collections of colliding keys.

Example: Using Java 8 Enhanced java.util.HashMap

Here's an example that demonstrates the benefits of the Java 8 enhancements to java.util.HashMap when handling collisions:

import java.util.HashMap;

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

        // Insert 20 key-value pairs with colliding hash codes
        for (int i = 0; i < 20; i++) {
            String key = "Key" + i;
            int value = i * 10;
            hashMap.put(key, value);
        }

        // Retrieve the value for a specific key
        String targetKey = "Key5";
        int targetValue = hashMap.get(targetKey);

        // Display the retrieved value
        System.out.println("The value for " + targetKey + " is: " + targetValue);
    }
}

In this example:

1. We create a HashMap named hashMap to store key-value pairs.

2. We insert 20 key-value pairs into the HashMap. These pairs are designed to have colliding hash codes because they have similar keys ("Key0," "Key1," etc.). The Java 8 enhancements ensure that when collisions occur, a red-black tree is used to maintain efficiency.

3. We retrieve the value associated with the key "Key5" using hashMap.get(targetKey). This operation is performed efficiently, even though there are collisions, thanks to the red-black tree structure.

By using Java 8's enhancements to java.util.HashMap, you can efficiently handle collisions in your code, even when dealing with a large number of colliding keys. This improvement is particularly valuable in scenarios where HashMaps store a substantial number of key-value pairs with the same hash code.