为什么HashMap使用TreeNode作为不可比较的键？

Question

我知道在Java 8 HashMap中针对分布不佳进行了优化hashCode.并且在超过阈值的情况下,它将桶中的节点从链表重建为树.此外,它表明这种优化不适用于不具有可比性的密钥(在性能方面没有得到改善).在下面的示例中,我没有放入Comparable密钥HashMap

import java.util.HashMap;
import java.util.Map;
import java.util.concurrent.TimeUnit;
import java.util.stream.IntStream;

class Main {
    public static void main(String[] args) throws InterruptedException {
        Map<Key, Integer> map = new HashMap<>();

        IntStream.range(0, 15)
                .forEach(i -> map.put(new Key(i), i));

        // hangs the application to take a Heap Dump
        TimeUnit.DAYS.sleep(1);
    }
}

final class Key {
    private final int i;

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

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

    @Override
    public int hashCode() {
        return 1;
    }
}

但是检查堆转储显示节点重新排列成树.

我的问题是,为什么节点会重建到树中,如果它不会提高性能,在这种情况下比较节点的哪个标准,找出哪个键应该是正确的节点,哪个键留下了？

Answer 1

我认为你有点误解了答案所说的.Comparable它不是必需的,它只是在哈希值相等时可以使用的优化 - 为了决定将条目移动到哪里 - 向左或向右(perfectly balanced red-black tree node).如果密钥不具有可比性,则会使用System.identityHashcode.

弄清楚哪个键应该是正确的节点,哪个键留下

它向右移动 - 更大的键向右移动,但树可能需要平衡.通常,您可以查找a Tree成为a 的确切算法perfectly balanced red black tree,就像这里一样