---

一、引言

Java 8中HashMap的一个重要改进是引入了红黑树来优化链表过长的问题。当哈希桶中的链表长度超过阈值（默认为8）时，链表会被转换为红黑树，这显著提升了在哈希冲突严重时的性能。

二、链表转红黑树的触发条件

HashMap在链表长度达到8且数组容量达到64时才会进行红黑树转换。这个设计是经过优化的阈值选择，因为当链表较短时，红黑树的维护成本可能会超过其带来的性能收益。

public class TreeConversionThreshold {
    public static void main(String[] args) {
        // 模拟HashMap中的链表转树条件判断
        class Node {
            int hash;
            Object key;
            Object value;
            Node next;
            
            Node(int hash, Object key, Object value) {
                this.hash = hash;
                this.key = key;
                this.value = value;
            }
        }
        
        // 创建一个链表模拟哈希桶
        Node head = null;
        int count = 0;
        
        // 添加节点直到达到转换阈值
        for (int i = 0; i < 9; i++) {
            Node newNode = new Node(1, "key" + i, "value" + i);
            newNode.next = head;
            head = newNode;
            count++;
            
            System.out.printf("添加第%d个节点，", count);
            if (count >= 8) {
                System.out.println("达到转换阈值，准备转换为红黑树");
            } else {
                System.out.println("继续使用链表结构");
            }
        }
    }
}

三、红黑树的节点结构

HashMap中的红黑树节点使用TreeNode类实现，它继承自LinkedHashMap.Entry。TreeNode不仅包含红黑树所需的父节点、左右子节点引用，还保留了链表节点的next引用，这使得红黑树节点仍然可以按照插入顺序进行遍历。

public class TreeNodeStructure {
    static class TreeNode<K,V> {
        final int hash;
        final K key;
        V value;
        TreeNode<K,V> parent;
        TreeNode<K,V> left;
        TreeNode<K,V> right;
        TreeNode<K,V> prev;    // needed for removing
        boolean red;           // 红黑树的颜色属性
        
        TreeNode(int hash, K key, V value, TreeNode<K,V> parent) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.parent = parent;
        }
        
        // 获取根节点
        final TreeNode<K,V> root() {
            for (TreeNode<K,V> r = this, p;;) {
                if ((p = r.parent) == null)
                    return r;
                r = p;
            }
        }
    }
    
    public static void main(String[] args) {
        // 创建一个简单的红黑树结构
        TreeNode<String, Integer> root = 
            new TreeNode<>(0, "root", 1, null);
        TreeNode<String, Integer> left = 
            new TreeNode<>(0, "left", 2, root);
        TreeNode<String, Integer> right = 
            new TreeNode<>(0, "right", 3, root);
        
        root.left = left;
        root.right = right;
        
        System.out.println("根节点: " + root.key);
        System.out.println("左子节点: " + root.left.key);
        System.out.println("右子节点: " + root.right.key);
    }
}

四、链表转换为红黑树的过程

转换过程首先需要将链表节点转换为树节点，然后按照红黑树的规则进行树化。这个过程包括构建父子关系、平衡调整等多个步骤。

public class TreeifyProcess {
    static class Node {
        int hash;
        String key;
        String value;
        Node next;
        
        Node(int hash, String key, String value) {
            this.hash = hash;
            this.key = key;
            this.value = value;
        }
    }
    
    static class TreeNode extends Node {
        TreeNode parent;
        TreeNode left;
        TreeNode right;
        boolean red = true;
        
        TreeNode(int hash, String key, String value) {
            super(hash, key, value);
        }
        
        // 模拟树化过程
        static TreeNode convertToTree(Node head) {
            // 转换链表节点为树节点
            TreeNode root = new TreeNode(head.hash, head.key, head.value);
            TreeNode current = root;
            Node next = head.next;
            
            while (next != null) {
                TreeNode node = 
                    new TreeNode(next.hash, next.key, next.value);
                // 模拟插入过程
                insertIntoTree(root, node);
                next = next.next;
            }
            
            return root;
        }
        
        private static void insertIntoTree(TreeNode root, TreeNode node) {
            TreeNode parent = root;
            TreeNode current = root;
            
            while (current != null) {
                parent = current;
                if (node.hash < current.hash)
                    current = current.left;
                else
                    current = current.right;
            }
            
            node.parent = parent;
            if (node.hash < parent.hash)
                parent.left = node;
            else
                parent.right = node;
            
            // 这里省略了实际的红黑树平衡调整过程
        }
    }
}

五、红黑树的平衡调整

红黑树转换后需要进行平衡调整，确保树满足红黑树的五个基本性质。这包括着色调整和旋转操作，以维持树的平衡性。

public class TreeBalancing {
    static class TreeNode {
        boolean red;
        TreeNode parent;
        TreeNode left;
        TreeNode right;
        
        // 左旋操作
        void rotateLeft(TreeNode root) {
            if (this.right == null)
                return;
                
            TreeNode rChild = this.right;
            this.right = rChild.left;
            
            if (rChild.left != null)
                rChild.left.parent = this;
                
            rChild.parent = this.parent;
            
            if (this.parent == null)
                root = rChild;
            else if (this == this.parent.left)
                this.parent.left = rChild;
            else
                this.parent.right = rChild;
                
            rChild.left = this;
            this.parent = rChild;
        }
        
        // 右旋操作
        void rotateRight(TreeNode root) {
            if (this.left == null)
                return;
                
            TreeNode lChild = this.left;
            this.left = lChild.right;
            
            if (lChild.right != null)
                lChild.right.parent = this;
                
            lChild.parent = this.parent;
            
            if (this.parent == null)
                root = lChild;
            else if (this == this.parent.right)
                this.parent.right = lChild;
            else
                this.parent.left = lChild;
                
            lChild.right = this;
            this.parent = lChild;
        }
    }
}

六、红黑树退化为链表

当红黑树节点数量减少到6个或更少时，HashMap会将红黑树转换回链表。这种设计考虑了数据结构转换的成本，避免在临界点反复转换。

public class TreeUntreeify {
    public static void main(String[] args) {
        Map<String, String> map = new HashMap<>();
        
        // 添加足够多的元素触发树化
        for (int i = 0; i < 10; i++) {
            map.put("key" + i, "value" + i);
        }
        
        // 移除元素直到触发反树化
        for (int i = 9; i >= 4; i--) {
            map.remove("key" + i);
            System.out.println("移除一个元素后的大小: " + map.size());
            if (map.size() <= 6) {
                System.out.println("节点数达到反树化阈值");
            }
        }
    }
}

七、总结

本文深入分析了HashMap中链表与红黑树转换的核心机制。从链表转换为红黑树的触发条件，到红黑树节点的结构设计，再到具体的转换过程和平衡调整，详细阐述了HashMap在处理哈希冲突时的优化策略。理解这些实现细节，有助于更好地理解HashMap的性能特征，做出更合理的使用决策。HashMap的这种动态转换机制，也为我们在设计类似的数据结构时提供了很好的参考。