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

hashmap java java-8

2022-09-03 04:12:42

我正在浏览java 8功能，发现当存储桶上的条目集数量增加时，哈希映射使用红色黑树而不是链接列表。

但是，这是否要求密钥具有可比性或密钥的某些排序才能存在，这是如何工作的？这种转换何时实际发生以及如何发生？

答案 1

当单个存储桶中至少有 8 个条目（）并且存储桶总数大于 64 （）时，该单个存储桶将转换为完全平衡的红色黑树节点。TREEIFY_THRESHOLDMIN_TREEIFY_CAPACITY

还有一个你应该注意的收缩（如果你愿意）当你删除条目时发生（ == 6）。UNTREEIFY_THRESHOLD

你是对的，键应该是 - 但这并不总是必需的，如果它们是好的（如果它们具有相同的），那就好了，但是如果它们不是，则使用：ComparablehashCode

 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 as a 用于比较，如果这也失败了，则使用（Marsaglia XOR-Shift 算法）来决定左边和右边。StringSystem.identityHashCode

当发生这种情况时回答您的问题 - 当调用调整大小时。当您必须调整大小时 - 发生了一些事情;就像桶的数量增加了两倍（如果条目将移动或不移动，则再考虑一位），或者将某个存储桶转换为树。这个过程（如果你真的在乎的话）非常慢，有人说Java HashMap是“sloooooooow，那么是快快快快的;然后是sloooooo，然后是快速快速“（我仍然认为这是嘲笑，但有实现）。HashMapPauselessHashMap

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

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

这将避免一些调整大小。

第二个是为什么转换为a很重要（想想数据库索引以及为什么它们是...）。您需要多少步骤才能在具有 INTEGER 的完美树中找到一个条目。MAX_VALUE条目（理论上）。最多只有 32 个。TreeBTREE

答案 2