HashMap Implementation with a Balanced Tree

 

In Java 8, the HashMap implementation was enhanced to use balanced trees (specifically, red-black trees) instead of linked lists in certain situations to improve performance. Here's a detailed explanation of how and why this change was made:

Background

In a typical HashMap, each bucket (or bin) in the underlying array is a linked list that holds all the entries with the same hash code. This means that if many keys hash to the same bucket (i.e., there are hash collisions), the time complexity for operations like get, put, and remove degrades from O(1) to O(n) in the worst case, where n is the number of elements in the bucket.

Changes in Java 8

To address this performance degradation, Java 8 introduced the use of balanced trees (red-black trees) for bins with a high number of collisions. The basic idea is to use a linked list for buckets with a small number of entries and switch to a red-black tree once the number of entries in a bucket exceeds a certain threshold (specifically, 8 entries). Here's how it works:

1. Initial State (Linked List): When entries are added to a HashMap, they are initially placed in a bucket that is represented as a linked list.

2. Threshold Check: When the number of entries in a single bucket exceeds the threshold (8 entries), the linked list is converted into a red-black tree.

3. Tree Structure: The red-black tree provides more efficient search, insertion, and deletion operations (O(log n) time complexity) compared to the linked list.

4. Tree to List Conversion: If the number of entries in a tree bin drops below a certain threshold (6 entries), the tree is converted back to a linked list to save memory.

Benefits

• Performance Improvement: Using a red-black tree reduces the time complexity of the operations from O(n) to O(log n) in cases of high hash collisions, significantly improving the performance of the HashMap under heavy load.
• Memory Efficiency: The conversion back to a linked list when entries are removed keeps memory usage efficient.

Implementation Details

Here are some key points about the implementation:

• TreeNode Class: Java 8 HashMap includes an internal TreeNode class that extends Node and adds tree-specific fields (e.g., parent, left, right, color).
• Treeify: The treeifyBin method is responsible for converting a linked list bin to a tree bin when the threshold is exceeded.
• Untreeify: The reverse conversion from tree bin to linked list happens through the untreeify method when the number of entries decreases.

Example

Here is a simplified example to illustrate the concept:

public class HashMap<K, V> {
    static final int TREEIFY_THRESHOLD = 8;
    static final int UNTREEIFY_THRESHOLD = 6;

    static class Node<K, V> {
        final int hash;
        final K key;
        V value;
        Node<K, V> next;
    }

    static final class TreeNode<K, V> extends Node<K, V> {
        TreeNode<K, V> parent;
        TreeNode<K, V> left;
        TreeNode<K, V> right;
        boolean red;
    }

    // Other methods and fields of HashMap...

    void treeifyBin(Node<K, V>[] tab, int index) {
        // Convert bin at index to a tree bin
    }

    void untreeifyBin(Node<K, V>[] tab, int index) {
        // Convert tree bin at index to a linked list bin
    }

    // Methods like put, get, remove will use the above logic to manage bins
}

Conclusion

The introduction of red-black trees in Java 8's HashMap enhances performance for hash collision scenarios, making the HashMap more efficient and robust under various conditions. This change ensures that even in the worst-case scenarios, the operations on HashMap remain performant.