HashMap1.8 源码解析(3)--TreeNode(红黑树

完整代码:代码

前言

在写这篇文章之前,我针对红黑树参考算法导论写了一篇文章图解红黑树-算法导论-java实现基于HashMap1.8,里面的的插入和删除以及旋转就是用的HashMap1.8里面的代码,所以里面细致地分析了balanceDeletion,balanceInsertion,rotateLeft,rotateRight,那这篇主要分析TreeNode中去其他的方法以及一些HashMap中TreeNode新加入的属性和操作.

往红黑树中插入元素 putTreeVal方法

在看putTreeVal方法前,先看这几个函数,因为putTreeVal在函数体中有调用这几个函数

comparableClassFor方法

 /**
     * 
     * @param x 对象x
     * @return 如果x所属的类实现了Comparable<T>接口,并且T是x类 比如 class Person implements Comparable<Person>
     *         如果class Person 或者类似于 class Person implements Comparable 或者 class Person implements Comparable<String>都会返回null
     */
    static Class<?> comparableClassFor(Object x) {
        if (x instanceof Comparable) {
            Class<?> c; Type[] ts, as; Type t; ParameterizedType p;
            if ((c = x.getClass()) == String.class) // 如果是String类直接返回了
                return c;
            /**
             * getGenericInterfaces():
             *       Returns the Types representing the interfaces directly implemented
             *       by the class or interface represented by this object.
             * 就是返回c类实现的所有接口
             */
            if ((ts = c.getGenericInterfaces()) != null) {   
                for (int i = 0; i < ts.length; ++i) {
                        /**
                         *  Comparable<Person> 如果此接口含有泛型 并且原型class是Compable类
                         *  getActualTypeArguments() 返回这个类里面所有的泛型 返回一个数组
                         *  as.length == 1 && as[0] == c 是为了保证Comparable<T>里面只有一个泛型并且就是传入的类c
                         */
                    
                    if (((t = ts[i]) instanceof ParameterizedType) &&
                        ((p = (ParameterizedType)t).getRawType() ==
                         Comparable.class) &&
                        (as = p.getActualTypeArguments()) != null &&
                        as.length == 1 && as[0] == c) // type arg is c
                        return c;
                }
            }
        }
        return null;
    }

给一个最直观的测试让大家明白这个函数的作用.

Person类的定义	调用	返回
class Person	comparableClassFor(new Person("Tom", 12))	null
class Person implements Comparable	comparableClassFor(new Person("Tom", 12))	null
class Person implements Comparable<String>	comparableClassFor(new Person("Tom", 12))	null
class Person implements Comparable<Person>	comparableClassFor(new Person("Tom", 12))	Person

compareComparables方法

方法很简单,就是在满足条件的情况下调用CompareTo方法返回,否则返回0

/**
     * Returns k.compareTo(x) if x matches kc (k's screened comparable
     * class), else 0.
     * 如果类不同就返回0 否则就返回调用compareTo比较后的结果
     */
    @SuppressWarnings({"rawtypes","unchecked"}) // for cast to Comparable
    static int compareComparables(Class<?> kc, Object k, Object x) {
        return (x == null || x.getClass() != kc ? 0 :
                ((Comparable)k).compareTo(x));
    }

tieBreakOrder方法

identityHashCode()和hashCode()的区别会在另外一篇博客待完成中分析

      /**
         * a或者b为null或者如果a和b同属一个类就调用系统的identityHashCode
         */
        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;
        }

root方法

因为当前的节点可能不是红黑树的根,为什么呢?

1.红黑树中的每个节点都是TreeNode节点,所以每个节点都可以调用TreeNode中的方法.

final TreeNode<K,V> root() {
            for (TreeNode<K,V> r = this, p;;) {
                if ((p = r.parent) == null)
                    return r;
                r = p;
            }
        }

find方法

TreeNode<K,V> find(int h, Object k, Class<?> kc)方法就是二叉树的查找了,查找该k和对应的h是否存在在以当前节点为头结点的子树中了.

代码就不贴了,比较简单.

putTreeVal方法

因为红黑树插入的时候需要比较TreeNode,这里是把节点的hash值来比较大小,具体比较机制在代码的注释中有解释.

至于为什么不直接用CompareTo方法来比较,因为在HashMap 1.7的时候没有引入红黑树,所以大部分的代码的Key是可能没有实现Comparable接口,因此我猜应该是为了兼容的问题.

final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab,
                                       int h, K k, V v) {
            Class<?> kc = null;
            boolean searched = false;
            //找到红黑树的根
            TreeNode<K,V> root = (parent != null) ? root() : this;
            /**
             * for 循环去寻找到该节点应该插入的位置,TreeNode之间的比较是通过该节点的hash值
             *     1. 如果该节点已经存在 那就直接返回
             *     2. 如果该节点hash值小于该节点的hash值 往左侧
             *     3. 如果该节点hash值小于该节点的hash值 往右侧
             *     
             */
            for (TreeNode<K,V> p = root;;) {
                int dir, ph; K pk;
                if ((ph = p.hash) > h) // 左侧
                    dir = -1;
                else if (ph < h)      // 右侧
                    dir = 1;
                else if ((pk = p.key) == k || (k != null && k.equals(pk))) //已经存在
                    return p;
                /**
                 * hash值相等但是key值没有匹配上会进行以下操作
                 * 1. 调用comparableClassFor先看该k是否已经实现compareable<k.class>接口
                 * 2. 如果实现了Compareable<k.class>接口 就进行compareComparables方法看看是否可以比较出结果
                 * 3. 如果还是没有比较出结果,就去左右子树中搜索有没有该节点(注意只搜索一次)
                 * 4. 如果左右子树中也没有该节点,说明必须要插入该节点到此红黑树中,所以就调用tieBreakOrder强行分出大小
                 */
                else if ((kc == null &&                                    
                          (kc = comparableClassFor(k)) == null) ||
                         (dir = compareComparables(kc, k, pk)) == 0) {
                    if (!searched) {
                        TreeNode<K,V> q, ch;
                        searched = true;
                        if (((ch = p.left) != null &&
                             (q = ch.find(h, k, kc)) != null) ||
                            ((ch = p.right) != null &&
                             (q = ch.find(h, k, kc)) != null))
                            return q;
                    }
                    dir = tieBreakOrder(k, pk);
                }
                
                /**
                 * 观察当前节点是进入左侧 还是进入右侧 还是插入
                 * 如果是插入的时候会进入if block 中的内容
                 */
                TreeNode<K,V> xp = p;
                if ((p = (dir <= 0) ? p.left : p.right) == null) {
                    Node<K,V> xpn = xp.next;
                    TreeNode<K,V> x = map.newTreeNode(h, k, v, xpn);  //生成节点
                    //插入到红黑树中
                    if (dir <= 0)
                        xp.left = x;
                    else
                        xp.right = x;
                    //插入到链表中
                    xp.next = x;
                    x.parent = x.prev = xp;
                    if (xpn != null)
                        ((TreeNode<K,V>)xpn).prev = x;
                    /**
                     * 调整红黑树返回新的节点值
                     * 把返回新的节点值移到链表的头
                     */
                    moveRootToFront(tab, balanceInsertion(root, x));
                    return null;
                }
            }
        }

balanceInsertion方法在图解红黑树-算法导论-java实现基于HashMap1.8已经分析过了

由于HashMap在树化的过程中既保持了红黑树的结构,并且也保持了原先链表中的结构,只不过这个链表与其他没有树化的链表的区别在于树化的链表的节点类型是TreeNode,而没有树化的链表的节点类型是Node,所以当新节点在插入的时候既要往红黑树中插入,也要往链表中插入.

所以在balanceInsertion的过程中有可能会通过旋转root会发生改变,因此moveRootToFront的作用就是把root节点move到链表的头.

 static <K,V> void moveRootToFront(Node<K,V>[] tab, TreeNode<K,V> root) {
            int n;
            if (root != null && tab != null && (n = tab.length) > 0) {
                    //计算在哪个bin 
                int index = (n - 1) & root.hash;
                TreeNode<K,V> first = (TreeNode<K,V>)tab[index];
                //如果链表的头不是红黑树的头节点 则把root移到头节点 也就是first的前面
                if (root != first) {
                    Node<K,V> rn;
                    tab[index] = root;
                    TreeNode<K,V> rp = root.prev;
                    if ((rn = root.next) != null)
                        ((TreeNode<K,V>)rn).prev = rp;
                    if (rp != null)
                        rp.next = rn;
                    if (first != null)
                        first.prev = root;
                    root.next = first;
                    root.prev = null;
                }
                // 检查一下红黑树的各个成员变量是否正常
                assert checkInvariants(root);
            }
        }

checkInvariants方法

循环检查红黑树每个节点的成员变量是否正常.

static <K,V> boolean checkInvariants(TreeNode<K,V> t) {
            TreeNode<K,V> tp = t.parent, tl = t.left, tr = t.right,
                tb = t.prev, tn = (TreeNode<K,V>)t.next;
            if (tb != null && tb.next != t)
                return false;
            if (tn != null && tn.prev != t)
                return false;
            if (tp != null && t != tp.left && t != tp.right)
                return false;
            if (tl != null && (tl.parent != t || tl.hash > t.hash))
                return false;
            if (tr != null && (tr.parent != t || tr.hash < t.hash))
                return false;
            if (t.red && tl != null && tl.red && tr != null && tr.red)
                return false;
            if (tl != null && !checkInvariants(tl))
                return false;
            if (tr != null && !checkInvariants(tr))
                return false;
            return true;
        }

树化 treeify方法

调用该方法的TreeNode节点是一个从原先的Node类型的链表转化成TreeNode中的头节点,看原因在哪里? 在treeifyBin方法中可以找到答案的.

 /**
         * @return 调用该方法的时候this就已经是一个TreeNode了 
         *         而且整个链表的节点类型已经从Node转换成TreeNode 但是顺序没有变化
         */
        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;
                // 插入的是第一个元素 并给root赋值
                if (root == null) {
                    x.parent = null;
                    x.red = false;
                    root = x;
                }
                else {
                    K k = x.key;
                    int h = x.hash;
                    Class<?> kc = null;
                    //插入到红黑树中的位置 逻辑跟putTreeVal类似
                    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;
                        }
                    }
                }
            }
            // 把root节点移到链表头
            moveRootToFront(tab, root);
        }

链表化untreeify

当红黑树中的节点个数等于6,就把红黑树转化成简单的链表类型

final Node<K,V> untreeify(HashMap<K,V> map) {
            Node<K,V> hd = null, tl = null;
            for (Node<K,V> q = this; q != null; q = q.next) {
                    //将Node转化成TreeNode
                Node<K,V> p = map.replacementNode(q, null);
                if (tl == null)
                    hd = p;
                else
                    tl.next = p;
                tl = p;
            }
            return hd;
        }

扩容时转移节点 split

思想与链表的转移节点类似,根据rehash的特殊性,把红黑树拆成两个链表,然后再根据两个链表的长度决定是否树化或者链表化.对原理不明白的可以参考另一篇文章HashMap1.8 源码解析(1)--插入元素的rehash部分.

有人可能对链表化有疑问？毕竟已经是链表了啊,为什么还需要进行链表化,答案是因为此时的链表是TreeNode类型的,需要转化成Node类型的.

        final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
            TreeNode<K,V> b = this;
            // 将红黑树根据rehash分成两个链表
            TreeNode<K,V> loHead = null, loTail = null;
            TreeNode<K,V> hiHead = null, hiTail = null;
            int lc = 0, hc = 0;
            for (TreeNode<K,V> e = b, next; e != null; e = next) {
                next = (TreeNode<K,V>)e.next;
                e.next = null;
                if ((e.hash & bit) == 0) {
                    if ((e.prev = loTail) == null)
                        loHead = e;
                    else
                        loTail.next = e;
                    loTail = e;
                    ++lc;
                }
                else {
                    if ((e.prev = hiTail) == null)
                        hiHead = e;
                    else
                        hiTail.next = e;
                    hiTail = e;
                    ++hc;
                }
            }
            
            //根据每个链表的长度来决定是树化还是链表化

            if (loHead != null) {
                if (lc <= UNTREEIFY_THRESHOLD)
                    tab[index] = loHead.untreeify(map);
                else {
                    tab[index] = loHead;
                    if (hiHead != null) // (else is already treeified)
                        loHead.treeify(tab);
                }
            }
            if (hiHead != null) {
                if (hc <= UNTREEIFY_THRESHOLD)
                    tab[index + bit] = hiHead.untreeify(map);
                else {
                    tab[index + bit] = hiHead;
                    if (loHead != null)
                        hiHead.treeify(tab);
                }
            }
        }

小例子

public class Person {
    String name;
    int age;
    public Person() {}
    public Person(String name, int age) {
        this.name = name;
        this.age  = age;
    }
    
    @Override
    public String toString() {
        return "Person [name=" + name + ", age=" + age + "]";
    }
    @Override
    public boolean equals(Object obj) {

        if (this == obj) return true;
        if (obj instanceof Person) {
            Person p = (Person)obj;
            return p.name.equals(this.name);
        }
        return false;

        //return true;
    }
    
    @Override
    public int hashCode() {
        // TODO Auto-generated method stub
        return age;
    }
}

import java.lang.reflect.ParameterizedType;
import java.lang.reflect.Type;

public class TestHashMap {

    public static void main(String[] args) {
        test_redblacktree_put();
        //test_system_hashcode();
    }
    
    public static void test_redblacktree_put() {
        HashMap<Person, Integer> map = new HashMap<>(64);
        char[] strs = "SEARCHXMPL".toCharArray();
        for (int i = 0; i < strs.length; i++) {
            //System.out.println("insert into " + strs[i]);
            map.put(new Person(strs[i] + "", (strs[i] - '0') * 64),  i);
            printMap(map);
        }
        map.put(new Person("Z", ('M' - '0') * 64), -1);  //will goto tieBreak block
        printMap(map);
    }

    private static void printMap(HashMap<Person, Integer> map) {
        HashMap.Node<Person, Integer>[] table = map.table; 
        for (int i = 0; i < table.length; i++) {
            HashMap.Node<Person, Integer> e;
            if ((e = table[i]) != null) {
                System.out.print(i + ":");
                System.out.print(e);
                HashMap.Node<Person, Integer> p;
                while ((p = e.next) != null) {
                    System.out.print("->" + p);
                    e = e.next;
                }
                System.out.println();
            }
        }
    }
}

简单看一下结果:

插入到P时才进行树化

image.png

树化结束时的红黑树结构以及链表结构 此时E是链表和红黑树的头

当插入节点L时,红黑树的root节点发生了变化成为了M,通过moveRootToFront方法把M移到E的前面成为链表的头结点.

image.png

建议感兴趣的人可以下载完整代码自己调试一下看看结果如何,对理解红黑树会有更清晰些.

至此HashMap中TreeNode所有的方法都已经分析了,希望可以对你有所帮助,如果哪里写得有问题,还请指正哈.

1.HashMap1.8 源码解析(1)--插入元素
2.HashMap1.8 源码解析(2)--删除元素
3.HashMap1.8 源码解析(3)--TreeNode(红黑树)包括每一个方法
4.HashMap1.8 源码解析(4)--遍历元素

参考

1.java1.8 源码