HashMap何时以及如何将存储区从链接列表转换为红黑树？ [英] When and how does HashMap convert the bucket from linked list to Red Black Trees?

问题描述

我正在浏览java 8特性，并发现hashmaps使用红黑树而不是链表，当bucket中的入口集数量增加时。然而，这不需要钥匙是可比较的，还是需要对钥匙进行一些排序，以及它是如何工作的？什么时候这个转换实际发生了，怎么做？

解决方案

当至少 code> 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; 
 
 $ / code> 

所以className作为 String 用于比较，如果失败，则使用 System.identityHashCode （Marsaglia XOR-Shift算法）来决定 left 和。

。

在这种情况发生时回答您的问题 - 调用resize时。当你不得不调整你的 HashMap 时 - 会发生一些事情;就像桶的数量增加2倍一样（在入口将移动或不移动时会考虑另外一个位），或者某个桶被转换为树。这个过程（如果你真的关心的话）速度很慢，有些人说Java HashMap是很慢很快，然后快速快速;然后它很慢，然后快速快速（我仍然认为这是嘲弄，但是在那里是 PauselessHashMap 的实现）。

这带来了两个有趣的观点。首先是在开始时选择正确的 Map 大小（即使是粗略的估算），即：

 新的HashMap<>（256）; //选择大小
  

这样可以避免一些大小变化。

第二个原因是为什么转换为 Tree 是很重要的（认为数据库索引以及为什么它们是 BTREE ...）。需要多少步才能在具有INTEGER.MAX_VALUE条目（理论上）的完美树中找到条目。只能达到32元。

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.

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 ?

解决方案

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.

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

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

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.

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).

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.

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何时以及如何将存储区从链接列表转换为红黑树？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！