面试题：Java集合框架HashMap源码深度剖析

从链表转换为红黑树的条件

链表长度：当链表的长度达到 8 时（TREEIFY_THRESHOLD 常量值为 8），并且当前 HashMap 的容量大于等于 64（MIN_TREEIFY_CAPACITY 常量值为 64），会将链表转换为红黑树。如果当前 HashMap 的容量小于 64，此时会优先进行扩容操作，而不是将链表转换为红黑树。
数组位置：链表是挂在 HashMap 内部数组 table 的某个位置上，针对该位置上的链表进行长度判断和转换操作。

源码实现逻辑

插入节点时判断：在 HashMap 的 putVal 方法中，当向 HashMap 插入新节点时，如果在链表中插入新节点后，该链表的长度达到 TREEIFY_THRESHOLD，就会调用 treeifyBin 方法。

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) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

treeifyBin 方法：在 treeifyBin 方法中，首先判断 HashMap 的容量是否小于 MIN_TREEIFY_CAPACITY，如果小于则进行扩容。否则，将链表转换为红黑树。

final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        resize();
    else if ((e = tab[index = (n - 1) & hash]) != null) {
        TreeNode<K,V> hd = null, tl = null;
        do {
            TreeNode<K,V> p = replacementTreeNode(e, null);
            if (tl == null)
                hd = p;
            else {
                p.prev = tl;
                tl.next = p;
            }
            tl = p;
        } while ((e = e.next) != null);
        if ((tab[index] = hd) != null)
            hd.treeify(tab);
    }
}

红黑树的构建：在 TreeNode 的 treeify 方法中，通过左旋、右旋、变色等操作构建红黑树。

final void treeify(Node<K,V>[] tab) {
    TreeNode<K,V> root = null;
    for (TreeNode<K,V> x = this, next; x != null; x = next) {
        next = (TreeNode<K,V>)x.next;
        x.left = x.right = null;
        if (root == null) {
            x.parent = null;
            x.red = false;
            root = x;
        }
        else {
            K k = x.key;
            int h = x.hash;
            Class<?> kc = null;
            for (TreeNode<K,V> p = root;;) {
                int dir, ph;
                K pk = p.key;
                if ((ph = p.hash) > h)
                    dir = -1;
                else if (ph < h)
                    dir = 1;
                else if ((kc == null &&
                          (kc = comparableClassFor(k)) == null) ||
                         (dir = compareComparables(kc, k, pk)) == 0)
                    dir = tieBreakOrder(k, pk);
                TreeNode<K,V> xp = p;
                if ((p = (dir <= 0)? p.left : p.right) == null) {
                    x.parent = xp;
                    if (dir <= 0)
                        xp.left = x;
                    else
                        xp.right = x;
                    root = balanceInsertion(root, x);
                    break;
                }
            }
        }
    }
    moveRootToFront(tab, root);
}

性能提升

查找性能：链表在查找元素时，平均时间复杂度为 O(n)，其中 n 为链表长度。而红黑树作为一种自平衡的二叉查找树，查找、插入和删除操作的平均时间复杂度和最坏时间复杂度均为 O(log n)，因此在链表长度较长时，转换为红黑树可以显著提高查找效率。
插入和删除性能：虽然在链表尾部插入元素的时间复杂度为 O(1)，但在链表中查找特定元素以进行删除操作的时间复杂度为 O(n)。对于红黑树，插入和删除操作虽然需要维护树的平衡（时间复杂度为 O(log n)），但总体上，当链表长度较长时，红黑树在插入和删除操作上的性能也优于链表，特别是在频繁查找和修改的场景下，红黑树的性能优势更加明显。

面试题：Java集合框架HashMap源码深度剖析

知识考点

面试题答案

从链表转换为红黑树的条件

源码实现逻辑

性能提升