在 JDK 1.8 中，HashMap 引入了 红黑树，用来代替原来的 链表，主要目的是优化 数据冲突 时的性能。简单来说，当某个位置的数据太多，形成很长的链表时，HashMap 会自动把这个链表变成 红黑树，这样就能让 查找、插入 和 删除操作 更加高效。通过这种方式，性能从 原来的慢速度（随数据量增加越来越慢）变成了 更快的速度，避免了链表在大量数据冲突时出现的性能问题。

📚 知识内容
🤔 什么是红黑树？
红黑树（Red-Black Tree）是一种自平衡的 二叉查找树，它具有以下特点：

每个节点是红色或黑色的。
根节点是黑色。
每个叶子节点是黑色的。
如果一个红色节点有子节点，那么它的两个子节点必须是黑色的。
从任何节点到其叶子节点的路径上，黑色节点的数量是相同的。
由于这些特性，红黑树能够保证 O(log n) 的查找、插入和删除时间复杂度。

🤔 为什么 HashMap 引入红黑树？
在 JDK 1.8 之前，HashMap 在发生哈希冲突时，会将冲突的元素通过 链表 存储。链表的插入、删除和查找操作的时间复杂度是 O(n)，当哈希表中的某个槽位发生大量冲突，链表的长度会变得非常长，从而导致性能问题。

为了优化这种情况，JDK 1.8 对 HashMap 做出了以下改进：

链表长度过长时，转化为红黑树：当某个槽位的链表长度超过一定阈值（默认为 8），HashMap 会将链表转换为红黑树。这样，查找、插入和删除操作的时间复杂度从 O(n) 降到 O(log n)。
当红黑树节点数过少时，恢复为链表：如果红黑树中的节点数降到一定值（默认为 6），则会恢复为链表。
为什么采用红黑树而不是其他树？
红黑树 保证了 O(log n) 的时间复杂度，而 平衡二叉树 的时间复杂度是 O(log n)，因此它在处理大量数据时更有效。
红黑树的结构简单，操作起来相对容易实现，不需要像其他平衡树（如 AVL 树）那样频繁地进行旋转操作。
🚀 红黑树与链表的性能比较
链表：在发生哈希冲突时，如果链表长度变得很长，查找某个元素的时间复杂度会变成 O(n)，这对于大量数据的存储来说是非常低效的。

示例：链表查找

Node node = head;
while (node != null) {
if (node.key.equals(key)) {
return node.value;
}
node = node.next;
}
return null;
红黑树：当哈希表的某个槽位发生大量哈希冲突时，HashMap 会把链表转换为红黑树，使查找时间复杂度降到 O(log n)，提高了哈希表操作的效率。

示例：红黑树查找

public Node find(Node node, int key) {
while (node != null) {
if (node.key == key) {
return node;
} else if (key < node.key) {
node = node.left;
} else {
node = node.right;
}
}
return null;
}
🤔 何时转换为红黑树？
在 HashMap 中，哈希冲突时链表长度过长时，哈希表会将该槽位的链表转换为红黑树。默认的阈值为 8。如果链表长度超过 8 个节点，就会触发转化为红黑树。

举个例子：
假设你有一个哈希表，初始化时大小为 16，负载因子为 0.75。哈希表的容量达到 12（16 * 0.75）时，就会触发扩容。当哈希表的某个槽位的链表长度超过 8 时，该链表就会被转化为红黑树，从而提高查询效率。

// 插入数据
map.put(“key1”, “value1”);
map.put(“key2”, “value2”);
…

当哈希冲突严重时，HashMap 会自动将链表转换为红黑树，从而提高效率。

🔎 知识拓展
🏆 为什么 JDK 1.8 会做这样的优化？
性能瓶颈：在大量哈希冲突的情况下，使用链表来存储冲突的元素会导致查找操作的时间复杂度退化为 O(n)。因此，当链表长度过长时，转换为红黑树可以将时间复杂度优化为 O(log n)。

提高查询性能：通过引入红黑树，HashMap 在查找、插入和删除操作上的性能得到了显著提升，特别是在存储大量数据且哈希冲突较为严重的情况下，红黑树能够提供更稳定的性能。

📈 红黑树在实际应用中的优势
查找效率：红黑树保证了 O(log n) 的查找效率，而链表的查找效率是 O(n)。因此，当哈希冲突较多时，红黑树可以显著提升查询速度。

插入与删除效率：红黑树在进行插入和删除时，也能保持 O(log n) 的时间复杂度。相比之下，链表的插入和删除操作有时会达到 O(n) 的时间复杂度。

示例：红黑树插入
// 插入节点
Node newNode = new Node(key, value);
insertIntoRedBlackTree(root, newNode);

// 红黑树插入的代码示例：
public void insertIntoRedBlackTree(Node root, Node newNode) {
// 根据红黑树的规则，插入新节点并进行旋转
// 确保树的平衡和颜色属性
}

⚡ 为什么不使用其他树结构？
虽然 AVL 树 和其他自平衡树也提供了 O(log n) 的时间复杂度，但红黑树在性能和实现上比这些树结构要更加高效。红黑树不需要像 AVL 树那样频繁地进行旋转操作，它的平衡操作相对较少，因而在实际应用中表现更好。

📝 总结
在 JDK 1.8 中，HashMap 引入了 红黑树 来优化链表的性能。这个改动的主要目的是避免链表在哈希冲突严重时导致查找效率变差的问题。当链表长度超过 8 时，HashMap 会自动将链表转换为红黑树，从 O(n) 优化为 O(log n) 的查询效率。这一改动显著提升了 HashMap 在高并发、大数据量情况下的性能，使得 HashMap 成为更加高效的哈希表实现。

通过使用红黑树，HashMap 提供了更高效的性能，尤其在处理大量数据并发访问时，能够避免链表带来的性能瓶颈。如果你在开发中使用 HashMap，了解这些优化机制能够帮助你更好地理解它的工作原理和应用场景。

🔑 关键点总结：
红黑树 提供了 O(log n) 的查询、插入和删除效率，解决了链表可能导致的性能瓶颈。
HashMap 在哈希冲突严重时，将链表转换为红黑树，减少了哈希冲突的影响。
这个改动提升了 HashMap 的性能，特别是在处理大量数据和高并发访问时。