https://blog.csdn.net/qq_46312987/article/details/121548428

原子方法

putIfAbsent()

插入数据如果插入数据的key 不存在于集合中则保存当前数据返回null 如果key 存在返回存在的value

remove()

根据key 和value来删除集合中的元素 该删除必须保证key和value完全匹配

replace(k,v,v)

根据key 和oldValue来替换集合中存在的值 新的值是new value 如果替换成功返回value 否则返回空

replace(k,v)

数据结构

数组+链表+红黑树

jdk1.7的改进

取消了 segment分段设计 直接使用Node 数组来保存数据 并且采用Node 数组元素作为锁的范围 进一步减小了并发冲突的范围和概率
引入了红黑树的设计 降低了极端情况下查询某个节点数据的时间复杂度

查询性能的改进

分段锁设计
多个线程协助并发扩容
高低迁移
链表转红黑树 红黑树转链表
降低锁的粒度

解决 hash冲突的方法

1.开放寻址

如果i被占用就探查 i+1,i+2 i+…的位置

2.链式寻址法

hash表的每个位置都连接一个链表 当发生hash冲突时 冲突的元素将会加入这个位置的链表的最后

3.再hash法

提供多个不同的hash 函数 当发生冲突时 使用第二个第三个等

原理

1.根据 key的 code 计算hash值
2.如果 table是空 则进行初始化
3.如果 table 不是空 hash 值来计算 key 在table 中的下标 如果没有值则直接添加进去
4.如果当前计算的下标有值 对当前数组位置的节点进行加锁
从链表头部 开始遍历 如果存在相同的key 则进行修改对应的value 如果没有相同的key 则构建一个node 从尾部插入链表
5.如果是正在扩容的情况下 则进行多线程协助扩容
当数组长度小于等于64 并且链表长度大于等于8时 优先对数组进行扩容
当数组长度大于64 并且链表长度大于8时 会转换成红黑树
每个位置是16 比如线程1迁移 0-15 线程2 迁移 16-31

  1.     public V put(K key, V value) {
  2.         return putVal(key, value, false);
  3.     }
  1.  /** Implementation for put and putIfAbsent */
  2.     final V putVal(K key, V value, boolean onlyIfAbsent) {
  3.         if (key == null || value == null) throw new NullPointerException();
  4.         //根据hash code计算hash值
  5.         int hash = spread(key.hashCode());
  6.         int binCount = 0;
  7.         //自旋
  8.         for (Node<K,V>[] tab = table;;) {
  9.             Node<K,V> f; int n, i, fh;
  10.             //如果 node是空 则进行初始化
  11.             if (tab == null || (n = tab.length) == 0)
  12.                 tab = initTable();
  13.             //通过(n-1)&hash来计算当前key在table中的下标位置 如果没有值则将当前 node添加进去
  14.             else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
  15.                 if (casTabAt(tab, i, null,
  16.                              new Node<K,V>(hash, key, value, null)))
  17.                     break;                   // no lock when adding to empty bin
  18.             }
  19.             //正在扩容的情况下 多个线程协助扩容
  20.             else if ((fh = f.hash) == MOVED)
  21.                 tab = helpTransfer(tab, f);
  22.             else {
  24.                 V oldVal = null;
  25.                 //对当前数组位置的节点加锁
  26.                 synchronized (f) {
  27.                     //判断当前节点是链表 还是红黑树
  28.                     if (tabAt(tab, i) == f) {
  29.                         if (fh >= 0) {
  30.                             binCount = 1;
  31.                             //从链表头节点开始遍历
  32.                             for (Node<K,V> e = f;; ++binCount) {
  33.                                 K ek;
  34.                                 //如果存在相同的key 则修改 key对应的value
  35.                                 if (e.hash == hash &&
  36.                                     ((ek = e.key) == key ||
  37.                                      (ek != null && key.equals(ek)))) {
  38.                                     oldVal = e.val;
  39.                                     if (!onlyIfAbsent)
  40.                                         e.val = value;
  41.                                     break;
  42.                                 }
  43.                                 //构建node 然后加入链表中如果 根据key的hash值得到的数组下标已经有元素并且是链表元素则添加到链表的尾部
  44.                                 Node<K,V> pred = e;
  45.                                 if ((e = e.next) == null) {
  46.                                     pred.next = new Node<K,V>(hash, key,
  47.                                                               value, null);
  48.                                     break;
  49.                                 }
  50.                             }
  51.                         }
  52.                        //如果是红黑树
  53.                         else if (f instanceof TreeBin) {
  54.                             Node<K,V> p;
  55.                             binCount = 2;
  56.                             if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
  57.                                                            value)) != null) {
  58.                                 oldVal = p.val;
  59.                                 if (!onlyIfAbsent)
  60.                                     p.val = value;
  61.                             }
  62.                         }
  63.                     }
  64.                 }
  65.                 if (binCount != 0) {
  66.                     if (binCount >= TREEIFY_THRESHOLD)
  67.                         treeifyBin(tab, i);
  68.                     if (oldVal != null)
  69.                         return oldVal;
  70.                     break;
  71.                 }
  72.             }
  73.         }
  74.         addCount(1L, binCount);
  75.         return null;
  76.     }

初始化

sizeCtl =-1 表示当前线程抢占到初始化数组的资格正在初始化数组
sizeCtl = -N 用sizeCtl 值的二进制低16位来记录当前参与扩容的线程数量
sizeCtl = 0 表示数组未初始化 并且构造方法中没有指定长度
sizeCtl >0 如果数组已经初始化 name sizeCtl 的阈值 = 初始容量*0.75 如果未初始化则表示数组的初始容量

  1.     private final Node<K,V>[] initTable() {
  2.         Node<K,V>[] tab; int sc;
  3.         //当初始化完成退出
  4.         while ((tab = table) == null || tab.length == 0) {
  5.             //判断是否有其他线程在进行初始化
  6.             if ((sc = sizeCtl) < 0)
  7.                 //把自己进入就绪状态 释放cpu的执行权
  8.                 Thread.yield(); // lost initialization race; just spin
  9.             cas 操作去抢占锁 确保只有一个线程能抢占到锁 
  10.             else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
  11.                 try {
  12.                     //初始化
  13.                     if ((tab = table) == null || tab.length == 0) {
  14.                         int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
  15.                         @SuppressWarnings("unchecked")
  16.                         Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
  17.                         //初始化 赋值给CHM中的table
  18.                         table = tab = nt;
  19.                         //计算下次扩容阈值
  20.                         sc = n - (n >>> 2);
  21.                     }
  22.                 } finally {
  23.                     sizeCtl = sc;
  24.                 }
  25.                 break;
  26.             }
  27.         }
  28.         return tab;
  29.     }

扩容

当数组长度小于等于64 并且链表长度大于等于8时 优先对数组进行扩容
当数组长度大于64 并且链表长度大于8时 会转换成红黑树

  1.                 if (binCount != 0) {
  2.                      binCount>=8
  3.                     if (binCount >= TREEIFY_THRESHOLD)
  4.                         treeifyBin(tab, i);
  5.                     if (oldVal != null)
  6.                         return oldVal;
  7.                     break;
  8.                 }
  1.    private final void treeifyBin(Node<K,V>[] tab, int index) {
  2.         Node<K,V> b; int n, sc;
  3.         if (tab != null) {
  4.             //如果小于64则使用扩容解决
  5.             if ((n = tab.length) < MIN_TREEIFY_CAPACITY)
  6.                  //扩容为原来的一位，调整某一个桶中元素过多的问题(超出了8个))
  7.         //会触发某些桶中的元素重新分配，避免在一个桶中有太多的元素影响访问效率
  8.                 tryPresize(n << 1);
  9.               //桶中存在结点，并且此结点的hash值大于0，调整红黑树的结构
  10.             else if ((b = tabAt(tab, index)) != null && b.hash >= 0) {
  11.                 synchronized (b) {
  12.                     //锁住节点，把元素添加到树中
  13.                     if (tabAt(tab, index) == b) {
  14.                         TreeNode<K,V> hd = null, tl = null;
  15.                         for (Node<K,V> e = b; e != null; e = e.next) {
  16.                             TreeNode<K,V> p =
  17.                                 new TreeNode<K,V>(e.hash, e.key, e.val,
  18.                                                   null, null);
  19.                             if ((p.prev = tl) == null)
  20.                                 hd = p;
  21.                             else
  22.                                 tl.next = p;
  23.                             tl = p;
  24.                         }
  25.                         setTabAt(tab, index, new TreeBin<K,V>(hd));
  26.                     }
  27.                 }
  28.             }
  29.         }
  30.     }
  1.  private final void tryPresize(int size) {
  2.          //判断扩容目标大小 如果大小为 MAXIMUM_CAPACITY的一半则直接扩容大小为 MAXIMUM_CAPACITY
  3.         int c = (size >= (MAXIMUM_CAPACITY >>> 1)) ? MAXIMUM_CAPACITY :
  4.       否则通过      tableSizeFor计算当前size的最小幂方 如果当前size不等于2幂方 通过 tableSizeFor调整离size最近的幂方值
  5.      tableSizeFor(size + (size >>> 1) + 1)
  6.         while ((sc = sizeCtl) >= 0) {
  7.             Node<K,V>[] tab = table; int n;
  8.             //判断是否初始化过 如果没有初始化则初始化
  9.             if (tab == null || (n = tab.length) == 0) {
  10.                 n = (sc > c) ? sc : c;
  11.                 if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
  12.                     try {
  13.                         if (table == tab) {
  14.                             @SuppressWarnings("unchecked")
  15.                             Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
  16.                             table = nt;
  17.                             sc = n - (n >>> 2);
  18.                         }
  19.                     } finally {
  20.                         sizeCtl = sc;
  21.                     }
  22.                 }
  23.             }
  24.             //c <= sc 表示当前已经有其他线程在进行扩容 不需要在进行扩容
  25.             //n >= MAXIMUM_CAPACITY 已到达最大值没法扩容
  26.             else if (c <= sc || n >= MAXIMUM_CAPACITY)
  27.                 break;
  28.             else if (tab == table) {
  29.                 //得到二进制的数据
  30.                 高16位 表示扩容标记 由于每次扩容时 n的值都不同 因此能保证每次扩容时这个标记的唯一性
  31.                 低16位表示扩容的线程数量    
  32.                 int rs = resizeStamp(n);
  33.                    //当前已经有其他线程在执行扩容 
  34.                 if (sc < 0) {
  35.                     Node<K,V>[] nt;
  36.                     if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
  37.                         sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||
  38.                         transferIndex <= 0)
  39.                         break;
  40.                     并且当前线程可以协助扩容
  41.                     if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))
  42.                         transfer(tab, nt);
  43.                 }
  44.                 //当前没有其他线程进行扩容 进行首次扩容
  45.                 else if (U.compareAndSwapInt(this, SIZECTL, sc,
  46.                                              (rs << RESIZE_STAMP_SHIFT) + 2))
  47.                     transfer(tab, null);
  48.             }
  49.         }
  50.     }

并发扩容机制

0d7b03db00b347c1a1ed87c60118ac79.png
当存在多个线程并发扩容及数据迁移时 默认情况下会给每个线程分配一个区间 默认是16 每个线程负责自己区间内的数据迁移工作 

  1.     private final void transfer(Node<K,V>[] tab, Node<K,V>[] nextTab) {
  2.         int n = tab.length, stride;
  3.         //让每个cpu 处理的区间相同  默认为16 
  4.         if ((stride = (NCPU > 1) ? (n >>> 3) / NCPU : n) < MIN_TRANSFER_STRIDE)
  5.             stride = MIN_TRANSFER_STRIDE; // subdivide range
  6.         // nextTab == null = true
  7.         if (nextTab == null) {            // initiating
  8.             try {
  9.                 @SuppressWarnings("unchecked")
  10.                 //初始化一个node
  11.                 Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n << 1];
  12.                 //将新构建的赋值给 nextTab
  13.                 nextTab = nt;
  14.             } catch (Throwable ex) {      // try to cope with OOME
  15.                 sizeCtl = Integer.MAX_VALUE;
  16.                 return;
  17.             }
  18.             //nextTable = 新构建的nextTab
  19.             nextTable = nextTab;
  20.             //赋值下标
  21.             transferIndex = n;
  22.         }
  23.         int nextn = nextTab.length;
  24.         //被迁移的node
  25.         ForwardingNode<K,V> fwd = new ForwardingNode<K,V>(nextTab);
  26.         boolean advance = true;
  27.         boolean finishing = false; // to ensure sweep before committing nextTab
  28.         for (int i = 0, bound = 0;;) {
  29.             Node<K,V> f; int fh;
  30.             //判断是否还有待处理的数据迁移工作
  31.             while (advance) {
  32.                 int nextIndex, nextBound;
  33.                 //判断区间是否分配完成
  34.                 if (--i >= bound || finishing)
  35.                     advance = false;
  36.                 else if ((nextIndex = transferIndex) <= 0) {
  37.                     i = -1;
  38.                     advance = false;
  39.                 }
  40.                   //进行分配工作
  41.                 比如一个线程分配到了 0-15这个区间
  42.                  第二个线程就是16-31这个区间  因为默认是16   
  43.                 else if (U.compareAndSwapInt
  44.                          (this, TRANSFERINDEX, nextIndex,
  45.                           nextBound = (nextIndex > stride ?
  46.                                        nextIndex - stride : 0))) {
  47.                     bound = nextBound;
  48.                     i = nextIndex - 1;
  49.                     advance = false;
  50.                 }
  51.             }
  53.             //如果数据迁移工作完成
  54.             if (i < 0 || i >= n || i + n >= nextn) {
  55.                 int sc;
  56.                 if (finishing) {
  57.                     //完成之后赋值 table
  58.                     nextTable = null;
  59.                     table = nextTab;
  60.                     sizeCtl = (n << 1) - (n >>> 1);
  61.                     return;
  62.                 }
  63.                 //如果还未完成 说明还有其他线程正在执行中 协助扩容还未完成
  64.                 if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc - 1)) {
  65.                     if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT)
  66.                         return;
  67.                     finishing = advance = true;
  68.                     i = n; // recheck before commit
  69.                 }
  70.             }
  71.             else if ((f = tabAt(tab, i)) == null)
  72.                 advance = casTabAt(tab, i, null, fwd);
  73.             else if ((fh = f.hash) == MOVED)
  74.                 advance = true; // already processed
  75.             else {
  76.                 //开始迁移
  77.                 synchronized (f) {
  78.                     if (tabAt(tab, i) == f) {
  79.                         Node<K,V> ln, hn;
  80.                         //表示当前节点为普通节点 按照链表或者普通节点的方式进行扩容
  81.                         if (fh >= 0) {
  82.                             int runBit = fh & n;
  83.                             Node<K,V> lastRun = f;
  84.                             for (Node<K,V> p = f.next; p != null; p = p.next) {
  85.                                 int b = p.hash & n;
  86.                                 if (b != runBit) {
  87.                                     runBit = b;
  88.                                     lastRun = p;
  89.                                 }
  90.                             }
  91.                             if (runBit == 0) {
  92.                                 ln = lastRun;
  93.                                 hn = null;
  94.                             }
  95.                             else {
  96.                                 hn = lastRun;
  97.                                 ln = null;
  98.                             }
  99.                             for (Node<K,V> p = f; p != lastRun; p = p.next) {
  100.                                 int ph = p.hash; K pk = p.key; V pv = p.val;
  101.                                 if ((ph & n) == 0)
  102.                                     ln = new Node<K,V>(ph, pk, pv, ln);
  103.                                 else
  104.                                     hn = new Node<K,V>(ph, pk, pv, hn);
  105.                             }
  106.                             setTabAt(nextTab, i, ln);
  107.                             setTabAt(nextTab, i + n, hn);
  108.                             setTabAt(tab, i, fwd);
  109.                             advance = true;
  110.                         }
  111.                         //表示当前节点为红黑树、
  112.                         //当红黑树节点小于6 会转换成链表
  113.                         else if (f instanceof TreeBin) {
  114.                             TreeBin<K,V> t = (TreeBin<K,V>)f;
  115.                             TreeNode<K,V> lo = null, loTail = null;
  116.                             TreeNode<K,V> hi = null, hiTail = null;
  117.                             //lc 低位链  hc 高位链
  118.                             int lc = 0, hc = 0;
  119.                             for (Node<K,V> e = t.first; e != null; e = e.next) {
  120.                                 int h = e.hash;
  121.                                 TreeNode<K,V> p = new TreeNode<K,V>
  122.                                     (h, e.key, e.val, null, null);
  123.                                 // == 0 表示需要迁移的数据
  124.                                 if ((h & n) == 0) {
  125.                                     if ((p.prev = loTail) == null)
  126.                                         lo = p;
  127.                                     else
  128.                                         loTail.next = p;
  129.                                     loTail = p;
  130.                                     ++lc;
  131.                                 }
  132.                                 //不需要迁移的数据
  133.                                 else {
  134.                                     if ((p.prev = hiTail) == null)
  135.                                         hi = p;
  136.                                     else
  137.                                         hiTail.next = p;
  138.                                     hiTail = p;
  139.                                     ++hc;
  140.                                 }
  141.                             }
  142.                             ln = (lc <= UNTREEIFY_THRESHOLD) ? untreeify(lo) :
  143.                                 (hc != 0) ? new TreeBin<K,V>(lo) : t;
  144.                             hn = (hc <= UNTREEIFY_THRESHOLD) ? untreeify(hi) :
  145.                                 (lc != 0) ? new TreeBin<K,V>(hi) : t;
  146.                             setTabAt(nextTab, i, ln);
  147.                             setTabAt(nextTab, i + n, hn);
  148.                             setTabAt(tab, i, fwd);
  149.                             advance = true;
  150.                         }
  151.                     }
  152.                 }
  153.             }
  154.         }
  155.     }

高低位迁移

17d56a324ba145128b4ba5c7e7627adb.png
低位(扩容线程数量)表示不需要迁移的元素
高位(扩容标记)表示需要迁移的元素

分段锁设计 提高统计元素数量的性能

当线程竞争不激烈时 直接使用baseCount+1来增加元素的个数
当线程竞争激烈时 构建一个 CountCell数组 默认长度为2 通过随机算法选择一个 CounterCell针对该CounterCell中的value进行保存

  1.  private final void addCount(long x, int check) {
  2.         CounterCell[] as; long b, s;
  3.         if ((as = counterCells) != null ||
  4.             //对 baseCount进行累加 当有竞争的时候会返回 false
  5.             !U.compareAndSwapLong(this, BASECOUNT, b = baseCount, s = b + x)) {
  6.             CounterCell a; long v; int m;
  7.             boolean uncontended = true;
  8.             // as == null 说明CounterCell 数组还未初始化
  9.             // (m = as.length - 1) < 0  说明CounterCell 数组还未初始化
  10.             //(a = as[ThreadLocalRandom.getProbe() & m]) == null  说明CounterCell已经创建 但是通过探针hash定位发现数组中还没有实例 说明这个数组中还存在没有CounterCell实例对象的情况
  11.             //U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x)) 说明当前 CounterCell数组每个位置都有一个CounterCell实例对象 直接通过 cas操作针对上一个步骤获得的 CounterCell的value值进行累加 如果失败则说明存在竞争
  13.             if (as == null || (m = as.length - 1) < 0 ||
  14.                 (a = as[ThreadLocalRandom.getProbe() & m]) == null ||
  15.                 !(uncontended =
  16.                   U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))) {
  17.                 //计算size
  18.                 fullAddCount(x, uncontended);
  19.                 return;
  20.             }
  21.             if (check <= 1)
  22.                 return;
  23.             //CounterCell数组的个数和
  24.             s = sumCount();
  25.         }
  26.      //是否需要扩容
  27.         if (check >= 0) {
  28.             Node<K,V>[] tab, nt; int n, sc;
  29.             while (s >= (long)(sc = sizeCtl) && (tab = table) != null &&
  30.                    (n = tab.length) < MAXIMUM_CAPACITY) {
  31.                 int rs = resizeStamp(n);
  32.                 if (sc < 0) {
  33.                     if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
  34.                         sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||
  35.                         transferIndex <= 0)
  36.                         break;
  37.                     if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))
  38.                         transfer(tab, nt);
  39.                 }
  40.                 else if (U.compareAndSwapInt(this, SIZECTL, sc,
  41.                                              (rs << RESIZE_STAMP_SHIFT) + 2))
  42.                     transfer(tab, null);
  43.                 s = sumCount();
  44.             }
  45.         }
  46.     }
  1.  private final void fullAddCount(long x, boolean wasUncontended) {
  2.         int h;
  3.         if ((h = ThreadLocalRandom.getProbe()) == 0) {
  4.             ThreadLocalRandom.localInit();      // force initialization
  5.             h = ThreadLocalRandom.getProbe();
  6.             wasUncontended = true;
  7.         }
  8.         boolean collide = false;                // True if last slot nonempty
  9.         for (;;) {
  10.             CounterCell[] as; CounterCell a; int n; long v;
  11.             //表示数组已经初始化完成
  12.             if ((as = counterCells) != null && (n = as.length) > 0) {
  13.                 if ((a = as[(n - 1) & h]) == null) {
  14.                     if (cellsBusy == 0) {    
  15.                        // Try to attach new Cell
  16.                         //创建 CounterCell对象
  17.                         CounterCell r = new CounterCell(x); // Optimistic create
  19.                         if (cellsBusy == 0 &&
  20.                             //cas 当前线程独占
  21.                             U.compareAndSwapInt(this, CELLSBUSY, 0, 1)) {
  22.                             boolean created = false;
  23.                             try {               // Recheck under lock
  24.                                 CounterCell[] rs; int m, j;
  25.                                 if ((rs = counterCells) != null &&
  26.                                     (m = rs.length) > 0 &&
  27.                                     rs[j = (m - 1) & h] == null) {
  28.                                     //将新构建的元素个数 保存到 rs[j]
  29.                                     rs[j] = r;
  30.                                     created = true;
  31.                                 }
  32.                             } finally {
  33.                                 cellsBusy = 0;
  34.                             }
  35.                             if (created)
  36.                                 break;
  37.                             continue;           // Slot is now non-empty
  38.                         }
  39.                     }
  40.                     collide = false;
  41.                 }
  42.                 else if (!wasUncontended)       // CAS already known to fail
  43.                     wasUncontended = true;      // Continue after rehash
  44.                 else if (U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))
  45.                     break;
  46.                 else if (counterCells != as || n >= NCPU)
  47.                     collide = false;            // At max size or stale
  48.                 else if (!collide)
  49.                     collide = true;
  50.                 else if (cellsBusy == 0 &&
  51.                          U.compareAndSwapInt(this, CELLSBUSY, 0, 1)) {
  52.                     try {
  53.                         //竞争激烈 数组的扩容
  54.                         if (counterCells == as) {// Expand table unless stale
  55.                             //在原有的基础上扩容一倍  
  56.                             CounterCell[] rs = new CounterCell[n << 1];
  57.                             for (int i = 0; i < n; ++i)
  58.                                 然后在进行数据迁移 
  59.                                 rs[i] = as[i];
  60.                             //把扩容后的对象赋值给 counterCells
  61.                             counterCells = rs;
  62.                         }
  63.                     } finally {
  64.                         cellsBusy = 0;
  65.                     }
  66.                     collide = false;
  67.                     continue;                   // Retry with expanded table
  68.                 }
  69.                 h = ThreadLocalRandom.advanceProbe(h);
  70.             }
  71.                 // 抢占到锁 将 cellsBusy 修改成1 表示独占状态
  72.             else if (cellsBusy == 0 && counterCells == as &&
  73.                      U.compareAndSwapInt(this, CELLSBUSY, 0, 1)) {
  74.                 boolean init = false;
  75.                 try {                           // Initialize table
  76.                     if (counterCells == as) {
  77.                         //创建初始化为2的 CounterCell数组
  78.                         CounterCell[] rs = new CounterCell[2];
  79.                         //把增加的元素个数x 保存到  rs[h & 1]的位置
  80.                         rs[h & 1] = new CounterCell(x);
  81.                         //把 rs赋值给全局对象 counterCells
  82.                         counterCells = rs;
  83.                         init = true;
  84.                     }
  85.                 } finally {
  86.                     cellsBusy = 0;
  87.                 }
  88.                 if (init)
  89.                     break;
  90.             }
  91.             //对数组指定位置的元素进行累加
  92.             else if (U.compareAndSwapLong(this, BASECOUNT, v = baseCount, v + x))
  93.                 break;                          // Fall back on using base
  94.         }
  95.     }

红黑树

特殊的平衡二叉树 特征是二叉树左子树和右子树的高度差绝对值不超过1

红黑树的特征

1.红黑树的每个节点颜色只能是红色或者黑色
2.根节点的颜色是黑色
3.如果当前节点的颜色是红色 name它的子节点的颜色必须是黑色
4.所有叶子节点的颜色都是黑色
5.从任一节点到其每个叶子节点的所有普通路径都包含相同数目的黑色节点

左旋

以某个节点作为旋转节点(支点) 其右子节变为旋转节点的父节点 右子节点对应的左子节点变为旋转接点的右子节点 ，右子节点对应的右子节点保持不变，旋转节点的左子节点保持不变
Dingtalk_20211102110517.jpg

右旋

以某个节点作为旋转节点 其左子节点变为旋转节点的父节点，左子节点对应的右子节点为旋转节点的左子节点 左子节点对应的左子节点保持不变 旋转节点的右子节点保持不变

Dingtalk_20211102110526.jpg

变色

节点的颜色由红色变成黑色 或者由黑色变成红色 保持红黑树的平衡 变色操作发生在红黑树的插入或者删除操作之后

向红黑树插入新的节点时 新节点的颜色一般设置成红色(红色节点破坏红黑树的基本原则可能性较小) 可能会破坏红黑树的部分特性 比如每个红色节点的两个子节点都是黑色节点 通过变色可以解决这些问题

红黑树的场景和规则

红黑树为空树

当前红黑树没有任何节点 那么插入的节点就可以作为红黑树的根节点 并且把节点设置为黑色

插入父节点为黑色

如果插入的父节点为黑色 新添加的节点为红色 直接添加即可 不需要做自平衡操作

插入节点的父节点为红色

插入的新节点为红色 如果父节点也为红色(如果当前新添加的节点的父节点为红色 意味着该父节点一定不是根节点 因为红黑树的根节点一定是黑色 所以插入节点存在组先节点) 违反了如果当前节点为红色 那么它的子节点必须为黑色的规则 因此需要进行自平衡操作 这时需要看叔叔节点的状态
1.叔叔节点为红色 说明 父亲节点和叔叔节点都已经无法协助实现平衡了 所以直接把父节点和叔叔节点都设置成黑色然后把祖父节点设置成红色
2.叔叔节点为黑色 说明叔叔节点还有空间来协助新的节点实现平衡 分为以下几种情况
2.1 当前新的节点为左子节点
2.1.1 新节点的父亲节点是左子节点 把新节点的父亲节点设置为黑色 把祖父节点设置为红色 以祖父节点为旋转节点进行旋转
2.1.2 新节点的父亲节点是右子节点 以新节点的父节点作为旋转节点进行右旋 把祖父节点设置为红色 把新节点设置为黑色 最后以祖父节点作为旋转节点进行左旋

2.2 当前新的节点为右子节点
2.2.1 新节点的父节点是左子节点 以新节点的父节点作为旋转节点进行左旋 再把新添加的节点设置为黑色 把祖父节点设置为红色 最后以祖父节点作为旋转节点进行右旋
2.2.2 新节点的父节点是右子节点 把新节点的父节点设置为黑色 把祖父节点设置为红色 以祖父节点作为旋转接点进行左旋
3.节点的矫正从当前插入节点的位置开始 把当前节点这颗小树(祖父节点以下)调整后 继续向上调整直至平衡
4.父节点和叔叔节点都为红色 就直接把这两个节点全部设置为黑色 然后把祖父节点设置为红色 相当于把不平衡的问题抛给了祖父节点把祖父节点因为这个变化导致不平衡name重复这个过程继续进行调整
5.父节点为红色 叔叔节点为黑色 如果当前节点跟父节点左右长度不一致 则旋转父节点使其变为一致之后再旋转祖父节点

Java并发集合

ConcurrentLinkedQueue

基于链表结构实现的并发安全的队列

ConcurrentLinkedDeque

基于双向链表实现的并发安全的双端队列

ConcurrentSkipListMap

基于跳表实现且有序的哈希表