当许多键具有相同的哈希码时，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 实现是同一个映射中的键时，该怎么办?

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?

推荐答案

实现注释注释 比我自己写的更好地描述了 HashMap 的操作.理解树节点及其排序的相关部分是:

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:

该映射通常用作分箱(分桶)哈希表，但是当分箱过大时，它们会被转换为 TreeNode 的分箱，每个分箱的结构类似于 java.util.TreeMap 中的分箱.[...] TreeNodes 的 bins 可以像任何其他 bins 一样被遍历和使用，但另外支持在人口过多时更快的查找.[...]

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. [...]

树箱(即所有元素都是 TreeNode 的箱)主要按 hashCode 排序，但在 tie 的情况下，如果两个元素属于相同的C 类实现 Comparable"type 然后他们的 compareTo 方法用于排序.(我们通过反射保守地检查泛型类型以验证这一点——参见方法 comparableClassFor).当键具有不同的散列或可排序时，树箱的增加的复杂性值得提供最坏情况的 O(log n) 操作，因此，在 hashCode() 方法返回的值很差的意外或恶意使用下，性能会优雅地降低分布式，以及其中许多键共享一个 hashCode 的那些，只要它们也是 Comparable 的.(如果这些都不适用，与不采取预防措施相比，我们可能会在时间和空间上浪费大约两倍的时间.但唯一已知的情况源于糟糕的用户编程实践，这些实践已经很慢，这几乎没有什么区别.)

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.)

当两个对象具有相同的哈希码但不能相互比较时，方法 tieBreakOrder 被调用来打破平局，首先通过 getClass().getName() 上的字符串比较 (!)，然后通过比较System.identityHashCode.

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.

实际的树构建开始于 treeifyBin，当一个 bin 到达 TREEIFY_THRESHOLD(当前为 8)，假设哈希表至少有 MIN_TREEIFY_CAPACITY 容量(当前为 64).这是一个大多数正常的红黑树实现(信用 CLR)，以与散列箱相同的方式支持遍历有一些复杂性(例如，removeTreeNode).

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屋！