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

Question

<分区>

Answer 1

当单个桶中至少 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;
 }

因此作为 String 的 className 用于比较，如果也失败，则使用 System.identityHashCode(Marsaglia XOR-Shift 算法)来决定 < em>左 和右。

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

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

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

这将避免一些调整大小。

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