Introduction

Understanding the internal workings of HashMap is essential for Java developers. This article examines the implemantation details in Java 8, focusing on the key mechanisms that govern its behavior.

Key Operations Overview

1. Resize Conditions

HashMap triggers a resize operation under the following circumstances:

• Initialization: When the map is first created with default settings
• Threshold exceeded: When the number of key-value pairs exceeds the threshold (capacity × load factor)
• Tree conversion preparation: When attempting to convert a linked list to a red-black tree but the underlying array capacity is less than 64

2. Linked List to Tree Conversion

When a bucket's linked list grows sufficiently, HashMap converts it to a red-black tree for better performance. The actual conversion happens when the ninth element is added to the bucket, not the eighth as commonly believed.

Before treeification occurs, the implementation checks the array capacity:

if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
    resize();

If the array capacity is below 64, the map chooses to resize rather than convert to a tree, even if the linked list has grown long enough.

3. Tree to Linked List Conversion

The tree-to-linked list conversion is triggered during resize operations or element removal. A common misconception is that this occurs when the element count drops below 6. However, the actual implementation uses a different approach:

if (root == null || root.right == null ||
    (rl = root.left) == null || rl.left == null) {
    tab[index] = first.untreeify(map);
    return;
}

This condition checks specific structural properties of the tree rather than the element count. The conversion is based on the tree's node structure rather than a simple count threshold.

4. Resize Mechanism

When resizing occurs, the array capacity doubles. The key optimizasion is the efficient recalculation of bucket positions:

if ((e.hash & oldCap) == 0) {
    // belongs to low bucket
    if (loTail == null)
        loHead = e;
    else
        loTail.next = e;
    loTail = e;
} else {
    // belongs to high bucket
    if (hiTail == null)
        hiHead = e;
    else
        hiTail.next = e;
    hiTail = e;
}

Elements are distributed to either the original index or the index plus the old capacity based on the hash value bitwise AND with the old capacity. For linked lists, this preserves order while efficiently redistributing elements.

Implementation Analysis

Initialization

When creating a HashMap without specifying initial capacity:

public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
}

The actual capacity is determined during the first insertion via the resize operation.

Put Operation

The putVal method handles several scenarios:

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
    Node<K,V>[] tab;
    Node<K,V> p;
    int n, i;
    
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e;
        K k;
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    if (binCount >= TREEIFY_THRESHOLD - 1)
                        treeifyBin(tab, hash);
                    break;
                }
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        if (e != null) {
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            return oldValue;
        }
    }
    ++modCount;
    if (++size > threshold)
        resize();
    return null;
}

Capacity Calculation

HashMap uses a bit manipulation technique to ensure proper capacity:

static final int tableSizeFor(int cap) {
    int n = cap - 1;
    n |= n >>> 1;
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

This method rounds up the specified capacity to the next power of two.

Verification Example

The following demonstrates the tree conversion timing:

public class HashMapVerification {
    public static void main(String[] args) {
        Node head = new Node(1);
        head.next = new Node(2);
        head.next.next = new Node(3);
        head.next.next.next = new Node(4);
        head.next.next.next.next = new Node(5);
        head.next.next.next.next.next = new Node(6);
        head.next.next.next.next.next.next = new Node(7);
        
        Node current = head;
        Node nextNode;
        for (int counter = 0; ; ++counter) {
            System.out.println("Counter: " + counter);
            if ((nextNode = current.next) == null) {
                current.next = new Node(9999);
                // When counter reaches 7, current is the 8th element
                // The new element becomes the 9th element
                if (counter >= 8 - 1)
                    System.out.println("Tree conversion triggered");
                break;
            }
            current = nextNode;
        }
    }
    
    static class Node {
        public Integer value;
        public Node next;
        
        Node(Integer val) {
            this.value = val;
        }
    }
}

This confirms that tree conversion occurs when adding the ninth element to a bucket.