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

Question

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

我最近才知道在Java 8哈希映射中使用二叉树而不是链表,并使用哈希代码作为分支因子.我知道在高冲突的情况下,查找从O(n)减少到O(log n)通过使用二叉树.我的问题是它真正做了什么好处,因为摊销的时间复杂度仍然是O(1)并且如果你强制通过为所有键提供相同的哈希码来存储同一桶中的所有条目可以看到一个显着的时间差异,但没有一个人在他们正确的思想中会这样做.

二进制树比单链表使用更多空间,因为它存储左右节点.当除了一些虚假测试用例之外,当时间复杂度完全没有改善时,为什么增加空间复杂度.

Answer 1

Tag*_*eev 22

这主要是与安全相关的变化.虽然在正常情况下很少有可能发生很多冲突,如果哈希密钥来自不受信任的来源(例如从客户端收到的HTTP头名称),那么可能并且不是很难专门设计输入,因此生成的密钥将具有相同的哈希码.现在,如果您执行许多查找,您可能会遇到拒绝服务.似乎在野外有相当多的代码容易受到这种攻击,因此决定在Java端解决这个问题.

有关更多信息,请参阅JEP-180.

@ user1613360,`String`的哈希函数是众所周知的和[记录](https://docs.oracle.com/javase/8/docs/api/java/lang/String.html#hashCode--),所以这不是一个大问题.每个Java实现都必须使用相同的功能. (2认同)
除了某些哈希码是固定的并且记录良好的事实之外,攻击者总是可以尝试找出服务器正在运行的特定版本,并查看如何计算特定类实现的哈希码.这就是大多数攻击的工作方式,首先,找出运行的软件,然后尝试针对特定软件和版本量身定制的适当漏洞. (2认同)

Answer 2

Hol*_*ger 17

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

一个水桶碰撞不一定是哈希冲突.您不需要为两个对象使用相同的哈希码来结束同一个存储桶.存储桶是数组的元素,并且哈希代码必须映射到特定索引.由于数组大小应该相对于大小合理Map,因此不能任意提高数组大小以避免存储桶冲突.甚至理论上的限制是阵列大小最大为2³¹,而有2 2,3可能的哈希码.
发生哈希冲突并不是编程错误的表现.对于值空间大于2³的所有对象,具有相同哈希码的不同对象的可能性是不可避免的.Strings是一个明显的例子,但即使是Point轴承两个int值或普通Long键也有不可避免的哈希冲突.所以它们可能比你想象的更常见,它在很大程度上取决于用例.
仅当存储桶中的冲突数超过某个阈值时,实现才会切换到二叉树,因此较高的内存成本仅在它们将获得回报时才适用.似乎有一个共同的误解,他们是如何工作的.由于桶冲突不一定是散列冲突,因此二进制搜索将首先搜索散列码.只有当哈希码相同且密钥适当实现时Comparable,才会使用其自然顺序.您可能在Web上找到的示例故意使用相同的对象哈希代码来演示实现的使用Comparable,否则将无法显示.他们触发的只是实施的最后手段.
正如Tagir所指出的,这个问题可能会影响软件的安全性,因为缓慢的后备可能会打开DoS攻击的可能性.在以前的JRE版本中已经有几次尝试来解决这个问题,这个问题比二叉树的内存消耗有更多的缺点.例如,尝试将哈希代码的映射随机化到Java 7中的数组条目,这导致初始化开销,如此错误报告中所述.这种新实现不是这种情况.

在此指出“桶碰撞”与“哈希碰撞”不一定相同。许多程序员错误地认为它们是同义词。 (4认同)
@Akanksha 也许，你没有足够仔细地阅读这个答案，尤其是第三点。通过将受影响的桶转换为哈希码上的二叉树来解决大量的*桶冲突*。这不需要键可以比较，哈希码是。仅对于大量实际散列冲突，即相同的散列代码，使用使用可比较实现的二叉树，*如果*键是可比较的，否则不。 (2认同)

归档时间：	10 年，3 月前
查看次数：	9044 次
最近记录：	10 年，3 月前