java - Java Hashmap 中有什么理由在 TREEIFY_THRESHOLD 上有 8 个吗？

Question

从 Java 8 开始，如果同一存储桶上的项目超过 8 个 (TREEIFY_THRESHOLD=8)，则 hashMap 略微修改为具有平衡树而不是链表。有什么理由选择8吗？

如果是 9，它会影响性能吗？

标签： javahashmap

Answer 1

使用平衡树而不是链表是一种折衷。在列表的情况下，必须执行线性扫描以在存储桶中执行查找，而树允许日志时间访问。当列表很小时，查找速度很快，并且使用树实际上并没有提供任何好处，而大约 8 个左右的元素在列表中查找的成本变得足够显着，以至于树提供了加速。

我怀疑树的使用是针对密钥哈希被灾难性破坏（例如许多密钥冲突）的例外情况。虽然线性查找会导致性能严重下降，但如果键可直接比较，则使用树会在一定程度上减轻这种性能损失。

因此，8 个条目的确切阈值可能不是非常重要：假设良好的密钥分布，树箱的机会是 0.00000006，因此在这种情况下显然很少使用树箱。当哈希算法灾难性地失败时，存储桶中的键数无论如何都远大于 8。

这会带来空间损失，因为树节点必须包含额外的引用：除了a的字段之外，还有四个对树节点的引用和一个布尔值LinkedHashMap.Entry（参见其源代码）。

从HashMap 类源中的评论：

因为 TreeNode 的大小大约是常规节点的两倍，所以我们仅在 bin 包含足够的节点以保证使用时才使用它们（请参阅 TREEIFY_THRESHOLD）。当它们变得太小（由于移除或调整大小）时，它们会被转换回普通垃圾箱。在具有良好分布的用户哈希码的使用中，很少使用树箱。理想情况下，在随机 hashCodes 下，bin 中节点的频率遵循泊松分布 ( http://en.wikipedia.org/wiki/Poisson_distribution )，默认调整大小阈值为 0.75，参数平均约为 0.5，尽管具有由于调整粒度而导致的较大差异。忽略方差，列表大小 k 的预期出现是 (exp(-0.5) * pow(0.5, k) / factorial(k))。