HashMap 何时以及如何将桶从链表转换为红黑树?

问题描述

我正在研究 Java 8 特性，发现当存储桶上的条目集数量增加时，哈希图使用红黑树而不是链表.

I was going through java 8 features and found out that hashmaps use a red black tree instead of a linkedlist when the number of entry sets on the bucket increases.

但是，这是否不需要密钥是 Comparable 或密钥的某种排序存在以及这是如何工作的?这种转换实际何时发生以及如何发生?

However, doesn't this require the key to be Comparable or some ordering of the keys to exist and how does this work ? When does this conversion actually happens and how ?

推荐答案

当一个桶中有至少 8个条目(TREEIFY_THRESHOLD)且总数量桶数大于 64 (MIN_TREEIFY_CAPACITY)，那么单个桶将被转换为完美平衡的红黑树节点.

When there are at least 8 entries (TREEIFY_THRESHOLD) in a single bucket and the total number of buckets is more then 64 (MIN_TREEIFY_CAPACITY) then that single bucket will be transformed to a perfectly balanced red black tree node.

当您删除条目 (UNTREEIFY_THRESHOLD == 6).

There is also the shrinkage that you should be aware of (if you want) that happens when you remove entries (UNTREEIFY_THRESHOLD == 6).

您是正确的，键应该是 Comparable - 但这并不总是必需的，如果它们是很好的(以防它们具有相同的 hashCode)，但是如果不是，则使用:

You are correct that keys should be Comparable - but that is not always required, it is good if they are (in case they have the same hashCode), but in case they are not, this is used:

 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 算法)来决定 左 和 右.

So the className as a String is used for comparison and if that fails too, then System.identityHashCode is used (Marsaglia XOR-Shift algorithm) to decide the left and right.

在发生这种情况时回答您的问题 - 调用调整大小时.当您必须调整 HashMap 的大小时 - 会发生一些事情；就像桶的数量增加了两倍(考虑到条目将移动或不移动的位置再增加一位)或某个桶被转换为一棵树.这个过程(如果你真的关心的话)非常慢，有人说 Java HashMap 是sloooooooow，然后是快快快；然后是 sloooooo，然后是快快快"(我仍然认为这是在嘲弄，但有是 PauselessHashMap 实现).

To answer you question when this happens - when resize is called. When you have to resize your HashMap - there are some things happening; like the number of buckets increases by a factor of two (one more bit is taken into consideration where an entry will move or not) or a certain bucket is transformed to a tree. This process (again if you really care) is pretty slow, some people say that a Java HashMap is "sloooooooow, then is fast fast fast; then it's sloooooo, then it's fast fast fast" (I still see this as mocking, but there are PauselessHashMap implementations).

这带来了两个有趣的点.首先是最初选择您的 Map 的正确大小(即使是粗略的估计也可以)，即:

This brings two interesting points. First is choose the correct size of your Map initially (even a rough estimation will do), i.e.:

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

这将避免一些调整大小.

this will avoid some resizes.

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

The second one is why transforming to a Tree is important (think database indexes and why they are BTREE...). How many steps it would take you to find an entry in a perfect tree that has INTEGER.MAX_VALUE entries (theoretically). Only up to 32.

这篇关于HashMap 何时以及如何将桶从链表转换为红黑树?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！