当许多键具有相同的哈希码时，Java 8 的 HashMap 如何退化为平衡树？我读到密钥应该实现Comparable定义排序。 HashMap如何结合散列和自然排序来实现树？没有实现的类怎么办Comparable，或者当多个、不可相互比较时Comparable实现是同一个映射中的键吗？
The 实施说明评论 http://hg.openjdk.java.net/jdk8u/jdk8u/jdk/file/a006fa0a9e8f/src/share/classes/java/util/HashMap.java#l143HashMap 中对 HashMap 操作的描述比我自己写的更好。理解树节点及其排序的相关部分是：
该映射通常充当分箱（分桶）哈希表，但当分箱变得太大时，它们会转换为 TreeNode 的分箱，每个结构与 java.util.TreeMap 中的结构类似。 [...] TreeNodes 的 bin 可以像其他任何节点一样被遍历和使用，而且在填充过多时还支持更快的查找。 [...]
Tree bins（即，其元素都是 TreeNodes 的 bins）主要通过 hashCode 排序，但在关系的情况下，如果两个元素属于相同的“C 类实现 Comparable”类型，则使用它们的compareTo 方法进行排序。 （我们通过反射保守地检查泛型类型以验证这一点 - 请参阅方法可比类 http://hg.openjdk.java.net/jdk8u/jdk8u/jdk/file/a006fa0a9e8f/src/share/classes/java/util/HashMap.java#l341）。当键具有不同的哈希值或可排序时，树箱的增加的复杂性在提供最坏情况的 O(log n) 操作方面是值得的，因此，在意外或恶意使用情况下，性能会适度下降，其中 hashCode() 方法返回的值很差分布式的，以及许多键共享 hashCode 的那些，只要它们也是可比较的。 （如果这些都不适用，与不采取预防措施相比，我们可能会在时间和空间上浪费大约两倍。但唯一已知的情况源于不良的用户编程实践，这些实践已经很慢，以至于几乎没有什么区别。）
当两个对象的哈希码相等但不能相互比较时，方法tieBreakOrder http://hg.openjdk.java.net/jdk8u/jdk8u/jdk/file/a006fa0a9e8f/src/share/classes/java/util/HashMap.java#l1876被调用来打破平局，首先通过字符串比较getClass().getName()(!)，然后通过比较System.identityHashCode.
实际的树构建开始于treeifyBin http://hg.openjdk.java.net/jdk8u/jdk8u/jdk/file/a006fa0a9e8f/src/share/classes/java/util/HashMap.java#l750，当垃圾箱到达时开始TREEIFY_THRESHOLD http://hg.openjdk.java.net/jdk8u/jdk8u/jdk/file/a006fa0a9e8f/src/share/classes/java/util/HashMap.java#l249（当前为 8），假设哈希表至少有MIN_TREEIFY_CAPACITY http://hg.openjdk.java.net/jdk8u/jdk8u/jdk/file/a006fa0a9e8f/src/share/classes/java/util/HashMap.java#l266容量（当前 64）。这是一个最正常的红黑树实现（记入CLR http://hg.openjdk.java.net/jdk8u/jdk8u/jdk/file/a006fa0a9e8f/src/share/classes/java/util/HashMap.java#l2168），但有一些复杂性需要以与散列箱相同的方式支持遍历（例如，removeTreeNode http://hg.openjdk.java.net/jdk8u/jdk8u/jdk/file/a006fa0a9e8f/src/share/classes/java/util/HashMap.java#l2005).
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
