java - 当许多键具有相同的哈希码时，Java 8 的 HashMap 如何退化为平衡树？

Question

当许多键具有相同的哈希码时，Java 8 的 HashMap 如何退化为平衡树？我读到键应该实现 Comparable 来定义排序。 HashMap 如何结合散列和自然排序来实现树？没有实现 Comparable 的类，或者当多个不可相互比较的 Comparable 实现是同一个映射中的键时，该怎么办？

Answer 1

implementation notes comment in HashMap 比我自己写的更好地描述了 HashMap 的操作。了解树节点及其排序的相关部分是:

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

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

实际的树构建开始于 treeifyBin , 从 bin 到达 TREEIFY_THRESHOLD 时开始(目前为 8 个)，假设哈希表至少有 MIN_TREEIFY_CAPACITY容量(目前为 64)。这是一个最普通的红黑树实现( crediting CLR )，支持以与哈希箱相同的方式遍历的一些复杂性(例如，removeTreeNode )。