java HashMap何时以及如何将bucket从链表转换为红黑树？

Question

我浏览了Java8的特性，发现当bucket上的条目集数量增加时，hashmaps使用红黑树而不是linkedlist

然而，这难道不要求密钥具有可比性，或者密钥存在某种顺序吗？这是如何工作的？这种转换实际上是什么时候发生的，如何发生的

Answer 1

当单个bucket中至少有8个条目（TREEIFY_THRESHOLD）且bucket总数超过64（MIN_TREEIFY_CAPACITY）时，该单个bucket将被转换为一个完全平衡的红黑树节点

当删除条目（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;
 }

因此，将类名作为String用于比较，如果也失败了，则使用System.identityHashCode（Marsaglia异或移位算法）来决定左和右

当这种情况发生时——当调用resize时，回答您的问题。当你不得不调整你的HashMap时，会发生一些事情；与此类似，bucket的数量增加了两倍（在条目移动或不移动的情况下，还要考虑一位），或者某个bucket被转换为一棵树。这个过程（如果你真的在乎的话）非常慢，有些人说Java HashMap是“慢的，然后是快的；然后是慢的，然后是快的”（我仍然认为这是在嘲笑，但有PauselessHashMap实现）

这带来了两个有趣的观点。首先，最初选择Map的正确大小（即使是粗略估计也可以），即：

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

这将避免一些大小调整

第二个问题是为什么转换为Tree很重要（想想数据库索引，为什么它们是BTREE…）。在一棵完美的树中找到一个包含整数的条目需要多少步。最大值输入（理论上）。最多32个