何时以及如何将HashMap从链表转换为红黑树? [重复]

问题描述 投票:6回答:1

这个问题在这里已有答案:

我正在浏览java 8的功能,发现当桶上的条目集数量增加时,哈希映射使用红黑树而不是链表。

但是,这不是要求密钥是可比较的还是存在密钥的某些顺序,这是如何工作的?这种转换何时实际发生?如何?

java java-8 hashmap
1个回答
16
投票

当一个桶中至少有8个条目(TREEIFY_THRESHOLD)并且桶的总数超过64(MIN_TREEIFY_CAPACITY)时,那个桶将被转换为完美平衡的红黑树节点。

当您删除条目(UNTREEIFY_THRESHOLD == 6)时,您应该注意(如果需要)收缩。

你是正确的,键应该是Comparable - 但并不总是需要,如果它们是好的(如果它们具有相同的hashCode),但如果它们不是,则使用:

 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;
 }

所以className作为String用于比较,如果也失败,则使用System.identityHashCode(Marsaglia XOR-Shift算法)来决定左右。

当发生这种情况时回答你的问题 - 调用resize时。当你必须调整你的HashMap大小 - 有一些事情发生;比如桶的数量增加了两倍(在一个条目将移动或不移动的情况下再考虑一个比特)或某个桶被转换为树。这个过程(再次,如果你真的关心)是相当缓慢的,有些人说Java HashMap是“sloooooooow,然后是快速快速;然后它是sloooooo,然后它快速快速”(我仍然认为这是嘲弄,但那里是PauselessHashMap实现)。

这带来了两个有趣的观点。首先是选择你的Map的正确大小(即使粗略的估计会做),即:

 new HashMap<>(256); // choosing the size

这将避免一些调整大小。

第二个是为什么转换为Tree很重要(想想数据库索引以及为什么它们是BTREE ......)。在完美的树中找到具有INTEGER.MAX_VALUE条目的条目(理论上)需要多少步骤。最多32个。

© www.soinside.com 2019 - 2024. All rights reserved.