摘要：我们来深入探讨 HashMap 源码中哈希冲突时插入红黑树的过程，重点分析 TreeNode 类的 putTreeVal 方法。当哈希桶中的链表已经树形化为红黑树后，后续的 put 操作如果仍然发生哈希冲突，并且需要插入到这个红黑树中，就会调用 putTree
我们来深入探讨 HashMap 源码中 哈希冲突时插入红黑树 的过程，重点分析 TreeNode 类的 putTreeVal 方法。当哈希桶中的链表已经树形化为红黑树后，后续的 put 操作如果仍然发生哈希冲突，并且需要插入到这个红黑树中，就会调用 putTreeVal 方法。
1. putTreeVal(HashMap map, Node tab, int h, K k, V v) 方法概述
TreeNode.putTreeVal(HashMap map, Node tab, int h, K k, V v) 方法是负责在红黑树中查找或插入键值对的核心方法。它类似于 HashMap 的 putVal 方法，但操作对象是红黑树，而不是链表或数组桶。
方法签名:
java复制代码 final TreeNode putTreeVal(HashMap map, Node tab, int h, K k, V v)参数:
HashMap map: 当前的 HashMap 实例。Node tab: 哈希表数组 (桶数组)。int h: 要插入键的哈希值。K k: 要插入的键。V v: 要插入的值。返回值:
TreeNode:如果在红黑树中找到了与要插入的键相同的节点，则返回该节点 (用于 putVal 方法后续更新值)。如果成功插入了新的节点 (键不存在)，则返回 null。2. putTreeVal 方法源码分析
我们来逐步分析 TreeNode.putTreeVal 方法的源码逻辑：
java复制代码 final TreeNode putTreeVal(HashMap map, Node tab, int h, K k, V v) {Class kc = null;boolean searched = false;TreeNode root = (parent != null) ? root : this; // 获取红黑树的根节点for (TreeNode p = root;;) { // 从根节点开始遍历红黑树int dir, ph; K pk;if ((ph = p.hash) > h) // 1. 如果当前节点 p 的哈希值 > 要插入的哈希值 hdir = -1; // 应该向左子树查找else if (ph x = new TreeNode(h, k, v, null); // 创建新节点 xp.right = x; // 将新节点 x 设置为当前节点 p 的右子节点x.parent = x.left = x.right = x.prev = p; // 初始化新节点 x 的父节点、子节点和 prev 引用moveRootToFront(tab, balanceInsertion(root, x)); // 平衡红黑树，并将根节点移动到哈希桶的头部return null; // 返回 null，表示插入了新节点}p = p.right; // 5b. 如果当前节点 p 有右子节点，则向右子树查找}else if (dir x = new TreeNode(h, k, v, null); // 创建新节点 xp.left = x; // 将新节点 x 设置为当前节点 p 的左子节点x.parent = x.left = x.right = x.prev = p; // 初始化新节点 x 的父节点、子节点和 prev 引用moveRootToFront(tab, balanceInsertion(root, x)); // 平衡红黑树，并将根节点移动到哈希桶的头部return null; // 返回 null，表示插入了新节点}p = p.left; // 7b. 如果当前节点 p 有左子节点，则向左子树查找}else { // 8. 如果 dir > 0 (应该向右子树查找，或者 compareComparables 比较结果 > 0)if ((p = p.right) == null) { // 9a. 如果当前节点 p 没有右子节点TreeNode x = new TreeNode(h, k, v, null); // 创建新节点 xp.right = x; // 将新节点 x 设置为当前节点 p 的右子节点x.parent = x.left = x.right = x.prev = p; // 初始化新节点 x 的父节点、子节点和 prev 引用moveRootToFront(tab, balanceInsertion(root, x)); // 平衡红黑树，并将根节点移动到哈希桶的头部return null; // 返回 null，表示插入了新节点}p = p.right; // 9b. 如果当前节点 p 有右子节点，则向右子树查找}}}putTreeVal 方法的核心步骤分解:
获取根节点:TreeNode root = (parent != null) ? root : this;: 获取当前红黑树的根节点。如果当前节点 this 不是根节点 (即 parent != null)，则调用 root 方法向上查找根节点。否则，当前节点 this 就是根节点。红黑树遍历循环 (for (TreeNode p = root;;)):从根节点 root 开始，使用无限循环 for (TreeNode p = root;;) 遍历红黑树，查找合适的插入位置。哈希值比较 (if ((ph = p.hash) > h), else if (ph :if ((ph = p.hash) > h): 比较当前节点 p 的哈希值 ph 与要插入的哈希值 h。如果 ph > h，说明要插入的键的哈希值较小，应该在当前节点 p 的 左子树 中查找插入位置。else if (ph : 如果 ph 右子树 中查找插入位置。else if ((pk = p.key) == k || (k != null && k.equals(pk))): 如果 ph == h (哈希值相等)，则进一步比较键是否相等。如果当前节点 p 的键 pk 与要插入的键 k 相同 (使用 == 或 equals 方法比较)，说明找到了相同键的节点。return p;: 直接返回当前节点 p，用于 putVal 方法后续更新值。键的类型比较 (else if (...)):如果哈希值相等，但键不相等，则需要进一步比较键的大小关系，以确定应该向左子树还是右子树查找。comparableClassFor(k): 尝试获取键 k 的 Comparable 类型。如果键 k 实现了 Comparable 接口，则返回其 Class 对象，否则返回 null。compareComparables(kc, k, pk): 如果键 k 和当前节点 p 的键 pk 都是 Comparable 类型，则使用 compareComparables 方法进行比较。compareComparables 方法会调用 k.compareTo(pk) 方法进行比较。复杂条件判断 ((kc == null && ... ) || (!searched && ... )): 这部分代码处理了键没有实现 Comparable 接口，或者键的类型不是 Comparable 类型，或者在比较过程中出现异常等情况。在这些情况下，会尝试使用 tie-breaker (决胜器) 策略，例如，比较 System.identityHashCode(k) 和 System.identityHashCode(pk) 的值，或者直接向右子树查找。dir = compareComparables(kc, k, pk): 如果可以使用 compareComparables 方法进行比较，则将比较结果赋值给 dir。dir 0 表示 k > pk，应该向右子树查找；dir == 0 表示 k == pk (理论上不应该发生，因为前面已经用 equals 方法比较过了，但作为一种容错处理)。向左子树或右子树查找插入位置 (else if (dir :else if (dir : 如果 dir if ((p = p.left) == null): 检查当前节点 p 是否有左子节点。如果没有左子节点，说明找到了插入位置 (当前节点的左子节点为空)。创建新节点并插入到左子树:TreeNode x = new TreeNode(h, k, v, null);: 创建一个新的 TreeNode 节点 x，存储要插入的键值对。p.left = x;: 将新节点 x 设置为当前节点 p 的左子节点。x.parent = x.left = x.right = x.prev = p;: 初始化新节点 x 的父节点为 p，左右子节点和 prev 引用都初始化为 p (在红黑树插入后会进行调整)。moveRootToFront(tab, balanceInsertion(root, x));: 红黑树平衡操作: 调用 balanceInsertion(root, x) 方法对红黑树进行平衡调整 (例如，旋转和颜色变换)，以保持红黑树的平衡性。balanceInsertion 方法会返回平衡后的红黑树根节点。moveRootToFront(tab, ...) 方法将平衡后的根节点移动到哈希桶的头部 tab[index] 位置。return null;: 返回 null，表示成功插入了新的节点。p = p.left;: 如果当前节点 p 有左子节点，则向左子树查找，将 p 指向左子节点，继续下一次循环迭代。else { ... }: 如果 dir > 0 (应该向右子树查找，或者 compareComparables 比较结果 > 0)。逻辑与向左子树查找类似，只是方向变为右子树。6. 红黑树平衡操作 (balanceInsertion(root, x))
balanceInsertion(root, x) 方法是红黑树插入操作中非常关键的一步，它负责在插入新节点 x 后，通过一系列的 旋转 (rotation) 和 颜色变换 (color flip) 操作，来 恢复红黑树的平衡性。红黑树的平衡性是保证其 O(log n) 查找性能的关键。
balanceInsertion 方法的实现比较复杂，涉及到红黑树的五种平衡调整情况。这里我们不深入分析 balanceInsertion 方法的具体实现细节，只需要理解它的作用是：
在红黑树中插入新节点后，保持红黑树的红黑性质 (五个性质)。通过旋转和颜色变换等操作，调整红黑树的结构，使其保持平衡。返回平衡后的红黑树根节点。7. moveRootToFront(Node tab, TreeNode root) 方法
moveRootToFront(Node tab, TreeNode root) 方法的作用是将红黑树的根节点 root 移动到哈希桶的头部 tab[index] 位置。由于红黑树的根节点在树形化过程中可能会发生变化 (例如，旋转操作可能会改变根节点)，因此需要确保哈希桶的头节点始终指向红黑树的根节点。
8. 总结：红黑树插入的核心
TreeNode.putTreeVal 方法实现了在红黑树中插入键值对的逻辑。其核心步骤包括：
从红黑树根节点开始，根据哈希值和键的比较结果，遍历红黑树，查找合适的插入位置 (类似于二叉搜索树的查找)。如果找到相同键的节点，则返回该节点 (用于更新值)。如果没有找到相同键的节点，则在找到的空位置创建新节点并插入到红黑树中。插入新节点后，调用 balanceInsertion 方法进行红黑树的平衡调整，保持红黑树的平衡性。将平衡后的红黑树根节点移动到哈希桶的头部。通过 putTreeVal 方法，HashMap 实现了在红黑树中高效地插入键值对，并保证了红黑树的平衡性，从而在哈希冲突严重的情况下，仍然能够保持较好的性能。
在后续的 HashMap 源码分析中，我们将继续探讨红黑树的删除操作、get 和 remove 等其他操作在红黑树场景下的实现，以及 HashMap 的扩容机制等更深入的内容。
来源：万事都可观