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

HashMap中的实现注释注释是对HashMap操作的更好描述，而不是我自己写的。了解树节点及其排序的相关部分是：

此映射通常充当装箱（桶装）哈希表，但是当箱子变得太大时，它们会转换为 TreeNodes 的条柱，每个箱子的结构类似于 java.util.TreeMap 中的条柱。[...]树节点的箱可以像其他任何一样遍历和使用，但在过度填充时还支持更快的查找。[...]

树箱（即，其元素都是TreeNodes的箱）主要按哈希码排序，但在联系的情况下，如果两个元素具有相同的“类C实现可比”类型，则它们的compareTo方法用于排序。（我们通过反射保守地检查泛型类型以验证这一点 - 请参阅方法ableClassFor）。当键具有不同的哈希或可排序时，树箱的复杂性在提供最坏情况下的O（log n）操作是值得的，因此，在意外或恶意用法下，性能会优雅地下降，其中hashCode（）方法返回分布不良的值，以及许多键共享哈希码的那些，只要它们也是可比较的。（如果这些都不适用，与不采取任何预防措施相比，我们可能会在时间和空间上浪费大约两倍的时间。但唯一已知的案例源于糟糕的用户编程实践，这些实践已经非常慢，以至于这几乎没有区别。

当两个对象具有相等的哈希代码但不相互比较时，将调用方法 tieBreakOrder 来打破关系，首先通过字符串比较 （！），然后通过比较 。getClass().getName()System.identityHashCode

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

阅读代码。它主要是一棵红黑色的树。

它实际上不需要 实现 ，但如果可用，可以使用它（例如，请参阅 find 方法Comparable)