为什么 Java 8 中的哈希映射使用二叉树而不是链表? [英] Why hash maps in Java 8 use binary tree instead of linked list?

问题描述

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

I recently came to know that in Java 8 hash maps uses binary tree instead of linked list and hash code is used as the branching factor.I understand that in case of high collision the lookup is reduced to O(log n) from O(n) by using binary trees.My question is what good does it really do as the amortized time complexity is still O(1) and maybe if you force to store all the entries in the same bucket by providing the same hash code for all keys we can see a significant time difference but no one in their right minds would do that.

二叉树也比单链表使用更多的空间，因为它同时存储左右节点.除了一些虚假的测试用例外，时间复杂度绝对没有改善，为什么还要增加空间复杂度.

Binary tree also uses more space than singly linked list as it stores both left and right nodes.Why increase the space complexity when there is absolutely no improvement in time complexity except for some spurious test cases.

推荐答案

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

This is mostly security-related change. While in normal situation it's rarely possible to have many collisions, if hash keys arrive from untrusted source (e.g. HTTP header names received from the client), then it's possible and not very hard to specially craft the input, so the resulting keys will have the same hashcode. Now if you perform many look-ups, you may experience denial-of-service. It appears that there's quite a lot of code in the wild which is vulnerable to this kind of attacks, thus it was decided to fix this on the Java side.

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

For more information refer to JEP-180.

这篇关于为什么 Java 8 中的哈希映射使用二叉树而不是链表?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！