Introduction:

HashMaps are indispensable tools for Java developers, offering efficient key-value pair storage and retrieval. But have you ever wondered how these magical data structures work under the hood? This article will delve into the internal workings of HashMaps, exploring concepts like hashing, collisions, and resizing, and how Java 8’s improvements enhance performance.

What is a HashMap?

A HashMap is a data structure that stores key-value pairs, allowing you to quickly retrieve a value based on its associated key. Imagine a dictionary: you look up a word (key) to find its definition (value). HashMaps function similarly, providing fast access to data. The efficiency of HashMap operations, such as insertion, deletion, and retrieval, is approximately O(1) due to its internal hashing mechanism.

Real-World Analogy: Organizing Books in a Library

Imagine a large library where books are stored on numbered shelves. Instead of placing books randomly, you categorize them by the first letter of their title. For example:

• “Harry Potter” goes to the “H” shelf.
• “The Hobbit” also goes to the “H” shelf.

When searching for “Harry Potter,” you know to check the “H” shelf instead of scanning the entire library, making retrieval faster.

This analogy represents the working of a HashMap:

• The library represents the HashMap.
• The shelves represent buckets in HashMap.
• The books represent key-value pairs.
• The first letter categorization represents hashing.

The Internal Structure: Buckets and Nodes

Internally, a HashMap uses an array called a “bucket array.” Each element of this array is a “bucket,” which can hold one or more key-value pairs.

Diagram: Simple Bucket Array

[Bucket 0] -> null
[Bucket 1] -> null
[Bucket 2] -> null
...
[Bucket 15] -> null

Hashing: The Key to Efficiency

When you add a key-value pair to a HashMap using the put() method, the following steps occur:

1. Hash Code Generation: The hashCode() method of the key object is called to generate a hash code. This hash code is an integer representation of the key.
2. Bucket Index Calculation: The HashMap uses the hash code to determine the index of the bucket where the key-value pair should be stored. This is typically done using the modulo operator (%) to map the hash code to a valid bucket index within the array’s bounds.

// Example: Simplified bucket index calculation
int bucketIndex = key.hashCode() % bucketArray.length;

Example:

Let’s say we have a HashMap with 16 buckets. If a key’s hashCode() is 100, the bucket index would be 100 % 16 = 4. The key-value pair would be stored in bucket 4.

Collision Handling: When Keys Collide

A collision occurs when two or more keys generate the same bucket index. This is inevitable, as the number of possible keys is often much larger than the number of buckets. Java uses Chaining (Linked List) and Tree-Based Structures (Java 8+) to resolve collisions.

Separate Chaining (Linked Lists):

Before Java 8, HashMaps handled collisions using separate chaining. In this approach, each bucket stores a linked list of key-value pairs. When a collision occurs, the new key-value pair is added to the linked list in the corresponding bucket.   

Diagram: Bucket Array with Linked Lists (Collision Handling)

[Bucket 0] -> null
[Bucket 1] -> (Key1, Value1) -> (Key2, Value2) -> null (Collision)
[Bucket 2] -> (Key3, Value3) -> null
...
[Bucket 15] -> null

The Role of equals():

When retrieving a value using the get() method, the HashMap first calculates the bucket index based on the key’s hash code. It then iterates through the linked list in that bucket, using the equals() method to compare the keys and find the correct key-value pair.

Java 8 Improvements: Treeify Threshold

Java 8 introduced a significant optimization to improve performance in cases of high collision rates. When the number of key-value pairs in a bucket exceeds a threshold (called the “treeify threshold,” typically 8), the linked list is converted into a balanced binary search tree (specifically, a red-black tree).

Diagram: Bucket Array with Trees (Java 8 Optimization)

[Bucket 0] -> null
[Bucket 1] -> (Key1, Value1) -> (Key2, Value2) -> (Key3, Value3) -> ... (Linked List/Tree)
[Bucket 2] -> (Key4, Value4) -> null
...
[Bucket 15] -> null

Why Trees?

Trees offer a logarithmic time complexity (O(log n)) for search operations, compared to the linear time complexity (O(n)) of linked lists. This significantly improves retrieval performance in cases of frequent collisions.

Load Factor and Rehashing

The load factor determines when the HashMap should expand. The default load factor is 0.75, meaning when the HashMap is 75% full, it doubles in size and rehashes all entries.

Rehashing recalculates hash values and redistributes elements into new buckets, which can impact performance.

Resizing Process:

1. A new bucket array with twice the capacity is created.
2. All existing key-value pairs are rehashed and moved to the new buckets.

Example Code (Java):

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

public class HashMapExample {
    public static void main(String[] args) {
        Map<String, Integer> studentGrades = new HashMap<>();

        studentGrades.put("Alice", 90);
        studentGrades.put("Bob", 85);
        studentGrades.put("Charlie", 95);
        studentGrades.put("David", 80);

        System.out.println("Alice's grade: " + studentGrades.get("Alice"));

        // Example to show duplicate key prevention.
        studentGrades.put("Alice", 92);
        System.out.println("Alice's updated grade: "+ studentGrades.get("Alice"));

        System.out.println(studentGrades);
    }
}

Performance Comparison (Pre-Java 8 vs Java 8)

Real-World Use Cases:

• Caching: Storing frequently accessed data for quick retrieval.
• Configuration settings: Storing application configuration parameters.
• Counting occurrences: Counting the frequency of elements in a collection.

Conclusion:

Understanding the internal workings of HashMaps empowers Java developers to write efficient and optimized code. By grasping concepts like hashing, collisions, and resizing, you can leverage the full potential of this powerful data structure.

Reference:

1. https://medium.com/@yashodhara.chowkar/internal-working-of-hashmap-in-java-and-performance-improvement-in-java-8-a28ee1660cda