为什么Java 8中的哈希映射使用二叉树而不是链表？[已关闭]

这主要是与安全相关的更改。虽然在正常情况下，很少可能发生许多冲突，但如果哈希键来自不受信任的源（例如，从客户端接收的HTTP标头名称），那么特制输入是可能的，并且不是很难，因此生成的键将具有相同的哈希码。现在，如果您执行许多查找，则可能会遇到拒绝服务。似乎有很多代码容易受到这种攻击，因此决定在Java方面解决这个问题。

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

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

1. 存储桶冲突不一定是哈希冲突。您不需要使用相同的哈希代码即可使两个对象最终位于同一存储桶中。存储桶是数组的元素，哈希代码必须映射到特定索引。由于数组大小相对于 的大小应该是合理的，因此不能任意提高数组大小以避免存储桶冲突。甚至存在理论限制，即数组大小最大可以为 2³¹，而可能有 2³² 的哈希代码。Map
2. 哈希冲突并不是编程不良的迹象。对于值空间大于 2³² 的所有对象，不可避免地会出现具有相同哈希代码的不同对象。s是一个明显的例子，但即使是带有两个值或一个普通键也不可避免地会产生哈希冲突。因此，它们可能比您想象的更常见，这在很大程度上取决于用例。StringPointintLong
3. 仅当存储桶中的冲突次数超过某个阈值时，实现才会切换到二叉树，因此较高的内存成本仅在它们得到回报时才适用。对于它们的工作方式似乎存在一个常见的误解。由于存储桶冲突不一定是哈希冲突，因此二进制搜索将首先搜索哈希代码。只有当哈希码相同并且密钥正确实现时，才会使用其自然顺序。您可能在 Web 上找到的示例故意对对象使用相同的哈希代码来演示实现的使用，否则这些实现将不会显示出来。它们触发的只是实现的最后手段。ComparableComparable
4. 正如Tagir所指出的，这个问题可能会影响软件的安全性，因为缓慢的回退可能会打开DoS攻击的可能性。在以前的 JRE 版本中，已经多次尝试解决此问题，其缺点比二叉树的内存消耗更多。例如，有人试图将哈希代码映射到 Java 7 中的数组条目随机化，这导致了初始化开销，如此 bug 报告中所述。此新实现并非如此。