HashMap何时以及如何将存储桶从链接列表转换为红黑树？

Question

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

但是，这是否不要求密钥具有可比性，或者是否要求密钥存在某种顺序，这是如何工作的？这种转换何时真正发生？如何发生？

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

因此，将className作为a String用于比较，如果也失败，则System.identityHashCode使用（MarsagliaXOR-Shift算法）确定 left 和 right 。

要回答您的问题，何时发生-何时调用调整大小。当您需要调整大小时HashMap-有些事情正在发生；例如存储桶的数量增加了两倍（考虑到条目将移动或不移动的更多位），或者某个存储桶被转换为树。这个过程（同样，如果您真的很在意）是非常缓慢的，有人说JavaHashMap是“sloooooooow，然后是快速快快；然后是sloooooooo，然后是快快快”（我仍然认为这是嘲笑，但是在那里是PauselessHashMap实现）。

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

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

这样可以避免调整大小。

第二个原因是为什么转换为aTree很重要（请考虑数据库索引以及它们为什么是BTREE…）。在理论上具有INTEGER.MAX_VALUE条目的完美树中查找条目将花费多少步骤。最多只能32个。