未重写Key比较器时HashMap桶中红黑树的优化与构建机制

当HashMap的桶内元素数量超过阈值（默认是8）时，会从链表转成红黑树来提升查询效率。如果没有为Key指定自定义比较器，红黑树的排序逻辑会按以下规则处理：

• HashMap允许不同类型的Key共存，这些Key有的实现了Comparable接口（具备可比性），有的没有。排序时优先使用Key自身的compareTo方法（如果实现了该接口）；
• 当Key不可比较，或者用compareTo比较后结果相等时，会启用平局决胜逻辑来确定元素顺序——这是为了给红黑树提供稳定一致的排序规则，确保重平衡操作时能维持树的等价性，同时简化测试流程。

JDK中负责这个逻辑的核心方法是tieBreakOrder，代码及注释翻译如下：

/**
 * 当哈希码相等且Key不可比较时，用于确定插入顺序的平局决胜工具。
 * 我们不需要严格的全序，仅需一致的插入规则以在重平衡时保持等价性。
 * 额外的平局决胜逻辑可略微简化测试。
 */
static int tieBreakOrder(Object a, Object b) {
    int d;
    if (a == null || b == null ||
        (d = a.getClass().getName().
         compareTo(b.getClass().getName())) == 0)
        d = (System.identityHashCode(a) <= System.identityHashCode(b) ?
             -1 : 1);
    return d;
}

这个方法的逻辑拆解：

1. 先比较两个Key的类全限定名的字典序：类名不同时，按类名字典序排序，这样同一类的Key会被集中排列；
2. 如果类名相同（比如同一类的不同实例），则用System.identityHashCode的结果来比较——这个值是对象的原生哈希码，不会被重写，能保证同一类的实例有稳定的相对顺序；
3. 最终返回-1或1，确保每次比较结果一致，满足红黑树对排序稳定性的要求。

内容的提问来源于stack exchange，提问作者zahaand