当许多密钥具有相同的哈希代码时，Java 8的HashMap如何退化为平衡树？ [英] How does Java 8's HashMap degenerate to balanced trees when many keys have the same hash code?
问题描述
当许多密钥具有相同的哈希代码时，Java 8的HashMap如何退化为平衡树？我读过这些键应该实现 Comparable 来定义一个排序。 HashMap如何将散列和自然排序结合起来实现这些树？那些没有实现 Comparable 的类，或者当多个不可相互比较的 Comparable 实现是关键字时同样的地图？
HashMap中的实现注释注释是我可以自己写的更好的HashMap操作描述。理解树节点及其排序的相关部分是：
lockquote
这个映射通常作为一个binned（bucketed）哈希表，但是当垃圾箱变得太大，它们被转换成TreeNodes的箱子，每个箱子的结构与java.util.TreeMap中的相似。 [...] TreeNodes的bin可以像其他任何地方一样遍历和使用，但是当人口过剩时还支持更快的查找。 [b]
树元素（即元素都是TreeNode的元素）主要由hashCode来排序，但在关系的情况下，如果两个元素是相同的C类实现Comparable类型，然后使用它们的compareTo方法进行排序。 （我们通过反射保守地检查泛型以验证这一点 - 参见 comparableClassFor ）。当密钥具有不同的哈希值或可订购时，提供最坏情况下的O（log n）操作是增值的，因此，在意外或恶意使用情况下，hashCode（）方法返回的值不佳分布式以及许多密钥共享一个hashCode，只要它们也是Comparable。 （如果两者都不适用，那么与未采取任何预防措施相比，我们可能浪费大约两倍的时间和空间，但唯一已知的情况源自不良用户编程实践，这些实践已经非常缓慢，几乎没有什么区别。） p>
当两个对象具有相同的哈希码但不相互可比时，方法 tieBreakOrder 被调用打破领带，首先通过字符串比较 getClass（）。getName（）（！），然后通过比较 System.identityHashCode 。
实际的树状结构始于 treeifyBin ，当bin达到 TREEIFY_THRESHOLD net / jdk8u / jdk8u / jdk / file / a006fa0a9e8f / src / share / classes / java / util / HashMap.java＃l266> MIN_TREEIFY_CAPACITY 容量64）。这是一个大部分正常的红黑树实现（记入CLR ），并以一些复杂的方式支持遍历，就像散列箱一样（例如 removeTreeNode ）。
How does Java 8's HashMap degenerate to balanced trees when many keys have the same hash code? I read that keys should implement Comparable to define an ordering. How does HashMap combine hashing and natural ordering to implement the trees? What about classes that do not implement Comparable, or when multiple, non-mutually-comparable Comparable implementations are keys in the same map?
The implementation notes comment in HashMap is a better description of HashMap's operation than I could write myself. The relevant parts for understanding the tree nodes and their ordering are:
This map usually acts as a binned (bucketed) hash table, but when bins get too large, they are transformed into bins of TreeNodes, each structured similarly to those in java.util.TreeMap. [...] Bins of TreeNodes may be traversed and used like any others, but additionally support faster lookup when overpopulated. [...]
Tree bins (i.e., bins whose elements are all TreeNodes) are ordered primarily by hashCode, but in the case of ties, if two elements are of the same "class C implements Comparable" type then their compareTo method is used for ordering. (We conservatively check generic types via reflection to validate this -- see method comparableClassFor). The added complexity of tree bins is worthwhile in providing worst-case O(log n) operations when keys either have distinct hashes or are orderable, Thus, performance degrades gracefully under accidental or malicious usages in which hashCode() methods return values that are poorly distributed, as well as those in which many keys share a hashCode, so long as they are also Comparable. (If neither of these apply, we may waste about a factor of two in time and space compared to taking no precautions. But the only known cases stem from poor user programming practices that are already so slow that this makes little difference.)
When two objects have equal hash codes but are not mutually comparable, method tieBreakOrder is invoked to break the tie, first by string comparison on getClass().getName() (!), then by comparing System.identityHashCode.
The actual tree building starts in treeifyBin, beginning when a bin reaches TREEIFY_THRESHOLD (currently 8), assuming the hash table has at least MIN_TREEIFY_CAPACITY capacity (currently 64). It's a mostly-normal red-black tree implementation (crediting CLR), with some complications to support traversal in the same way as hash bins (e.g., removeTreeNode).
这篇关于当许多密钥具有相同的哈希代码时，Java 8的HashMap如何退化为平衡树？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
