ConcurrentHashMap第六讲:TreeBin源码解析

发布于:2023-01-21 ⋅ 阅读:(416) ⋅ 点赞:(0)

读取TreeBin节点 使用共享锁

写 TreeBin节点 使用独占锁(排它锁 synchronize)

  1. 共享锁(读锁
  2. 排它锁 又称为写锁、独占锁
  3. 互斥锁 是 独占锁的一种
  • 独占锁:指该锁一次只能被一个线程所持有。对ReentrantLock和Synchronized而言都是独占锁
  • 共享锁:指该锁可以被多个线程锁持有
  • 对ReentrantReadWriteLock其读锁是共享,其写锁是独占
    在这里插入图片描述
    在putVal 方法中有一段判断是否树化链表的代码:
      // 当前桶位不为null,可能是链表,可能是红黑树
                if (binCount != 0) {
                    //如果binCount >= 8 表示处理的桶位一定是链表
                    if (binCount >= TREEIFY_THRESHOLD)
                        //调用转化链表为红黑树的方法
                        treeifyBin(tab, i);
                    //不等于null 代表与原数据发生冲突,返回原来的值
                    if (oldVal != null)
                        return oldVal;
                    break;
                }

里面树化红黑树使用treeifyBin 方法,里面分两种情况:

  1. 扩容数组 tryPresize(n<<1)
  2. 树化链表

treeifyBin方法(包括tryPresize方法)

    private final void treeifyBin(Node<K,V>[] tab, int index) {
        Node<K,V> b; int n, sc;
        if (tab != null) {
            // 条件成立:说明当前table数组长度 未达到64,此时不进行树化操作,进行扩容操作
            if ((n = tab.length) < MIN_TREEIFY_CAPACITY)
                // 扩容
                tryPresize(n << 1);
            // 条件成立:说明当前桶位 有数据,且是普通node数据
            else if ((b = tabAt(tab, index)) != null && b.hash >= 0) {
                // 给头节点加锁
                synchronized (b) {
                    // 加锁没有问题
                    if (tabAt(tab, index) == b) {
                        // TreeNode链表是双向链表
                        // hd 代表代表头节点,tl代表前一个节点
                        TreeNode<K,V> hd = null, tl = null;

                        for (Node<K,V> e = b; e != null; e = e.next) {
                            TreeNode<K,V> p = new TreeNode<K,V>(e.hash, e.key, e.val,null, null);
                            if ((p.prev = tl) == null)
                                hd = p;
                            else
                                tl.next = p;

                            tl = p;
                        }

                        // 把TreeBin放到对应的桶位中
                        setTabAt(tab, index, new TreeBin<K,V>(hd));
                    }
                }
            }
        }
    }

里面用到的方法 tryPresize

   * 传进来的 size=len<<1
     *             假如len=16,size=32
     */
    private final void tryPresize(int size) {
        // size=32 , c=tableSizeFor(32 + 16 + 1) = 64
        int c = (size >= (MAXIMUM_CAPACITY >>> 1)) ? MAXIMUM_CAPACITY :
            tableSizeFor(size + (size >>> 1) + 1);
        int sc;
        // sizeCtl > 0
        // 1.如果table 未初始化,表示初始化大小
        // 2.如果已经初始化,表示下次扩容时的 触发条件(阈值)
        // sizeCtl = 0
        // 表示创建table数组时,使用 DEFAULT_CAPACITY 为大小
        while ((sc = sizeCtl) >= 0) {
            Node<K,V>[] tab = table;
            // n 代表扩容的大小
            int n;
            // 说明table 还未初始化
            if (tab == null || (n = tab.length) == 0) {
                n = (sc > c) ? sc : c;
                // 设置sizeCtl 为-1,告诉其它线程,table正在初始化
                if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
                    try {
                        if (table == tab) {
                            @SuppressWarnings("unchecked")
                            Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
                            table = nt;
                            sc = n - (n >>> 2);
                        }
                    } finally {
                        sizeCtl = sc;
                    }
                }
            }
            // 条件成立:说明sizeCtl > 0 ,因为c一定是一个正数,sc就是sizeCtl
            // 扩容大小还没有达到扩容阈值
            else if (c <= sc || n >= MAXIMUM_CAPACITY)
                break;
            // 前置条件:table已经初始化,c 已达到扩容阈值
            else if (tab == table) {
                // rs 代表当前长度的版本戳
                int rs = resizeStamp(n);
                // sc 如果 小于 0
                if (sc < 0) {
                    Node<K,V>[] nt;
                    //
                    if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
                        sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||
                        transferIndex <= 0)
                        break;
                    if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))
                        // 协助扩容
                        transfer(tab, nt);
                }
                // 开始扩容
                else if (U.compareAndSwapInt(this, SIZECTL, sc,
                                             (rs << RESIZE_STAMP_SHIFT) + 2))
                /** 因为我们的 rs 最终都是要赋值给 sizeCtl 的,而 sizeCtl 负数才代表扩容,
                 * 而将 rs 左移 16 位就刚好使得最高位为 1,此时低 16 位全部是 0,而因为低 16 位要记录扩容线程数,
                 * 按常理 +1 即可,但是  sizeCtl 中 -1 这个数值已经被使用了,用来代替当前有线程准备扩容,所以只好 +2
                 */
                    //当前线程扩容
                    transfer(tab, null);
            }
        }
    }

TreeBin源码

TreeBin中的变量

部分变量:

    static final class TreeBin<K,V> extends Node<K,V> {
        // 红黑树 根节点
        TreeNode<K,V> root;
        // 链表的头节点
        volatile TreeNode<K,V> first;
        // 等待者线程 (当前lockState是读锁状态)
        volatile Thread waiter;

         * 1.写锁状态 写是独占状态,以散列表来看,真正进入到TreeBin 中的写线程 同一时刻 只有一个线程
         * 2.读锁状态,读锁是共享,同一时刻可以有多个线程,同时进入到TreeBin对象中获取数据,每一个线程 都会给 lockStat + 4
         * 3.等待者状态(写线程在等待),当TreeBin 中有读线程目前正在读取数据时,写线程无法修改数据,那么就将lockState的最低2位 设置为 0b 10
         */
        volatile int lockState;
        // values for lockState
        
        //在持有写锁时设置
        static final int WRITER = 1; 
        //在等待写锁时设置
        static final int WAITER = 2; 
      	//设置读锁的增量值	
        static final int READER = 4; 

TreeBin的构造方法

*  b 链表的头元素
   */
 TreeBin(TreeNode<K,V> b) {
      // 设置节点hash 为-2,此节点是TreeBin节点
      super(TREEBIN, null, null, null);

      // 使用first 引用 TreeNode 链表
      this.first = b;

      // r 红黑树的根节点
      TreeNode<K,V> r = null;

      // x 表示遍历的当前节点
      // 插入链表:这个for循环是把 以b开头的链表插入到 红黑树中
      for (TreeNode<K,V> x = b, next; x != null; x = next) {
          next = (TreeNode<K,V>)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;

              //p 表示查找插入节点的父节点的一个临时节点
              // 插入节点:这个for循环是把 x节点插入到 红黑树中
              for (TreeNode<K,V> p = r;;) {
                  // dir
                  //  1:表示插入节点的hash值大于 当前p节点的hash
                  // -1:表示插入节点的hash值小于 当前p节点的hash
                  // ph:表示临时父节点的hash值
                  int dir, ph;
                  // 临时节点 key
                  K pk = p.key;

                  //插入节点的hash值 小于 临时父节点
                  if ((ph = p.hash) > h)
                      // 插入节点可能需要插入到 当前节点 的左子节点 或者 继续在左子树查找
                      dir = -1;

                  //插入节点的hash值 大于 临时父节点
                  else if (ph < h)
                      // 插入节点可能需要插入到 当前节点 的右子节点 或者 继续在右子树查找
                      dir = 1;

                  // 自定义类型比较,比较的对象是实现了Comparable 接口
                  // 如果执行到CASE3:说明当前插入节点的hash 与 当前节点的hash一致,会在case3 做出最终排序
                  // 最终拿到的dir 一定不是0,而是(1,或 -1)
                  else if ((kc == null &&
                            (kc = comparableClassFor(k)) == null) ||
                           (dir = compareComparables(kc, k, pk)) == 0)
                      dir = tieBreakOrder(k, pk);

                  // xp 表示 插入节点的父节点
                      TreeNode<K,V> xp = p;
                  // dir<=0 说明 x 应该在 p 的左边
                  // 条件成立:p==null 说明当前来到了叶子节点
                  // 条件不成立: 说明p下面还有层数,还可以继续向下查找
                  if ((p = (dir <= 0) ? p.left : p.right) == null) {
                      // 设置插入节点为 xp
                      x.parent = xp;
                      //dir<=0 说明插入节点是父节点的左子树
                      if (dir <= 0)
                          xp.left = x;
                      //dir>0  说明插入节点是父节点的右子树
                      else
                          xp.right = x;
                      // 插入节点后 红黑树的性质可能会被破坏,所以需要调用 平衡方法
                      r = balanceInsertion(r, x);
                      break;
                  }
              }
          }
      }
      // 将r 赋值给 TreeBin对象的 root引用
      this.root = r;
      assert checkInvariants(root);
  }

TreeBin的find方法

    final Node<K,V> find(int h, Object k) {
            if (k != null) {
                //e 表示 循环迭代的当前节点   迭代的是first引用的链表
                for (Node<K,V> e = first; e != null; ) {
                    // s 保存的是lock 临时状态
                    // ek 链表当前节点 的key
                    int s; K ek;

                    // (WAITER|WRITER) =》 0010 | 0001 = 0011
                    //等待者状态(写线程在等待),当TreeBin 中有读线程目前正在读取数据时,写线程无法修改数据,那么就将lockState的最低2位 设置为 0b 10
                    // lockState & 0011 != 0 条件成立:说明当前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;
                    }

                    //前置条件:说明上面是等于0的,当前treeBin中,等待者线程 或者 写线程 都没有
                    // 说明添加读锁成功     lockStat + 4
                    else if (U.compareAndSwapInt(this, LOCKSTATE, s,
                                                 s + READER)) {
                        TreeNode<K,V> r, p;
                        try {
                            //查询操作
                            // r是红黑树 根节点
                            // TreeBin 的find 里面调用的是 TreeNode 的findTreeNode
                            p = ((r = root) == null ? null :
                                 r.findTreeNode(h, k, null));
                        } finally {
                            // w 表示等待者线程
                            Thread w;

                            //查询完后,释放读锁
                            // U.getAndAddInt(this, LOCKSTATE, -READER) == (READER|WAITER)
                            // getAndAddInt 返回的值是未修改前的值
                            //1.当前线程查询红黑树结束,释放当前线程的读锁,就是让lockstate - 4
                            // (READER|WAITER) = (4 | 2) = 0110 => 表示当前只有一个线程在读,且有一个线程在等待
                            // 当前读线程未TreeBin 中的最后一个读线程

                            //2.(w = waiter) != null 说明有一个写线程在等待读操作全部结束
                            if (U.getAndAddInt(this, LOCKSTATE, -READER) ==
                                    (READER|WAITER) && (w = waiter) != null)
                                // 使用unpark 让写线程 恢复运行状态
                                LockSupport.unpark(w);
                        }
                        return p;
                    }
                }
            }
            return null;
        }

putTreeVal方法

* 查找或添加节点。
  * 如果添加则返回null
  */
 final TreeNode<K,V> putTreeVal(int h, K k, V v) {
     Class<?> kc = null;
     boolean searched = false;
     for (TreeNode<K,V> p = root;;) {

         // dir
         //  1:表示插入节点的hash值大于 当前p节点的hash
         // -1:表示插入节点的hash值小于 当前p节点的hash
         // ph:表示临时父节点的hash值
         int dir, ph; K pk;
         // 当根节点为null,插入节点就是根节点
         if (p == null) {
             first = root = new TreeNode<K,V>(h, k, v, null, null);
             break;
         }
         // 插入节点 比 当前节点小  dir<0
         else if ((ph = p.hash) > h)
             dir = -1;
         // 插入节点 比 当前节点大  dir>0
         else if (ph < h)
             dir = 1;
         // 插入节点 比 当前节点一样(key一样)
         else if ((pk = p.key) == k || (pk != null && k.equals(pk)))
             // 插入失败返回当前TreeNode
             return p;

         // 自定义类型比较,比较的对象是实现了Comparable 接口
         // 如果执行到CASE3:说明当前插入节点的hash 与 当前节点的hash一致,会在case3 做出最终排序
         // 最终拿到的dir 一定不是0,而是(1,或 -1)
         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.findTreeNode(h, k, kc)) != null) ||
                     ((ch = p.right) != null &&
                      (q = ch.findTreeNode(h, k, kc)) != null))
                     return q;
             }
             dir = tieBreakOrder(k, pk);
         }

         // xp 父节点
         TreeNode<K,V> xp = p;
         if ((p = (dir <= 0) ? p.left : p.right) == null) {
             // 当前循环节点p 即为x节点的爸爸

             // x 表示插入节点
             // f 表示链表之前的 链表的头节点
             TreeNode<K,V> x, f = first;
             first = x = new TreeNode<K,V>(h, k, v, f, xp);

             // 条件成立:说明链表有数据
             if (f != null)
                 // 设置老的头节点的前置引用,当前的头节点
                 f.prev = x;


             if (dir <= 0)
                 xp.left = x;
             else
                 xp.right = x;

             // 如果xp 父节点是黑色的,则x当前节点为红色
             if (!xp.red)
                 x.red = true;
             else {
                 // 表示当前新插入节点后,新插入节点 与父节点 形成“红红相连”
                 lockRoot();
                 try {
                     // 平衡红黑树,使其再次符合规范
                     root = balanceInsertion(root, x);
                 } finally {
                     unlockRoot();
                 }
             }
             break;
         }
     }
     assert checkInvariants(root);
     return null;
 }

lockRoot方法和unlockRoot方法:

* 为树结构重组获取写锁。
 */
private final void lockRoot() {
    // 只有一个写线程可以存在于TreeBin中
    // 条件成立:说明lockState 并不是0,说明此时有其它线程在TreeBin红黑树中读取数据
    // !false = true 说明我们已经加锁成功了
    if (!U.compareAndSwapInt(this, LOCKSTATE, 0, WRITER))
        contendedLock(); // offload to separate method 卸载到分离方法
}


 * 为树结构调整释放写锁。
 */
private final void unlockRoot() {
    lockState = 0;
}

contendedLock()方法

* 可能阻塞等待根锁。
*/
private final void contendedLock() {
   boolean waiting = false;
   // s 表示lock值
   for (int s;;) {
       // ~WAITER = 11111....10
       //条件成立:说明目前TreeBin中没有读线程在访问 红黑树
       // 因为读的时候lockState 后两位是 10,所以等于0时,lockState没有读线程
       // 条件不成立:有线程访问红黑树
       if (((s = lockState) & ~WAITER) == 0) {

           // 条件成立:说明写线程 抢占成功
           // 把LOCKSTATE 改为 1
           if (U.compareAndSwapInt(this, LOCKSTATE, s, WRITER)) {
               if (waiting)
                   // 设置TreeBin 对象waiter 引用为null
                   waiter = null;
               return;
           }
       }
       // lock & 0000...10 = 0 :说明lock 中waiter 标志位为0,此时当前线程可以设置为 1了,然后将当前线程挂起
       else if ((s & WAITER) == 0) {
           // 设置LOCKSTATE 的低两位为 01,让线程等待
           if (U.compareAndSwapInt(this, LOCKSTATE, s, s | WAITER)) {
               waiting = true;
               // 设置等待线程就是当前线程
               waiter = Thread.currentThread();
           }
       }
       //条件成立:说明当前线程在CASE2 中,已经将waiter设置为了当前线程,并且将lockState 中表示 等待者标记位的地方 设置为了1
       // 这个时候,就是让当前线程挂起
       else if (waiting)
           LockSupport.park(this);
   }
}


网站公告

今日签到

点亮在社区的每一天
去签到