hashmap 树化部分 源码分析

HashMap的树化部分源码如下：

final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        resize();
    else if ((e = tab[index = (n - 1) & hash]) != null) {
        TreeNode<K,V> hd = null, tl = null;
        do {
            TreeNode<K,V> p = replacementTreeNode(e, null);
            if (tl == null)
                hd = p;
            else {
                p.prev = tl;
                tl.next = p;
            }
            tl = p;
        } while ((e = e.next) != null);
        if ((tab[index] = hd) != null)
            hd.treeify(tab);
    }
}

这部分代码主要是将一个桶中的链表转化为红黑树。具体步骤如下：

1. 如果数组为空或者长度小于MIN_TREEIFY_CAPACITY，调用resize()函数扩容数组；
2. 如果桶中的第一个元素不为空，将链表转化为红黑树；
3. 将链表中的每个节点都替换为TreeNode类型的节点，并将它们链接成双向链表；
4. 将双向链表转化为红黑树。

其中第3步中的replacementTreeNode()方法代码如下：

TreeNode<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> next) {
    return new TreeNode<>(p.hash, p.key, p.value, next);
}

该方法用于将普通节点转换为红黑树节点。最后一步中的treeify()方法代码如下：

final void treeify(Node<K,V>[] tab) {
    TreeNode<K,V> root = null;
    for (TreeNode<K,V> x = this, next; x != null; x = next) {
        next = (TreeNode<K,V>)x.next;
        x.left = x.right = null;
        if (root == null) {
            x.parent = null;
            x.red = false;
            root = x;
        }
        else {
            K k = x.key;
            int h = x.hash;
            Class<?> kc = null;
            for (TreeNode<K,V> p = root;;) {
                int dir, ph;
                K pk = p.key;
                if ((ph = p.hash) > h)
                    dir = -1;
                else if (ph < h)
                    dir = 1;
                else if ((kc == null &&
                          (kc = comparableClassFor(k)) == null) ||
                         (dir = compareComparables(kc, k, pk)) == 0)
                    dir = tieBreakOrder(k, pk);
                TreeNode<K,V> xp = p;
                if ((p = (dir <= 0) ? p.left : p.right) == null) {
                    x.parent = xp;
                    if (dir <= 0)
                        xp.left = x;
                    else
                        xp.right = x;
                    root = balanceInsertion(root, x);
                    break;
                }
            }
        }
    }
    moveRootToFront(tab, root);
}

该方法用于将双向链表转换为红黑树。具体步骤如下：

1. 创建一个root节点，将第一个节点作为root节点；
2. 遍历双向链表中的每个节点，将它们插入到红黑树中；
3. 在插入节点时，根据节点的hash值比较大小，将节点插入到左子树或右子树中；
4. 插入节点后，将红黑树进行平衡，保证红黑树的性质；
5. 将root节点移到数组的最前面，保证root节点在桶的第一个位置上。

总之，HashMap的树化部分主要是将链表转化为红黑树，以提高查询效率。