当许多密钥具有相同的哈希码时，Java 8的HashMap如何退化为平衡树？
当许多密钥具有相同的哈希码时，Java 8的HashMap如何退化为平衡树？ 我读到键应该实现Comparable来定义一个排序。 HashMap如何结合散列和自然排序来实现树？ 那些没有实现Comparable ，或者多个不可互相比较的Comparable实现是同一个映射中的键呢？
HashMap中的实现注释注释是对HashMap操作的更好描述，而不是我自己编写的。 理解树节点及其排序的相关部分是：
此映射通常用作分区（分区）哈希表，但是当分区变得太大时，它们将转换为TreeNodes的分区，每个分区的结构与java.util.TreeMap中的类似。 […] TreeNodes的Bins可以像其他任何一样遍历和使用，但是当人口过多时还支持更快的查找。 […]
树容器（即，其元素都是TreeNode的容器）主要由hashCode排序，但在tie的情况下，如果两个元素具有相同的“C类实现可比较”类型，则它们的compareTo方法用于排序。 （我们保守地通过reflection检查generics类型以validation这一点 – 请参阅方法equivalentClassFor ）。 当密钥具有不同的哈希值或可订购时，增加树容器的复杂性对于提供最坏情况的O（log n）操作是值得的。因此，在hashCode（）方法返回值很差的偶然或恶意用法中，性能会优雅地降级分布式，以及许多密钥共享hashCode的那些，只要它们也是可比较的。 （如果这些都不适用，与不采取任何预防措施相比，我们可能在时间和空间上浪费大约两倍。但是，唯一已知的情况源于糟糕的用户编程实践，这些实践已经非常缓慢，这几乎没有什么区别。）
当两个对象具有相同的哈希码但不能相互比较时，首先通过getClass().getName() （！）上的字符串比较调用方法tieBreakOrder来打破平局，然后通过比较System.identityHashCode 。
实际的树构建从treeifyBin开始，从bin到达TREEIFY_THRESHOLD （当前为8）开始，假设哈希表至少具有MIN_TREEIFY_CAPACITY容量（当前为64）。 这是一个大多数正常的红黑树实现（ 贷记CLR ），有一些复杂性来支持遍历，就像哈希箱一样（例如， removeTreeNode ）。
阅读代码 。 它主要是一棵红黑树 。
它实际上并不需要实现Comparable ，但如果可用则可以使用它（例如参见find方法 ）
HashMap有自己的哈希方法，它将补充的2位长度哈希应用于里面的对象，以避免这个问题：
将补充哈希函数应用于给定的hashCode，以防御质量差的哈希函数 。 这很关键，因为HashMap使用两个幂的长度哈希表，否则会遇到低位不同的hashCodes的冲突 。 注意：空键始终映射到散列0，因此索引为0。
如果你想看看它是如何完成的，看看是否在HashMap类的源代码中 。
static int hash(int h) { // This function ensures that hashCodes that differ only by // constant multiples at each bit position have a bounded // number of collisions (approximately 8 at default load factor). h ^= (h >>> 20) ^ (h >>> 12); return h ^ (h >>> 7) ^ (h >>> 4); }