HashMap 是如何解决 hash 冲突的 ？为何 HashMap 中的链表须要转成红黑树 ？

解答思路：

对于第一个问题，HashMap 通过将键值对映射到哈希表中的索引来解决 hash 冲突。当两个不同的键产生相同的哈希值时，即发生冲突，HashMap 使用链表或其他数据结构来解决这种冲突。对于第二个问题，HashMap 中的链表转换为红黑树是为了提高查询效率。当链表长度超过一定阈值时（默认为8），使用红黑树可以更快地找到特定元素，从而提高性能。

最优回答：

对于第一个问题，HashMap 通过计算键的哈希值并将其映射到哈希表中的索引来解决 hash 冲突。当发生冲突时，HashMap 使用链表或其他数据结构来存储具有相同哈希值的元素。对于第二个问题，当 HashMap 中的链表长度过长时，查询效率会降低。为了提高查询效率，当链表长度超过一定阈值（默认为8）时，HashMap 会将链表转换为红黑树。红黑树是一种自平衡的二叉搜索树，可以更快地执行插入、删除和查找操作。

一、HashMap 中的哈希冲突解决：
HashMap 通过计算键的哈希值并将其映射到哈希表的索引来解决哈希冲突问题。当两个键的哈希值相同时，这两个键会产生冲突。HashMap 使用链表或其他数据结构（如开放地址法、再哈希等）来解决这种冲突。链表是最常见的解决方案之一，HashMap 在每个索引位置维护一个链表，将具有相同哈希值的元素存储在该链表中。

二、HashMap 中链表转为红黑树的阈值：
在 Java 中，当 HashMap 中的链表长度超过一定阈值（默认为8）时，会将该链表转换为红黑树。这是因为当链表过长时，顺序查找的效率会大大降低。红黑树是一种自平衡的二叉搜索树，具有优秀的查找性能。将链表转换为红黑树可以显著提高查询效率，特别是在处理大量数据时。需要注意的是，当删除操作导致红黑树的节点数量减少时，可能会再次将其转回链表。

三、红黑树的特性：
红黑树是一种自平衡的二叉搜索树，具有以下特性：
1. 每个节点要么是红色要么是黑色。
2. 根节点是黑色。
3. 每个叶子节点（NIL节点）是黑色。
4. 如果一个节点是红色的，那么它的子节点必须是黑色。
5. 从任一节点到其每个叶子节点的所有路径都包含相同数量的黑色节点。这些特性保证了红黑树的相对平衡，从而实现了高效的查找、插入和删除操作。