解析HashMap(三)——红黑树（TreeNode）

Posted on | In , | Views:

解析HashMap(三)——红黑树（TreeNode）

一、概述

​ 由于在JDK1.8中，在HashMap中为了提高性能新加了红黑树，在putVal()和remove()方法中都使用到了红黑树。我们来介绍HashMap中几个关键方法。

二、源码分析

1. TreeNode

​ 首先我们要知道，所有有关红黑树的操作都是在HashMap的内部类TreeNode中。

​ TreeNode<K, V>也是继承Node<K, V>.

1
static final class TreeNode<K,V> extends Node<K,V> {...}

2. 属性：

1
2
3
4
5
6
7
8
9
10
11
12
13
/* 红黑树中的父节点 */
TreeNode<K,V> parent;
/* 红黑树中的左子树 */
TreeNode<K,V> left;
/* 红黑树中的右子树 */
TreeNode<K,V> right;
/* bucket既保持了链表的结构用(next,prev)也保持了红黑树的结构(left,right,parent)
 * 遍历时候红黑树可以当作链表处理，有next
 * 删除之后需要断开链接
 */
TreeNode<K,V> prev;
/* 是否是红节点 */
boolean red;

3. 构造函数：

1
2
3
TreeNode(int hash, K key, V val, Node<K,V> next) {
	super(hash, key, val, next);
}

4. 树化

treeifyBin(Node<K,V>[] tab, int hash)

​ 树化的条件：链表中的个数 ≥ TREEIFY_THRESHOLD，但是并不是满足这个条件一定树化，当满足这个条件时，进入treeifyBin()方法，此时会判断两个条件：

  1. tab为null
  2. tab的length也就是capacity的大小比MIN_TREEIFY_CAPACITY=64小

​ 因为这个时候认为扩容的效果比树化要好。

​ 树化的三步：

  1. Node节点变成TreeNode节点
  2. 链表变成双向链表
  3. 双向链表变成红黑树
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/* 将hash对应的bucket链表红黑树树化 */
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) { 
        // 如果当前bucket不为null
        // hd 头指针　tl 尾指针
        TreeNode<K,V> hd = null, tl = null;
        /**
         * 循环遍历整个链表
         * 1. 先把Node节点转换成TreeNode节点
         * 2. 红黑树的所有节点按原来的顺序利用指针(prev和next)形成了一个双向链表
         * 这也是多次遍历链表的时候顺序也不会变化的原因
         */
        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);
        /**
         * 将TreeNode形成的双向链表转化成红黑树
         */
        if ((tab[index] = hd) != null)
            hd.treeify(tab);
    }
}

replacementTreeNode(Node<K,V> p, Node<K,V> next)

1
2
3
4
// 将Node节点转化成TreeNode节点
TreeNode<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> next) {
    return new TreeNode<>(p.hash, p.key, p.value, next);
}

treeify(Node<K,V>[] tab)

​ 该方法将TreeNode形成的双向链表转化成红黑树。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
/**
  * 调用该方法的时候this就已经是一个TreeNode了 
  * 而且整个链表的节点类型已经从Node转换成TreeNode,但是顺序没有变化
  */
final void treeify(Node<K,V>[] tab) {
    TreeNode<K,V> root = null;
    // 遍历链表　x是当前节点
    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;;) {
                // dir 通过比较hash得到，ph从红黑树拿出的当前节点哈希值
                int dir, ph;
                // 从红黑树拿出的当前节点哈希值
                K pk = p.key;
                // 链表节点哈希值<红黑树节点，去左侧
                if ((ph = p.hash) > h)
                    dir = -1;
                // 链表节点哈希值>红黑树节点，去右侧
                else if (ph < h)
                    dir = 1;
                // 哈希值相同时，通过key值比较，
                else if ((kc == null &&
                         (kc = comparableClassFor(k)) == null) || (dir = compareComparables(kc, k, pk)) == 0)
                    //如果没有key比较器,调用tieBreakOrder()强制比较
                    dir = tieBreakOrder(k, pk);
                // xp 代表　红黑树节点
                TreeNode<K,V> xp = p;
                // dir ≤ 0去左侧，否则去右侧
                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);
}

tieBreakOrder(Object a, Object b)

​ 强行比较a,b的大小。

1
2
3
4
5
6
7
8
9
10
/**
 * 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;
}

5. 插入

putTreeVal(HashMap<K,V> map, Node<K,V>[] tab, int h, K k, V v)

​ 在HashMap的putVal()方法中，我们使用到了putTreeVal()方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
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值
      * 利用红黑树具有二叉搜索树的性质    
      */
    for (TreeNode<K,V> p = root;;) {
     	/*
         * dir用来判断选择左子树还是右子树,dir = -1选择左侧，dir = 1选择右侧　
         * ph用来存放树中当前节点
         */ 
    	int dir, ph; 
     	// pk用来存放树中当前节点的键
     	K pk;
     	// 如果 插入节点 hash值小于 树的当前节点 的hash值,往左侧
     	if ((ph = p.hash) > h)
        	dir = -1;
     	// 如果 插入节点 hash值大于 树的当前节点 的hash值,往右侧
	 	else if (ph < h)
        	dir = 1;
        // 节点已经存在，直接返回该节点
	 	else if ((pk = p.key) == k || (k != null && k.equals(pk)))
   	 		return p;
        /**
         * hash值相等但是key值没有匹配上会进行以下操作
         * 总的来说就是先根据hash比较，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;
                /* 
                 * 在左右子树查找该节点，如果有则返回该节点
                 * find()方法实际上就是二叉树的查找
                 */
                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;
            }
            // 当前树中没有该节点,通过key分大小，决定插入位置
            dir = tieBreakOrder(k, pk);
        }   
        /**
         * 到这里说明红黑树中没有该节点
         * 观察当前节点是进入左侧，还是进入右侧，还是插入
         * 如果是插入的时候会进入if block 中的内容
         */
        TreeNode<K,V> xp = p;
        // 直到找到叶子节点为止
        if ((p = (dir <= 0) ? p.left : p.right) == null) {
            
        	// xpn是xp的next
            Node<K,V> xpn = xp.next;
            //Node变为TreeNode
            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;
        }
    }
}

comparableClassFor(Object x)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
/**
  * @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) {
    // 判断x所属的类实现了Comparable<T>接口
    if (x instanceof Comparable) {
        Class<?> c; 
        Type[] ts, as; 
        Type t; 
        ParameterizedType p;
        // 如果是String类直接返回了
        if ((c = x.getClass()) == String.class) 
            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()

1
2
3
4
5
6
7
/**
 * 如果类不同就返回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));
}

6. 删除

​ 在HsahMap的removeNode方法中，如果我们删除的是红黑树上的节点，我们调用了红黑树的两个方法treeNode.getTreeNode(hash, key)和treeNode.removeTreeNode(this, tab, movable).我们现在就来分析这两个方法。

getTreeNode(int h, Object k)

​ 这个方法比较简单，先找到当前节点的root根节点，然后调用根节点的find()方法，直到找到目标节点。

1
2
3
final TreeNode<K,V> getTreeNode(int h, Object k) {
    return ((parent != null) ? root() : this).find(h, k, null);
}

removeTreeNode(HashMap<K,V> map, Node<K,V>[] tab, boolean movable)

​ 删除树节点的大致过程：

  • 先在链表中删除
  • 判断是否需要链表化
  • 最后再进行红黑树删除
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
final void removeTreeNode(HashMap<K,V> map, Node<K,V>[] tab, boolean movable) {
	int n;
    /* 如果tab等于null或者tab.length长度为0 直接返回 */
    if (tab == null || (n = tab.length) == 0)
        return;
    // 求在数组中的索引
    int index = (n - 1) & hash;
    // first是链表中的头节点
    TreeNode<K,V> first = (TreeNode<K,V>)tab[index], root = first, rl;
    // succ是被删除节点的下一个节点，pred是被删除节点的上一个节点
    TreeNode<K,V> succ = (TreeNode<K,V>)next, pred = prev;
    /* 在链表中删除 */
    // 链表的第一个节点就是要被删除的节点
    if (pred == null)
        // 让第二节点作为头结点
        first = succ;
        tab[index] = first;
    // 被删除节点不是头结点
    else
        // 其上一个节点和下一个节点直接相连
        pred.next = succ;
    //双向连接
    if (succ != null)
        succ.prev = pred;
    if (first == null)
        return;
    if (root.parent != null)
        root = root.root();
    
    /**
     * too small 直接把红黑树转成链表
     * 该判断作为链表化的阀值
     */
    if (root == null || root.right == null || 
        (rl = root.left) == null || rl.left == null) {
        tab[index] = first.untreeify(map);  // too small
        return;
    }
    /**
     * 接下来就是红黑树的节点删除
     * p 被删除的节点，pl被删除节点的左儿子，pr被删除节点的右儿子
     * replacement被删除节点的后继节点
     */
    TreeNode<K,V> p = this, pl = left, pr = right, replacement;
    // p不是叶子节点
    if (pl != null && pr != null) {
        TreeNode<K,V> s = pr, sl;
        // 找到其后继结点
        while ((sl = s.left) != null) 
            s = sl;
        // 交换颜色
        boolean c = s.red; 
        s.red = p.red; 
        p.red = c; 
        TreeNode<K,V> sr = s.right;
        TreeNode<K,V> pp = p.parent;
        // p是s的直接父节点
        if (s == pr) {
            //　交换位置
            p.parent = s;
            s.right = p;
        }
        else {
            TreeNode<K,V> sp = s.parent;
            if ((p.parent = sp) != null) {
                if (s == sp.left)
                    sp.left = p;
                else
                    sp.right = p;
            }
            if ((s.right = pr) != null)
                pr.parent = s;
        }
        p.left = null;
        if ((p.right = sr) != null)
            sr.parent = p;
        if ((s.left = pl) != null)
            pl.parent = s;
        if ((s.parent = pp) == null)
            root = s;
        else if (p == pp.left)
            pp.left = s;
        else
            pp.right = s;
        if (sr != null)
            replacement = sr;
        else
            replacement = p;
    }
    else if (pl != null)
        replacement = pl;
    else if (pr != null)
        replacement = pr;
    else
        replacement = p;
    if (replacement != p) {
        TreeNode<K,V> pp = replacement.parent = p.parent;
        if (pp == null)
            root = replacement;
        else if (p == pp.left)
            pp.left = replacement;
        else
            pp.right = replacement;
        p.left = p.right = p.parent = null;
    }
    TreeNode<K,V> r = p.red ? root : balanceDeletion(root, replacement);    
    if (replacement == p) {  // detach
        TreeNode<K,V> pp = p.parent;
        p.parent = null;
        if (pp != null) {
            if (p == pp.left)
                pp.left = null;
            else if (p == pp.right)
                pp.right = null;
        }
    }
    if (movable)
        moveRootToFront(tab, r);
}

7. 链表化：

untreeify(HashMap<K,V> map)

​ 我们在调用rmoveTreeNode()和扩容时调用split()时有可能使用该方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
 * 红黑树链表化
 */
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<K,V> p = map.replacementNode(q, null);
        //维护顺序
        if (tl == null)
            hd = p;
        else
            tl.next = p;
        tl = p;
    }
    return hd;
}

replacementNode(Node<K,V> p, Node<K,V> next)

​ 构造一个Node节点。

1
2
3
Node<K,V> replacementNode(Node<K,V> p, Node<K,V> next) {
    return new Node<>(p.hash, p.key, p.value, next);
}

8. 扩容时转移节点

split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit)

我们在扩容时，对于链表的情况是将链表分成两个链表，而对于树也类似；我们将树从给定的结点分裂成低位和高位的两棵树，若新树结点太少则转为线性链表。只有`resize`时会调用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
/*
 * @param map the map
 * @param tab 数组
 * @param index 需要分裂的表下标位置，数组下标
 * @param bit 分裂时分到高位和低位的依据参数，实际使用时输入的是扩展之前旧数组的大小
 */
final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
	TreeNode<K,V> b = this;
    //重新链接到lo和hi链表，保留顺序
    //低位头尾指针
    TreeNode<K,V> loHead = null, loTail = null;
    //高位头尾指针
    TreeNode<K,V> hiHead = null, hiTail = null;
    //低位和高位的结点个数统计
    int lc = 0, hc = 0;
    //e从this开始遍历直到next为null，一般是链表的头结点
    for (TreeNode<K,V> e = b, next; e != null; e = next) {
        next = (TreeNode<K,V>)e.next;
        e.next = null;
		//这段决定了该结点被分到低位还是高位，依据算式是e.hash & bit，由于bit是oldCap，所以一定是2的指数次幂，所以bit一定只有一个高位是1其余全是0
        //这个算式实际是判断e.hash新多出来的有效位是0还是1，若是0则分去低位树，是1则分去高位树
        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;
            //若高位树为null则代表整棵树全保留在了低位，树没有变化所以不用进行后面的treeify
            if (hiHead != null) 
                loHead.treeify(tab);
        }
    }
    //这段与上面对于低位部分的分析相对应
    if (hiHead != null) {
        if (hc <= UNTREEIFY_THRESHOLD)
            tab[index + bit] = hiHead.untreeify(map);
        else {
            //高位所处的位置为原本位置+旧数组的大小即bit
            tab[index + bit] = hiHead;
            if (loHead != null)
                hiHead.treeify(tab);
        }
    }
}