ConcurrentHashMap源码解析6.TreeBin类

我们知道，当一个桶位形成了红黑树时，此时桶位中存的是一个TreeBin节点，其内部存在两个引用，分别是指向双向链表的first和指向红黑树根节点的r。

   
    

   static final class TreeBin extends Node {
     
        //红黑树根节点
        TreeNode root;
     
        //双向链表的头结点
        volatile TreeNode first;
     
        //等待者线程(当前lockState是读锁状态)
        volatile Thread waiter;
        
        
        volatile int lockState;
        
     	
        static final int WRITER = 1; // set while holding write lock
        static final int WAITER = 2; // set when waiting for write lock
        static final int READER = 4; // increment value for setting read lock
     

前面我们在分析put方法时，当我们成功的添加了数据时，会检查链表的长度是否大于8，大于的话会调用treeifyBin()方法。

• TreeBin的成员方法，将链表转换为红黑树的方法.

流程总结

1.先检查当前哈希表的长度是否达到了MIN_TREEIFY_CAPACITY(64)，如果没有达到，则会去尝试扩容而不会将当前桶位转为红黑树。

2.第一步会先将当前桶位的头节点锁定(synchronized)，然后遍历链表，将原Node链表转换为TreeNode形成的双向链表。

3.最后通过传入双向链表的头结点构造一个TreeBin节点 (调用TreeBin的构造方法)，放到当前的桶位上。

源码解析

    private final void treeifyBin(Node[] tab, int index) {
             
        
        Node b; int n, sc;
        if (tab != null) {
            
            //数组长度未达到树化的最小长度(64)，此时不进行树化，尝试去扩容
            if ((n = tab.length) < MIN_TREEIFY_CAPACITY)
                tryPresize(n << 1);
            
            
            else if ((b = tabAt(tab, index)) != null && b.hash >= 0) {
                
                //锁定当前桶位(锁对象是桶位的头元素)
                synchronized (b) {
                    
                    //再次判断，防止多线程下加锁对象已经被修改
                    if (tabAt(tab, index) == b) {
                        
                        
                        
                        TreeNode hd = null, tl = null;
                        for (Node e = b; e != null; e = e.next) {
                            TreeNode p =
                                new TreeNode(e.hash, e.key, e.val,
                                                  null, null);
                            if ((p.prev = tl) == null)
                                hd = p;
                            else
                                tl.next = p;
                            tl = p;
                        }
                        
                        setTabAt(tab, index, new TreeBin(hd));
                    }
                }
            }
        }
    }

接着上面的treeifyBin()方法，传入一个双向链表构造出一颗红黑树。

过程

• 先调用父类Node的构造器设置TreeBin节点的hash值为-2，然后TreeBin内部的first属性引用传来的双向链表的头节点。
• 然后遍历双向链表，根据节点的hash值，hash值比当前节点小的放到往左子树插，反之往右子树插。最终构造出一颗红黑树。
• 将构造出来的红黑树的根节点赋值给TreeBin内部的root引用。

       	   
      TreeBin(TreeNode b) {
            //调用父类的构造器，只设置了自己的hash值为-2，(TREEBIN = -2)
            super(TREEBIN, null, null, null);
          
            //使用first引用TreeNode链表。
            this.first = b;
          
            //r就是构造后的红黑树的根节点
            TreeNode r = null;
            
            
            for (TreeNode x = b, next; x != null; x = next) {
                //拿到next节点
                next = (TreeNode)x.next;
           		
                //强制设置当前插入节点的左右子树为NULL。
                x.left = x.right = null;
                
                
                if (r == null) {
                    //根节点的父节点为NULL
                    x.parent = null;
                    //红黑树的根节点是黑色
                    x.red = false;
                    //r引用x的对象 (根节点的对象)
                    r = x;
                }
			    
                //非第一个节点进来，此时已经有根节点了。
                else {
                    
                    //k 表示插入节点的key
                    K k = x.key;
                    
                    //h表示插入节点的hash
                    int h = x.hash;
                    
                    //kc 表示插入节点key的Class类型
                    Class kc = null;
                    
                    //表示为查找插入节点的父节点的一个临时节点
                    TreeNode p = r;
                    
                    //自旋
                    for (;;) {
                        
                        
                        int dir, ph;
                        
                        //临时节点p的key。
                        K pk = p.key;
                     
                     //--- 下面三种情况都是为dir赋值
                     
                     if ((ph = p.hash) > h)   
                            dir = -1; // dir设置为 -1 
                        
                       
                      else if (ph < h)
                            dir = 1; // dir设置为1
                    
                     
                      else if ((kc == null &&
                                  (kc = comparableClassFor(k)) == null) ||
                                 (dir = compareComparables(kc, k, pk)) == 0)
                            dir = tieBreakOrder(k, pk);
                        
                      
                      //xp 表示的是插入节点的父节点
                      TreeNode xp = p;
                      
                      
                      if ((p = (dir <= 0) ? p.left : p.right) == null) {
                          
                            //设置插入节点的父节点为当前节点
                            x.parent = xp;
                          
                            //判断待插入节点应该插入到当前节点的左儿子或者右儿子上。
                            if (dir <= 0)
                                xp.left = x;
                            else
                                xp.right = x;
                            
                            //插入节点后，红黑树的性质可能被破坏，需要调用平衡方法。
                            r = balanceInsertion(r, x);
                            break;
                        }
                    }
                }
            }
            //将r赋值给TreeBin对象的root引用。
            this.root = r;
            assert checkInvariants(root);
        }

     			
	 final Node find(int h, Object k) {
         
            if (k != null) {
                
                
                for (Node e = first; e != null; ) {
                    
                    
                    int s; K ek;
                    
                    //条件成立表示当前TreeBin有等待者线程 或者 有写操作线程正在加锁
                    if (((s = lockState) & (WAITER|WRITER)) != 0) {
                        if (e.hash == h &&
                            ((ek = e.key) == k || (ek != null && k.equals(ek))))
                            return e;
                        e = e.next;
                    }
                    
                    
                    else if (U.compareAndSwapInt(this, LOCKSTATE, s,
                        s + READER)) {
                        
                        
                        TreeNode r, p;
                        try {
                            p = ((r = root) == null ? null :
                                 r.findTreeNode(h, k, null)); //查询
                            
                        } finally {
                            Thread w;
                            
                            
                            if (U.getAndAddInt(this, LOCKSTATE, -READER) ==
                                (READER|WAITER) && (w = waiter) != null)
                                //unpark唤醒写线程，
                                LockSupport.unpark(w);
                        }
                        return p;
                    }
                }
            }
            return null;
        }