侧边栏壁纸
  • 累计撰写 98 篇文章
  • 累计创建 20 个标签
  • 累计收到 3 条评论

HashMap之红黑树原理探究

林贤钦
2020-06-29 / 0 评论 / 10 点赞 / 599 阅读 / 0 字
温馨提示:
本文最后更新于 2020-06-29,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

HashMap之红黑树原理探究

HashMap基础原理和数据结构的红黑树这里不解释,详情看我博客的《数据结构--红黑树》《HashMap原理探究

HashMap转红黑树的必要条件:

  • 数组长度>64且链表长度大于8

1、节点的基本信息

红黑树节点继承LinkedHashMap的Entry,Entry继承HashMap的Node

Map.TreeNode

static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
    TreeNode<K,V> parent;  // red-black tree links
    TreeNode<K,V> left;
    TreeNode<K,V> right;
    TreeNode<K,V> prev;    // needed to unlink next upon deletion
    boolean red;
    TreeNode(int hash, K key, V val, Node<K,V> next) {
        super(hash, key, val, next);
    }
}

LinkedHashMap.Entry

static class Entry<K,V> extends HashMap.Node<K,V> {
    Entry<K,V> before, after;
    Entry(int hash, K key, V value, Node<K,V> next) {
        super(hash, key, value, next);
    }
}

Map.Entry

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;

    Node(int hash, K key, V value, Node<K,V> next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }
}    

2、所有添加的操作最终都由这个方法完成。

与红黑树相关在putVal这只有两个地方

  • // 如果当前的bucket里面已经是红黑树的话,执行红黑树的添加操作
    e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
  • // TREEIFY_THRESHOLD = 8,判断如果当前bucket的位置链表长度大于8的话就将此链表变成红黑树。在treeifyBin方法里判断如果小于64,就扩容
    if (binCount >= TREEIFY_THRESHOLD - 1) treeifyBin(tab, hash);
/**
 * Implements Map.put and related methods
 * 实现Map.put和相关方法
 * @param hash hash for key   哈希
 * @param key the key   	键
 * @param value the value to put	值  
 * @param onlyIfAbsent if true, don't change existing value  如果为true,则不要更改现有值
 * @param evict if false, the table is in creation mode.   如果为false,则表处于创建模式。
 * @return previous value, or null if none  先前的值;如果没有,则为null
 */
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        else if (p instanceof TreeNode)
            // 如果当前的bucket里面已经是红黑树的话,执行红黑树的添加操作
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    // TREEIFY_THRESHOLD = 8,判断如果当前bucket的位置链表长度大于8的话就将此链表变成红黑树。
                    // 在treeifyBin方法里判断如果小于64,就扩容
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

3、树化准备

这个treefyBin方法先判断传过来的tab数组是否为空或者长度小于64,如果是就进行扩容,否则就根据hash获取相对应数组的链表,再将node链表转化成红黑树的链表TreeNode,最后调用链表头hd的树化方法treeify进行树化。

/**
 * Replaces all linked nodes in bin at index for given hash unless
 * table is too small, in which case resizes instead.
 * 除非给定表太小,否则将替换给定哈希值的索引中bin中所有链接的节点,在这种情况下,将调整大小。
 */
final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
    //如果table数组为空,或者数组的长度小于64,就进行扩容,不进行树化
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        resize();
    //通过hash求出bucket的位置。
    else if ((e = tab[index = (n - 1) & hash]) != null) {
        //hd为TreeNode链表的头部,tl为链表的尾部
        TreeNode<K,V> hd = null, tl = null;
        do {
            //将每个Node<K,V> e转成--->TreeNode<K,V> p
            TreeNode<K,V> p = replacementTreeNode(e, null);
            if (tl == null)
                hd = p;
            else {
                //将获取到p节点接在tl尾部
                p.prev = tl;
                tl.next = p;
            }
            //令tl置为链表尾部
            tl = p;
            //e=e.next 不断遍历,添加
        } while ((e = e.next) != null);
        if ((tab[index] = hd) != null)
             //当链表的=头部不为null的时候,就进行树化
            hd.treeify(tab);
    }
}

4、树化过程

树化过程就是将上面的treeNode链表结构转化成红黑树结构,根据hash得到对应的位置,放入红黑树中,然后再调用balanceInsertion维护红黑树的结构

/**
 * Forms tree of the nodes linked from this node.
 * 从该节点链接的节点的表单树。
 * @return root of tree
 */
final void treeify(Node<K,V>[] tab) {
    TreeNode<K,V> root = null;
     // 以for循环的方式遍历刚才我们创建的链表。this指的是前面的hd链表头部,x保存当前节点
    for (TreeNode<K,V> x = this, next; x != null; x = next) {
        //next保存下一个指针
        next = (TreeNode<K,V>)x.next;
        //将x的左右子树初始化为null
        x.left = x.right = null;
        //如果根节点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;;) {
                // dir:directory,比较添加项与当前树中访问节点的hash值判断加入项的路径,-1为左子树,+1为右子树。
                int dir, ph;
                K pk = p.key;
                //父节点的hash>当前节点的哈希值比较,则为-1.否则为1
                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);
				//xp保存父节点信息,p判断保存父节点xp的左子树或者右子树
                TreeNode<K,V> xp = p;
                if ((p = (dir <= 0) ? p.left : p.right) == null) {
                    //将x的父节点设为xp
                    x.parent = xp;
                    if (dir <= 0)
                         //将xp的左子节点设为x
                        xp.left = x;
                    else
                         //将xp的右子节点设为x
                        xp.right = x;
                    //维护红黑树的结构
                    root = balanceInsertion(root, x);
                    break;
                }
            }
        }
    }
    //确保根节点为数组索引到的第一个节点,也就是之前链表的第一个元素hd
    moveRootToFront(tab, root);
}

5、维护红黑树的结构

static <K, V> TreeNode<K, V> balanceInsertion(TreeNode<K, V> root, TreeNode<K, V> x)
{
    // 正如开头所说,新加入树节点默认都是红色的,不会破坏树的结构。
    x.red = true;
    // 这些变量名不是作者随便定义的都是有意义的。
    // xp:x parent,代表x的父节点。
    // xpp:x parent parent,代表x的祖父节点
    // xppl:x parent parent left,代表x的祖父的左节点。
    // xppr:x parent parent right,代表x的祖父的右节点。
    for (TreeNode<K, V> xp, xpp, xppl, xppr;;)
    {
        // 如果x的父节点为null说明只有一个节点,该节点为根节点,根节点为黑色,red = false。
        if ((xp = x.parent) == null)
        {
            x.red = false;
            return x;
        } 
        // 进入else说明不是根节点。
        // 如果父节点是黑色,那么大吉大利(今晚吃鸡),红色的x节点可以直接添加到黑色节点后面,返回根就行了不需要任何多余的操作。
        // 如果父节点是红色的,但祖父节点为空的话也可以直接返回根此时父节点就是根节点,因为根必须是黑色的,添加在后面没有任何问题。
        else if (!xp.red || (xpp = xp.parent) == null)
            return root;

        // 一旦我们进入到这里就说明了两件是情
        // 1.x的父节点xp是红色的,这样就遇到两个红色节点相连的问题,所以必须经过旋转变换。
        // 2.x的祖父节点xpp不为空。

        // 判断如果父节点是否是祖父节点的左节点
        if (xp == (xppl = xpp.left))
        {
            // 父节点xp是祖父的左节点xppr
            // 判断祖父节点的右节点不为空并且是否是红色的
            // 此时xpp的左右节点都是红的,所以直接进行上面所说的第三种变换,将两个子节点变成黑色,将xpp变成红色,然后将红色节点x顺利的添加到了xp的后面。
            // 这里大家有疑问为什么将x = xpp?
            // 这是由于将xpp变成红色以后可能与xpp的父节点发生两个相连红色节点的冲突,这就又构成了第二种旋转变换,所以必须从底向上的进行变换,直到根。
            // 所以令x = xpp,然后进行下下一层循环,接着往上走。
            if ((xppr = xpp.right) != null && xppr.red)
            {
                xppr.red = false;
                xp.red = false;
                xpp.red = true;
                x = xpp;
            }
            // 进入到这个else里面说明。
            // 父节点xp是祖父的左节点xppr。
            // 祖父节点xpp的右节点xppr是黑色节点或者为空,默认规定空节点也是黑色的。
            // 下面要判断x是xp的左节点还是右节点。
            else
            {
                // x是xp的右节点,此时的结构是:xpp左->xp右->x。这明显是第二中变换需要进行两次旋转,这里先进行一次旋转。
                // 下面是第一次旋转。
                if (x == xp.right)
                {
                    root = rotateLeft(root, x = xp);
                    xpp = (xp = x.parent) == null ? null : xp.parent;
                }
                // 针对本身就是xpp左->xp左->x的结构或者由于上面的旋转造成的这种结构进行一次旋转。
                if (xp != null)
                {
                    xp.red = false;
                    if (xpp != null)
                    {
                        xpp.red = true;
                        root = rotateRight(root, xpp);
                    }
                }
            }
        } 
        // 这里的分析方式和前面的相对称只不过全部在右测不再重复分析。
        else
        {
            if (xppl != null && xppl.red)
            {
                xppl.red = false;
                xp.red = false;
                xpp.red = true;
                x = xpp;
            } else
            {
                if (x == xp.left)
                {
                    root = rotateRight(root, x = xp);
                    xpp = (xp = x.parent) == null ? null : xp.parent;
                }
                if (xp != null)
                {
                    xp.red = false;
                    if (xpp != null)
                    {
                        xpp.red = true;
                        root = rotateLeft(root, xpp);
                    }
                }
            }
        }
    }
}

6、左旋右旋过程

进入左旋右旋的必要条件:

  1. 父节点为红色,叔叔节点为黑色或空
  2. 祖父节点不为空,且为黑色(这个必然,因为两个红色不能连在一起)

所以有四种情况,LL红色情况,LR红色情况,RR红色情况,RL红色情况

左旋

//左旋
private <K,V>Node<K,V> rotateLeft(Node<K,V> root,Node<K,V>p){
    //定义当前p节点的右节点r,右节点r的左节点rl,当前节点p的父节点pp
    Node<K,V>r,rl,pp;
    //->1.如果当前节点p不为null;2.r=p.right 3.p节点的右节点r不为空!;
    if (p!=null&&(r=p.right)!=null){
        //1.rl=r.left;2.当前节点的右节点指向r的左节点p.right=r.left;3.rl!=null如果不为空,走里面
        if ((rl=p.right=r.left)!=null)
            //不为空就将rl的父节点指向p
            rl.parent=p;
        //1.pp=r.parent;2.r.parent=p.parent3.如果pp为空,走里面
        if ((pp=r.parent=p.parent)==null)
            //如果pp为空,根节点指向r,2.颜色定义为false,也就是黑色
            (root=r).red=false;
            //如果p是pp的左节点,pp的左节点指向r
        else if (pp.left==p)
            pp.left=r;
            //如果p是pp的右节点,pp的右节点指向r
        else
            pp.right=r;
        //r的左节点指向p
        r.left=p;
        //p的父节点指向r
        p.parent=r;
    }
    return root;
}

右旋

//右旋
private  <K,V>Node<K,V> rotateRight(Node<K,V>root,Node<K,V>p){
    Node<K,V> l,lr,pp;
    if (p!=null&&(l=p.left)!=null){
        if ((lr=p.left=l.right)!=null)
            lr.parent=p;
        if ((pp=l.parent=p.parent)==null)
            (root=l).red=false;
        else if (pp.left==p)
            pp.left=l;
        else
            pp.right=l;
        l.right=p;
        p.parent=l;
    }
    return root;
}

以上就是hashMap的链表转红黑树的过程。具体细节这里就没详细说,详情参考我另外的博客文章

10

评论区