在Java 8之后，HashMap的最坏情况下时间复杂度仍然是O(n)而不是O(log n)

今天，我遇到了一个与Java HashMaps有关的面试问题，我想澄清一些关于Java 8和更高版本中某些操作的时间复杂性和关键比较的问题.

给出下面的代码片段，考虑到Java 8对HashMap的改进，这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; // always hash collision
    }
}

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)); // What's the time complexity of this line?
    }
}

我最初的回答是O(log n)，提到Java 8自动将bucket中的冗长链表转换为红黑树，以提高效率.

Q1:然而，面试官随后询问了how comparison is done within the RB Tree when the Key class doesn't implement the 100 interface.

我回答说，hashCode首先用于比较，因为即使在同一个桶中，它也只意味着h1 % length == h2 % length.在进一步询问哈希代码相同的情况下，我提到了System.identityHashCode的用法.我的答案和https://stackoverflow.com/a/43911638/10969942一样

Q2:这引发了关于the case where two keys are 100 but likely have different 101 values:的讨论

Key k1 = new Key(1); 
Key k2 = new Key(1);

我推测这可能需要遍历子树中的所有条目，使用相同的哈希代码.Then the interviewer asked whether it means that the worst case time complexity is O(n)? I don't know since I always heard that after Java8, HashMap can have guaranteed worst case O(log n) time complexity.

Q3:然后，采访者询问如何将两个具有相同System.identityHashCode的不同密钥插入到映射中，假定RB树不允许重复密钥:

Key k1 = new Key(1); // same identityHashCode
Key k2 = new Key(2); // same identityHashCode

我记得不同的对象有可能有相同的System.identityHashCode https://stackoverflow.com/a/1063100/10969942，但我不清楚HashMap如何管理这些插入而不违反RB树的约束，即处理hashCode和identityHashCode冲突.