面试题：Java HashMap红黑树转换过程中，重新计算节点位置的原理

原理

哈希冲突解决方式的转变：
- 在HashMap中，当链表长度达到一定阈值（默认8）且数组容量大于等于64时，链表会转换为红黑树以提高查找效率。
- 链表通过链地址法解决哈希冲突，红黑树作为一种平衡二叉树，有着不同的数据组织方式。重新计算节点位置，是因为红黑树的结构特性与链表不同，需要重新定位节点在新结构中的位置，以保证数据在转换结构后仍能正确访问。
哈希值与数组索引的关系：
- HashMap计算节点在数组中的位置是通过 (n - 1) & hash （n为数组长度）。当链表转换为红黑树时，数组长度可能发生变化（扩容时），或者由于结构改变，原有的哈希值与数组索引的映射关系需要调整。

具体实现方式

扩容时重新计算：
- 当HashMap扩容时（数组长度变为原来的2倍），重新计算节点位置的核心代码如下（简化版示意）：

Node<K,V>[] newTab = new Node[newCapacity];
for (Node<K,V> e : table) {
    while (e != null) {
        Node<K,V> next = e.next;
        int hash = e.hash;
        int index = (newCapacity - 1) & hash;
        if (oldCap >= 64) {
            // 如果原数组容量大于等于64，此时链表转换为红黑树，这里会处理红黑树节点的拆分和重新定位
            if ((e.hash & oldCap) == 0) {
                // 新的索引位置不变
                if (loTail == null)
                    loHead = e;
                else
                    loTail.next = e;
                loTail = e;
            } else {
                // 新的索引位置为原索引位置 + 旧数组容量
                if (hiTail == null)
                    hiHead = e;
                else
                    hiTail.next = e;
                hiTail = e;
            }
        } else {
            // 原数组容量小于64，链表还未转换为红黑树，这里还是按照链表方式处理扩容后节点位置
            if (binCount >= TREEIFY_THRESHOLD - 1)
                treeifyBin(tab, hash);
        }
        e = next;
    }
}

这里通过 (e.hash & oldCap) 判断节点新的索引位置。如果 (e.hash & oldCap) == 0，节点在新数组中的索引位置不变；否则，新的索引位置为原索引位置 + 旧数组容量。

链表转换为红黑树时：
- 在转换为红黑树的过程中，主要是将链表中的节点重新组织成红黑树结构。节点的哈希值和数组索引计算方式还是基于 (n - 1) & hash，但在红黑树内部，节点按照红黑树的插入规则进行插入，以维持红黑树的平衡性质。例如，在 treeifyBin 方法中，通过比较节点哈希值和树中已有节点哈希值来确定插入位置。

为什么要这样做

保持数据一致性：
- 重新计算节点位置可以确保在结构转换过程中，HashMap中存储的数据能够被正确访问。如果不重新计算，由于结构变化和可能的数组扩容，原有的节点位置可能无法正确映射到新的结构中，导致数据丢失或无法访问。
适应新结构特点：
- 红黑树的查找、插入和删除操作与链表不同，它有自己的平衡和排序特性。重新计算节点位置可以更好地将数据适配到红黑树结构中，充分利用红黑树高效的查找和插入删除性能，提升HashMap在数据量较大且哈希冲突较多情况下的整体性能。

星途面试题库

面试题：Java HashMap红黑树转换过程中，重新计算节点位置的原理

知识考点

面试题答案

原理

具体实现方式

为什么要这样做