为什么链表改为红黑树的阈值是 8?

JDK 8 中 `HashMap` 设计链表转换为红黑树的阈值为 8 是有理论依据的，主要源自概率统计中的 **泊松分布**。泊松分布用于描述在给定时间或空间内某个事件发生的次数，特别适用于稀疏的事件。对于 `HashMap` 来说，这个事件就是元素被分配到某个桶中的次数。 根据源码中的注释，泊松分布帮助设计者预测了在理想情况下，随机哈希码下节点分布在 `HashMap` 中桶的情况。链表长度为 8 的概率非常低，继续增大的可能性更小，因此设计者根据这一统计结果，选择了链表长度达到 8 时，转换为红黑树来优化性能。 以下是这个选择背后的一些关键点： 1. **链表的劣势**：当链表长度较长时，查找性能会下降到 O(n)，这是低效的。 2. **红黑树的引入**：当链表长度达到 8 时，`HashMap` 将链表转换为红黑树，红黑树查找的时间复杂度为 O(log n)，显著提升了性能。 3. **泊松分布的概率**：根据泊松分布，链表长度达到 8 的概率极低，只有 0.00000006（即不到千万分之一），因此继续增大链表长度的场景非常罕见，链表长度为 8 是合理的转换阈值。 总结来说，**链表长度为 8 时的转换是基于统计学计算得出的最佳平衡点**，既避免了链表过长带来的性能问题，又保持了较小的内存占用。