为什么Java8中的哈希映射使用二叉树而不是链表？

Question

我最近才知道 Java 8 哈希映射使用二叉树而不是链表，并且哈希码用作分支 factor.I 了解在高冲突的情况下查找是通过使用二进制 trees.My 从 O(n) 减少到 O(log n)通过为所有键提供相同的哈希码，我们可以看到一个显着的时间差异，但没有人会这样做。

二叉树也比单链表使用更多space，因为它同时存储左和右nodes.Why增加space复杂度，而时间复杂度绝对没有改善，除了一些虚假的测试用例。

Answer 1

这主要是 security-related 更改。虽然在正常情况下很少有可能发生很多冲突，但如果哈希键来自不受信任的来源（例如从客户端收到的 HTTP header 名称），那么有可能并且不是很难专门制作输入，因此结果键将具有相同的哈希码。现在，如果您执行许多 look-ups，您可能会遇到 denial-of-service。似乎有相当多的代码容易受到这种攻击，因此决定在 Java 方面修复此问题。

有关详细信息，请参阅 JEP-180。

Answer 2

你的问题包含一些错误的前提。

1. 桶冲突不一定是散列冲突。两个对象不需要相同的哈希码就可以结束在同一个桶中。桶是数组的一个元素，哈希码必须映射到特定的索引。由于数组大小相对于 Map 的大小应该是合理的，因此您不能任意增加数组大小以避免桶冲突。甚至还有一个理论上的限制，即数组大小最大为 2³¹，而可能有 2³² 个哈希码。
2. 哈希冲突并不表示编程不好。对于值 space 大于 2³² 的所有对象，具有相同哈希码的不同对象的可能性是不可避免的。 String 是一个明显的例子，但即使 Point 带有两个 int 值或普通的 Long 键也不可避免地会发生哈希冲突。所以它们可能比你想象的更常见，这在很大程度上取决于用例。
3. 仅当存储桶中的碰撞次数超过特定阈值时，该实现才会切换到二叉树，因此只有在它们得到回报时才会应用更高的内存成本。关于它们的工作方式似乎存在普遍的误解。由于bucket碰撞不一定是hash碰撞，所以二分查找会先搜索hash码。只有当哈希码相同并且密钥适当地实现 Comparable 时，才会使用其自然顺序。您可能在 Web 上找到的示例故意对对象使用相同的哈希码来演示 Comparable 实现的使用，否则不会显示。他们触发的只是执行的最后手段。
4. 如, this issue might affect the security of a software as a slow fallback may open the possibility of DoS attacks. There have been several attempts in previous JRE versions to address this issue which had more drawbacks than the memory consumption of a binary tree. For example, there was an attempt to randomize the mapping of hash codes to array entries in Java 7 which caused an initialization overhead as documented in this bug report。这个新实现不是这种情况。