put方法

image.png

  1. //onlyIfAbsent 表示有重复的key是否覆盖，默认false表示会覆盖
  2. final V putVal(K key, V value, boolean onlyIfAbsent) {
  3.         if (key == null || value == null) throw new NullPointerException();
  4.        // 算出hash值   这个值一定是个正数      0x7fffffff; 
  5.        // f的二进制为：1111，7的二进制位0111  换算完之后最高位为0，所以最终值肯定为正数
  6.         int hash = spread(key.hashCode());  
  7.         int binCount = 0;
  9.         //这是一个死循环
  10.         for (Node<K,V>[] tab = table;;) {
  11.             // f 是链表头节点
  12.             // fh 是链表头结点的 hash
  13.             // i 是链表在 table 中的下标
  14.             Node<K,V> f; int n, i, fh;
  16.             if (tab == null || (n = tab.length) == 0){
  17.                 //第一个线程进来的第一次添加必然为true
  18.                 tab = initTable();   // 初始化 table 使用了 cas, 无需 synchronized 创建成功, 进入下一轮循环
  19.                 } 
  21.             // tabAt通过hash计算取出数组中的一个值，判断是否为空
  22.             else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {   //拿出key hash位置的value，如果为空则去添加
  23.                 //如果为空，就CAS创建一个新的node放在这个位置
  24.                 //多线程访问，第二个线程会CAS失败
  25.                 if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value, null)))
  26.                     break;                   // no lock when adding to empty bin
  27.                 }
  29.              //如果此判断成立  说明此数组正在扩容，则去协助扩容 MOVED -1
  30.             else if ((fh = f.hash) == MOVED){  
  31.                 // 帮忙之后, 进入下一轮循环
  32.                 tab = helpTransfer(tab, f);
  33.                    }
  35.             else {
  36.                 V oldVal = null;
  37.                 //锁住链表头节点
  38.                 synchronized (f) {     
  39.                     if (tabAt(tab, i) == f) {  //再次判断是因为  此位置的value有可能变为红黑树，锁就没用了
  40.                         if (fh >= 0) { //如果成立说明是链表
  41.                             binCount = 1;                            
  42.                            // 遍历链表 
  43.                             for (Node<K,V> e = f;; ++binCount) {
  44.                                 K ek;
  45.                                 // 找到相同的 key
  46.                                 if (e.hash == hash &&
  47.                                     ((ek = e.key) == key ||
  48.                                      (ek != null && key.equals(ek)))) {    //如果key和value都一样
  49.                                     oldVal = e.val;                         
  50.                                     if (!onlyIfAbsent)
  51.                                         //判断key相同的时候是否覆盖
  52.                                         e.val = value;      
  53.                                     break;
  54.                                 }
  55.                                 Node<K,V> pred = e;
  56.                                 //循环直到链表的最后都没有相同的值，就加入到链表的末尾
  57.                                 if ((e = e.next) == null) {            
  58.                                     pred.next = new Node<K,V>(hash, key,value, null);
  59.                                     break;
  60.                                 }
  61.                             }
  62.                         }
  63.                         else if (f instanceof TreeBin) {  //红黑树
  64.                             Node<K,V> p;
  65.                             binCount = 2;
  66.                             // putTreeVal 会看 key 是否已经在树中, 是, 则返回对应的 TreeNode
  67.                             if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
  68.                                                            value)) != null) {
  69.                                 oldVal = p.val;
  70.                                 if (!onlyIfAbsent)
  71.                                     p.val = value;
  72.                             }
  73.                         }
  74.                     }
  75.                 // 释放链表头节点的锁
  76.                 }
  77.                 if (binCount != 0) {
  78.                     if (binCount >= TREEIFY_THRESHOLD)   //如果链表的长度>=8  则变为黑红树
  79.                         treeifyBin(tab, i);    //但是如果数组的长度小于64，那么则不变为红黑树，则扩容
  80.                     if (oldVal != null)
  81.                         return oldVal;
  82.                     break;
  83.                 }
  84.             }
  85.         }
  86.            //维护集合长度，判断是否达到扩容阈值，如果是，则扩容
  87.         addCount(1L, binCount);  
  88.         return null;
  89.     }

initTable() 初始化数组

  • CAS保证只有一个线程在创建table

    compareAndSwapInt(Object var1, long var2, int var4, int var5);

  • o：目标Java变量引用。

  • offset：目标Java变量中的目标属性的偏移地址。
  • expected：目标Java变量中的目标属性的期望的当前值。
  • x：目标Java变量中的目标属性的目标更新值。

    步骤：

  1. 第一个线程进来将sizeCtl 改为-1，表示正在初始化中
  2. 第二个线程进来发现是-1，就yield放弃当前cpu时间。如果还是自己抢到cpu时间就继续空轮询再执行到这里判断是否是小于0。
  3. 第一个线程初始化完成后将sizeCtl改为扩容阈值
  4. 后续的线程继续进来，将sizeCtl赋值给sc
    1.  private final Node<K,V>[] initTable() {
    2.      Node<K,V>[] tab; int sc;
    3.      while ((tab = table) == null || tab.length == 0) {
    4.          //sizeCtl小于0，代表 数组正在初始化或者正在扩容
    5.          if ((sc = sizeCtl) < 0) {
    6.              Thread.yield(); 
    7.              }
    8.          // 尝试将 sizeCtl 设置为 -1（表示初始化 table）
    9.          else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {  
    10.              // 第一次进来SIZECTL= sc会成立， 将SIZECTL修改为-1，
    11.              // -1表示正在初始化，返回true
    12.              // 获得锁, 创建 table, 这时其它线程会在 while() 循环中 yield 直至 table 创建
    13.              try {
    14.                  //双重判断是为了不重复创建 因为一个线程创建完后，会更改sizeCtl值
    15.                  if ((tab = table) == null || tab.length == 0) {  
    16.                      int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
    17.                      @SuppressWarnings("unchecked")
    18.                      Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];//n为初始化的容量
    19.                      table = tab = nt;
    20.                      //可以换算为 n*0.75   n >>> 2表示 四分之一  ，此时sizeCtl=扩容阈值
    21.                      sc = n - (n >>> 2);    
    22.                  }
    23.              } finally {
    24.                  sizeCtl = sc;
    25.              }
    26.              break;
    27.          }
    28.      }
    29.      return tab;
    30.  }

addCount(1L, binCount)

  • 维护size的计数

  • 如果计数超过阈值，则触发扩容

    1.   // check 传进来的是binCount，表示当前位置链表的长度
    2.   private final void addCount(long x, int check) {
    3.       CounterCell[] as; long b, s;
    4.       if ((as = counterCells) != null ||      
    5.           // BASECOUNT 用于单线程情况下的计数   x=1 传进来的
    6.           !U.compareAndSwapLong(this, BASECOUNT, b = baseCount, s = b + x)) { 
    7.           //多线程情况下添加basecount失败，就进入
    8.           CounterCell a; long v; int m;
    9.           boolean uncontended = true;
    10.           if (as == null || (m = as.length - 1) < 0 ||
    11.               (a = as[ThreadLocalRandom.getProbe() & m]) == null ||
    12.               !(uncontended = U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))) {
    13.                  //见下面
    14.               fullAddCount(x, uncontended);
    15.               return;
    16.           }
    17.           if (check <= 1)
    18.               return;
    19.           //算出当前map中有多少元素，判断是否达到扩容阈值，如果是，则扩容
    20.           s = sumCount();   
    21.       }
    22.       if (check >= 0) {
    23.           Node<K,V>[] tab, nt; int n, sc;
    24.           while (s >= (long)(sc = sizeCtl) && (tab = table) != null &&
    25.                  (n = tab.length) < MAXIMUM_CAPACITY) {
    26.               int rs = resizeStamp(n);    //创建一个标识值
    27.               if (sc < 0) {            //第一个线程进来不可能小于0
    28.                   if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
    29.                       sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||
    30.                       transferIndex <= 0)
    31.                       break;
    32.                   if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))
    33.                       transfer(tab, nt);   //协助扩容
    34.               }
    35.               else if (U.compareAndSwapInt(this, SIZECTL, sc,    //将SIZECTL 改为一个负数
    36.                                            (rs << RESIZE_STAMP_SHIFT) + 2))
    37.                   transfer(tab, null);   //发起扩容（只有可能是第一个线程执行）
    38.               s = sumCount();
    39.           }
    40.       }
    41.   }

    fullAddCount

    2.   private final void fullAddCount(long x, boolean wasUncontended) {
    3.       int h;
    4.       if ((h = ThreadLocalRandom.getProbe()) == 0) {     //以此线程生成一个随机数，作为数组下标
    5.           ThreadLocalRandom.localInit();      // force initialization
    6.           h = ThreadLocalRandom.getProbe();
    7.           wasUncontended = true;
    8.       }
    9.       boolean collide = false;                // True if last slot nonempty
    10.       for (;;) {
    11.           CounterCell[] as; CounterCell a; int n; long v;
    12.           if ((as = counterCells) != null && (n = as.length) > 0) {    //第一次进来肯定为false（一旦有线程进入，则为true，那么数组已经创建）
    13.               if ((a = as[(n - 1) & h]) == null) { //随机取计数数组的一个位置，数组的这个位置还没有值则赋值
    14.                   if (cellsBusy == 0) {            // Try to attach new Cell
    15.                       CounterCell r = new CounterCell(x); // Optimistic create
    16.                       if (cellsBusy == 0 &&
    17.                           U.compareAndSwapInt(this, CELLSBUSY, 0, 1)) {
    18.                           boolean created = false;
    19.                           try {               // Recheck under lock
    20.                               CounterCell[] rs; int m, j;
    21.                               if ((rs = counterCells) != null &&
    22.                                   (m = rs.length) > 0 &&
    23.                                   rs[j = (m - 1) & h] == null) {
    24.                                   rs[j] = r;
    25.                                   created = true;
    26.                               }
    27.                           } finally {
    28.                               cellsBusy = 0;
    29.                           }
    30.                           if (created)
    31.                               break;
    32.                           continue;           // Slot is now non-empty
    33.                       }
    34.                   }
    35.                   collide = false;
    36.               }
    37.               else if (!wasUncontended)       // CAS already known to fail
    38.                   wasUncontended = true;      // Continue after rehash
    40.               else if (U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x)) 
    41.                   //数组的这个位置已经有值，那么直接累加
    42.                   //多线程的累加操作 自旋 最终会在这里停止(小于CPU的核数)
    43.                   break;
    44.               else if (counterCells != as || n >= NCPU)   
    45.                   //当计数数组的长度n >=CPU核数时，避免计数数组扩容
    46.                   collide = false;            // At max size or stale
    47.               else if (!collide)
    48.                   //只要n一直大于cpu核数，就会在这里死循环
    49.                   collide = true;
    50.               else if (cellsBusy == 0 && U.compareAndSwapInt(this, CELLSBUSY, 0, 1)) {     //数组扩容
    51.                   try {
    52.                       if (counterCells == as) {// Expand table unless stale
    53.                           CounterCell[] rs = new CounterCell[n << 1];
    54.                           for (int i = 0; i < n; ++i)
    55.                               rs[i] = as[i];
    56.                           counterCells = rs;
    57.                       }
    58.                   } finally {
    59.                       cellsBusy = 0;
    60.                   }
    61.                   collide = false;
    62.                   continue;                   // Retry with expanded table
    63.               }
    64.               h = ThreadLocalRandom.advanceProbe(h);
    65.           }
    67.     //创建计数数组，并且赋值（只有第一个线程能进入）
    68.     else if (cellsBusy == 0 && counterCells == as && U.compareAndSwapInt(this, CELLSBUSY, 0, 1)) {      
    69.               boolean init = false;
    70.               try {                           // Initialize table
    71.                   if (counterCells == as) {
    72.                       CounterCell[] rs = new CounterCell[2];
    73.                       rs[h & 1] = new CounterCell(x); //x=1 传进来的
    74.                       counterCells = rs;
    75.                       init = true;
    76.                   }
    77.               } finally {
    78.                   cellsBusy = 0;
    79.               }
    80.               if (init)
    81.                   break;
    82.           }
    83.           else if (U.compareAndSwapLong(this, BASECOUNT, v = baseCount, v + x))   //数组正在创建  对baseCount++
    84.               break;                          // Fall back on using base
    85.       }
    86.   }