Java 8+ HashMap最坏时间复杂度及红黑树比较机制技术问询

问题背景 #

给定以下代码片段，所有Key实例的hashCode固定返回0，导致全量哈希冲突。Java 8及后续版本中，调用map.get(new Key(1))的时间复杂度是多少？同时延伸出三个关键问题：

import java.util.*;

class Key {
    int v;

    public Key(int v) {
        this.v = v;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Key key = (Key) o;
        return v == key.v;
    }

    @Override
    public int hashCode() {
        return 0; // 始终触发哈希冲突
    }
}

class Solution {
    public static void main(String[] args) {
        int n = 1_000_000;
        Map<Key, Integer> map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            Key key = new Key(i);
            map.put(key, i);
        }
        map.get(new Key(1)); // 该行的时间复杂度是多少？
    }
}

核心问题解答：map.get(new Key(1))的时间复杂度 #

初始回答O(log n)是基于Java 8+的红黑树优化，但实际情况需要结合键的比较逻辑细节判断：在示例场景中，由于Key未实现Comparable，且存在equals匹配但System.identityHashCode不同的情况，最坏时间复杂度会退化为O(n)，具体原因见后续问题解析。

Q1：Key未实现Comparable时，红黑树内部如何比较？ #

Java 8+ HashMap的红黑树节点遵循以下比较优先级：

1. 先比较键的hashCode值（键自身实现的hashCode方法返回值）；
2. 若hashCode相同，则使用System.identityHashCode()返回的对象标识哈希值比较；
3. 若System.identityHashCode也相同，会直接判断引用是否相等（==）；若仍不相等，底层会通过对象内存地址的隐式比较作为兜底逻辑，确保任意两个不同对象能被区分，维持红黑树的有序性。

Q2：equals相等但System.identityHashCode不同的键，get操作最坏时间复杂度是O(n)吗？ #

是的，这种场景下最坏时间复杂度会退化为O(n)：

• 红黑树的查找依赖节点的排序比较逻辑，当两个键equals相等但System.identityHashCode不同时，红黑树的比较逻辑无法将它们判定为“同一节点”；
• 此时查找操作需要遍历红黑树中所有hashCode相同的节点，逐一调用equals方法匹配目标键；
• 在示例中所有节点hashCode都为0，若目标键的System.identityHashCode与树中所有节点都不同，就需要遍历全部n个节点，时间复杂度变为O(n)。

注意：Java 8+ HashMap宣称的O(log n)最坏时间复杂度是有前提的——键需实现Comparable接口，或能通过hashCode+System.identityHashCode形成稳定的有序比较逻辑，避免大量equals匹配但比较逻辑无法区分的情况。

Q3：System.identityHashCode相同的不同键，如何插入红黑树？ #

当两个不同键的System.identityHashCode相同时，HashMap会通过以下逻辑保证红黑树的约束：

1. 首先判断两个键是否equals：若返回true，则视为重复键，插入操作会覆盖原有值；
2. 若equals返回false，即使System.identityHashCode相同，底层会使用对象的内存地址作为最终比较依据（通过Unsafe类获取对象内存偏移量实现）；
3. 这种兜底逻辑能确保任意两个不同对象都能被区分，从而维持红黑树的有序性，不会因System.identityHashCode冲突导致树结构无法构建。

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