为什么HashMap使用TreeNode作为不可比较的键？ [英] Why HashMap uses TreeNode for not Comparable keys?

问题描述

我知道在Java 8中 HashMap 针对分布不佳的 hashCode 进行了优化。在超过阈值的情况下，它会将存储桶中的节点从链表重建为树。此外，

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

解决方案

我认为你有点误解了答案所说的。 可比较不是需要，它只是在哈希值相等时可能会使用的优化 - 为了决定将条目移动到哪里 - 到向左或向右（完美平衡的红黑树节点）。如果密钥不可比，它将使用 System.identityHashcode 。

找出哪个键应该是正确的节点，哪个键是哪个键

它向右移动 - 更大的键去了在右边，但树可能需要平衡。 通常你可以查找树如何成为完全平衡的红黑树的确切算法，例如此处

I know that in Java 8 HashMap was optimized for poorly distributed hashCode. And in cases when threshold was exceeded it rebuilds nodes in bucket from linked list into tree. Also it is stated that this optimization doesn't work for not comparable keys (at leas performance is not improved). In the example below I put not Comparable keys into 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;
    }
}

But Inspecting the Heap Dump shows that nodes was rearrange into Tree.

My question is why nodes is rebuilt into the tree if it will not improve performance and on which criteria in this case nodes is compared to figure out which key should be right node and which left?

解决方案

I think that you sort of misunderstood what that answer was saying. Comparable is not needed, it's just an optimization that might be used when hashes are equal - in order to decide where to move the entry - to the left or to the right (perfectly balanced red-black tree node). Later if keys are not comparable, it will use System.identityHashcode.

figure out which key should be right node and which left

It goes to the right - the bigger key goes to the right, but then the tree might need to be balanced. Generally you can look-up the exact algorithm of how a Tree becomes a perfectly balanced red black tree, like here

这篇关于为什么HashMap使用TreeNode作为不可比较的键？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！