java - 当条目超过饱和级别时，Java 8 HashMap 中如何创建树

Question

这个问题已经有答案了:

HashMap Java 8 implementation (6 个回答)

已关闭 5 年前。

我正在浏览 java 8 中的 TreeNode 类。

static final class TreeNode<K, V> extends java.util.LinkedHashMap.Entry<K, V> {
    HashMap.TreeNode<K, V> parent;
    HashMap.TreeNode<K, V> left;
    HashMap.TreeNode<K, V> right;
    HashMap.TreeNode<K, V> prev;
    boolean red;

    TreeNode(int arg0, K arg1, V arg2, HashMap.Node<K, V> arg3) {
        super(arg0, arg1, arg2, arg3);
    }

当HashCode相同时将创建树，即所有哈希冲突键的存储桶将相同。那么当同一个桶中的条目超过8个时，如何创建红黑树呢？

Answer 1

在Java 8中，当桶中的元素数量达到一定阈值时，HashMap会用二叉树替换链表。

将列表转换为二叉树时，使用哈希码作为分支变量。

如果同一个桶中有两个不同的哈希码，一个被认为更大并位于树的右侧，另一个位于左侧。

但是当两个哈希码相等时，HashMap 假定键是可比较的，并比较键来确定方向，以便可以维持某种顺序。