Beyond Buckets and Lists: A Look Inside HashMap’s Dynamic Data Storage

Java’s HashMap is a fundamental data structure for storing key-value pairs. While its basic operations of adding and retrieving elements seem straightforward, a deeper dive reveals a fascinating interplay between efficiency and adaptability. This article delves into the internal workings of HashMap, exploring how it utilizes a combination of hash tables, linked lists, and even red-black trees (in Java 8 and later) to optimize performance for various scenarios. We’ll uncover the mechanisms behind key-value storage, collision handling, and the dynamic transformation employed by HashMap to ensure efficient data access.

class HashMap<K, V> {

    private Node<K, V>[] table; // Hash table (array of buckets)
    private int size; // Number of key-value pairs
    private final double loadFactor; // Threshold for resizing

    // ... other methods and constructors

    // Put method (simplified)
    public V put(K key, V value) {
        int hash = key.hashCode(); // Calculate hash code for key
        int index = hash & (table.length - 1); // Get bucket index

        // Collision handling (simplified)
        Node<K, V> newNode = new Node<>(key, value);
        if (table[index] == null) {
            table[index] = newNode;
        } else {
            // Add to linked list in the bucket
            newNode.next = table[index];
            table[index] = newNode;
        }

        size++;
        // Check for resize if needed
        if (size > table.length * loadFactor) {
            // Resize logic (omitted for simplicity)
        }
        return value;
    }

    // Get method (simplified)
    public V get(K key) {
        int hash = key.hashCode();
        int index = hash & (table.length - 1);

        // Traverse linked list if bucket is not empty
        Node<K, V> current = table[index];
        while (current != null) {
            if (current.key.equals(key)) {
                return current.value;
            }
            current = current.next;
        }
        return null;
    }

    private static class Node<K, V> {
        final K key;
        V value;
        Node<K, V> next;

        public Node(K key, V value) {
            this.key = key;
            this.value = value;
        }
    }
}

Explanation:

• This simplified code shows the basic structure of HashMap with a hash table (array of buckets), nodes for key-value pairs, and methods for put and get.
• The put method calculates the hash code and bucket index for the key. It then checks for collisions and adds the new node to the beginning of the linked list in the corresponding bucket.
• The get method uses the same logic to find the bucket index and then iterates through the linked list (if any) to find the node with the matching key. It returns the associated value or null if not found.
• The actual implementation in Java uses more complex logic for resizing, handling null keys, and ensuring thread safety (not shown here).

HashMap in Java 8 (and later versions) can actually utilize a red-black tree under the hood in certain situations. Here’s how it works:

HashMap with Red-Black Trees:

• By default, HashMap uses linked lists within its buckets to store key-value pairs.
• When the number of entries in a single bucket exceeds a certain threshold (default: 8), and the total number of buckets is above a minimum size (default: 64), a conversion to a red-black tree occurs.
• This conversion aims to improve performance for scenarios where frequent insertions and deletions occur within the same bucket. Red-black trees offer efficient insertion, deletion, and search operations (average O(log n) time complexity).