为什么Java8中的哈希映射使用二叉树而不是链表?
我最近了解到,在Java8中,哈希映射使用二叉树而不是链表,哈希代码被用作分支因子。我知道在高冲突的情况下,通过使用二叉树,查找会从O(n)减少到O(logn)。我的问题是,当摊销时间复杂度仍然是O(1)时,它真的有什么好处?如果你强制将所有条目存储在同一个存储桶中,为所有密钥提供相同的哈希代码,我们可以看到显著的时间差,但头脑正常的人不会这么做
二叉树也比单链表使用更多的空间,因为它同时存储左和右节点。除了一些虚假的测试用例,时间复杂度绝对没有任何改善,为什么还要增加空间复杂度呢
# 1 楼答案
这主要是与安全相关的变化。虽然在正常情况下,很少可能发生多次冲突,但如果散列密钥来自不受信任的源(例如,从客户端接收到的HTTP头名称),则可能也不太难专门处理输入,因此生成的密钥将具有相同的散列码。现在,如果执行多次查找,可能会遇到拒绝服务。似乎有相当多的代码在野外很容易受到这种攻击,因此决定在Java端解决这个问题
有关更多信息,请参阅JEP-180
# 2 楼答案
你的问题包含一些错误的前提
Map
的大小应该是合理的,所以不能随意提高数组大小以避免桶冲突。甚至还有一个理论上的限制,即当存在2个可能的哈希码时,数组大小可以最大为2%李>String
是一个明显的例子,但即使是带有两个int
值的Point
或普通的Long
键也不可避免地存在哈希冲突。所以它们可能比你想象的更常见,这在很大程度上取决于用例李>Comparable
时,才会使用其自然顺序。您可能在web上找到的示例故意对对象使用相同的哈希代码,以演示Comparable
实现的使用,否则就不会出现。它们触发的只是实施的最后手段李>