ConcurrentHashMap源码分析

Myth丶恋晨 2023-09-24 21:21 209阅读 0赞

format_png

概述

ConcurrentHashMap（CHM）是日常开发中使用频率非常高的一种数据结构，想对于普通的HashMap，CHM提供了线程安全的读写，CHM里面使用了许多比较精妙的优化&操作。本文主要对CHM的整体结构、初始化，查找，插入等做分析。

CHM在1.8之前和之后有比较大的变动，1.8之前主要通过Segment 分段锁 来解决并发问题，1.8及之后就没有这些臃肿的数据结构了，其数据结构与普通的HashMap一样，都是Node数组+链表+红黑树

format_png 1

一颗红黑树应满足如下性质：

  1. 根节点是黑色的

    • 外部节点均为黑色（图中的 leaf 节点，通常在表述的时候会省略）

    • 红色节点的孩子节点必为黑色（通常插入的节点为红色）

    • 从任一外部节点到根节点的沿途，黑节点的数目相等

format_png 2

除了上面基本的数据结构之外，Node节点也是一个需要关心的数据结构，Node节点本质上是单向链表的节点，其中包含key、value、Hash、next属性

  1. staticclassNode<K,V> implementsMap.Entry<K,V> {
  2.     finalint hash;  
  3.     final K key;
  4.     volatile V val;
  5.     volatile Node<K,V> next;
  6. }
  7. 复制代码

ForwardingNode节点

ForwardingNode节点（简称fwd节点）继承自Node节点，主要用于扩容，该节点里面固定Hash值为MOVED(值为-1)，同时持有新表的引用

  1. staticfinalclassForwardingNode<K,V> extendsNode<K,V> {
  2.     final Node<K,V>[] nextTable;
  3.     ForwardingNode(Node<K,V>[] tab) {
  4.         super(MOVED, null, null, null);
  5.         this.nextTable = tab;
  6.     }
  8.     Node<K,V> find(int h, Object k) {
  9.         ...
  10.     }
  11. }
  12. 复制代码

TreeNode

TreeNode节点也继承自Node节点，用于表示红黑树上的节点，主要属性如下所示

  1. staticfinalclassTreeNode<K,V> extendsNode<K,V> {
  2.     TreeNode<K,V> parent;  // 父节点
  3.     TreeNode<K,V> left;    // 左儿子
  4.     TreeNode<K,V> right;   // 右儿子
  5.     TreeNode<K,V> prev;    // 记录前驱节点，用于恢复链表boolean red;
  6. }
  7. 复制代码

TreeBin

TreeBin节点内部持有TreeNode节点的引用，内部实现了读写锁用于控制多线程并发在红黑树上的操作，主要属性如下所示

  1. staticfinalclassTreeBin<K,V> extendsNode<K,V> {
  2.     TreeNode<K,V> root;  // 红黑树根节点volatile TreeNode<K,V> first;  // 链表根节点，读写分离时会用到volatile Thread waiter;  // 当前线程volatileint lockState;  // 当前红黑树的锁状态// values for lockStatestaticfinalintWRITER=1; // set while holding write lockstaticfinalintWAITER=2; // set when waiting for write lockstaticfinalintREADER=4; // 读锁标记
  3. }
  4. 复制代码

SizeCtl

除了数据结构需要说明外，SizeCtl也是理解CHM十分重要的一个字段，他是一个整数，不同的值表示不同的状态

  1. 当SizeCtl > 0时，表示下次扩展的阈值，其中阈值计算方式：数组长度 * 扩展阈值（注意这里是固定的0.75）

  2. 当SizeCtl = 0时，表示还没有开始初始化

  3. 当sizeCtl = -1是，表示此时正在进行初始化

  4. 当SizeCtl < -1时，表示此时正在进行扩展，其中高16位表示扩容标识戳，低16位表示参与扩容的线程数+1

初始化

CHM的初始化是惰性初始化的，即当我们使用ConCurrentHashMap map = new ConcurrentHashMap(20);创建一个CHM对象时，并不会真正的创建对象，而是只有在put时才会真正开始创建对象。

  1. publicConcurrentHashMap(int initialCapacity) {
  2.     // 只是检查参数是否合理，并设置好数组容量和扩容阈值if (initialCapacity < 0)
  3.     thrownewIllegalArgumentException();
  4. intcap= ((initialCapacity >= (MAXIMUM_CAPACITY >>> 1)) ?
  5.            MAXIMUM_CAPACITY :
  6.            tableSizeFor(initialCapacity + (initialCapacity >>> 1) + 1));
  7. this.sizeCtl = cap;
  8. }
  9. 复制代码

初始化流程

  1. privatefinal Node<K,V>[] initTable() {
  2.     Node<K,V>[] tab; int sc;
  3.     // 判空，注意这里是while，当线程苏醒后会记性检查直到初始化完毕while ((tab = table) == null || tab.length == 0) {
  4.         // 如果其他线程正在初始化，则让出cpuif ((sc = sizeCtl) < 0)
  5.             Thread.yield(); // lost initialization race; just spinelseif (U.compareAndSwapInt(this, SIZECTL, sc, -1)) { // 当前线程尝试获取创建数组的重任try {
  6.                 // 这里需要再进行判断是否为空，防止当前线程创建完毕后又有其他线程进来重复创建if ((tab = table) == null || tab.length == 0) {
  7.                     intn= (sc > 0) ? sc : DEFAULT_CAPACITY;
  8.                     @SuppressWarnings("unchecked")
  9.                         Node<K,V>[] nt = (Node<K,V>[])newNode<?,?>[n];
  10.                     table = tab = nt;
  11.                     // 设置阈值为0.75n
  12.                     sc = n - (n >>> 2);
  13.                 }
  14.             } finally {
  15.                 sizeCtl = sc;
  16.             }
  17.             break;
  18.         }
  19.     }
  20.     return tab;
  21. }
  22. 复制代码

查找

get方法进行查找，针对不同情况有不同处理

  1. public V get(Object key) {
  2.     Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
  3. // 扰动运算inth= spread(key.hashCode());
  4. // 判断表是否为空，表长度是否为0，以及元素对应下标是否为空if ((tab = table) != null && (n = tab.length) > 0 &&
  5.     (e = tabAt(tab, (n - 1) & h)) != null) {
  6.     // 判断当前下边下是否是我们要找到值if ((eh = e.hash) == h) {
  7.         if ((ek = e.key) == key || (ek != null && key.equals(ek)))
  8.             return e.val;
  9.     }
  10.     elseif (eh < 0) // 判断Node节点的Hash值是否小于0，如果小于0的话，则会在他的子类上进行查找//这里情况比较复杂，不同的节点有不同的处理，如果当前节点为fwd节点，则去新表上找，如果为红黑树//节点，则在红黑树上进行查找，后文会展开红黑树上的查找流程return (p = e.find(h, key)) != null ? p.val : null;
  11.     // 普通链表查找while ((e = e.next) != null) {
  12.         if (e.hash == h &&
  13.             ((ek = e.key) == key || (ek != null && key.equals(ek))))
  14.             return e.val;
  15.     }
  16. }
  17. returnnull;
  18. }
  19. 复制代码

插入

  1. final V putVal(K key, V value, boolean onlyIfAbsent) {
  2.     if (key == null || value == null) thrownewNullPointerException();
  3.     inthash= spread(key.hashCode());
  4.     intbinCount=0;
  5.     for (Node<K,V>[] tab = table;;) { // 注意这里是个死循环
  6.         Node<K,V> f; int n, i, fh;
  7.         // 判断是否初始化if (tab == null || (n = tab.length) == 0)
  8.             tab = initTable();
  9.         elseif ((f = tabAt(tab, i = (n - 1) & hash)) == null) { // 判断对应节点是否是空节点，如果是//直接通过cas创建节点if (casTabAt(tab, i, null,
  10.                          newNode<K,V>(hash, key, value, null)))
  11.                 break;                   // no lock when adding to empty bin
  12.         }
  13.         elseif ((fh = f.hash) == MOVED) // 如果当前节点是fwd节点（正在扩容），则帮助扩容
  14.             tab = helpTransfer(tab, f);
  15.         else { 
  16.             VoldVal=null;
  17.             synchronized (f) { // 这里加锁if (tabAt(tab, i) == f) { // 这里需要继续判断是否当前位置的节点没有变化，因为其他线程可能// 改变此节点if (fh >= 0) { // fh >= 0表示当前节点是链表节点，直接next往下找就行
  18.                         binCount = 1;
  19.                         for (Node<K,V> e = f;; ++binCount) {
  20.                             K ek;
  21.                             if (e.hash == hash &&
  22.                                 ((ek = e.key) == key ||
  23.                                  (ek != null && key.equals(ek)))) {
  24.                                 oldVal = e.val;
  25.                                 if (!onlyIfAbsent)
  26.                                     e.val = value;
  27.                                 break;
  28.                             }
  29.                             Node<K,V> pred = e;
  30.                             if ((e = e.next) == null) {
  31.                                 pred.next = newNode<K,V>(hash, key,
  32.                                                           value, null);
  33.                                 break;
  34.                             }
  35.                         }
  36.                     }
  37.                     elseif (f instanceof TreeBin) { // 如果此时节点是TreeBin节点，则需要再红黑树上进行插入，具体// 插入流程后文展开
  38.                         Node<K,V> p;
  39.                         binCount = 2;
  40.                         if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
  41.                                                               value)) != null) {
  42.                             oldVal = p.val;
  43.                             if (!onlyIfAbsent)
  44.                                 p.val = value;
  45.                         }
  46.                     }
  47.                 }
  48.             }
  49.             // 判断是否需要树化if (binCount != 0) {
  50.                 if (binCount >= TREEIFY_THRESHOLD)
  51.                     treeifyBin(tab, i);
  52.                 if (oldVal != null)
  53.                     return oldVal;
  54.                 break;
  55.             }
  56.         }
  57.     }
  58.     // 计数器加1，这里使用了计数器而不是AtomicLong这种
  59.     addCount(1L, binCount);
  60.     returnnull;
  61. }
  62. 复制代码

扩容

CHM的扩容利用了多线程并发的去扩容

CHM在两种条件下会发生扩容：

  1. 单个链表长度大于8，并且数组长度小于64时，会发生扩容

  2. 元素个数超过阈值会发生扩容

扩容流程：

  1. 创建新的Node表，长度为当前数组长度的两倍

  2. 从后往前分配任务区间，最小长度是16，即每个线程每次扩容最少需要迁移16个桶，具体迁移数量由cpu核数决定

  3. 判断当前元素是否为空，为空直接cas操作当前节点为fwd节点，否则判断当前元素是否为fwd节点，如果是，则说明其他线程再次区间扩容，此时需要重新选定区间，否则就对当前桶开始进行迁移

  4. 其他元素在put时如果发现当前桶位是fwd节点，会先协助扩容再put

  5. 最后一个扩容线程退出扩容时再次检查一遍旧桶，更新sizeCtl的值，同时引用新桶

    privatefinalvoidtransfer(Node[] tab, Node[] nextTab) {

    1. intn= tab.length, stride;
    2. // 确定任务长度if ((stride = (NCPU > 1) ? (n >>> 3) / NCPU : n) < MIN_TRANSFER_STRIDE)
    3.     stride = MIN_TRANSFER_STRIDE; // subdivide rangeif (nextTab == null) {            // 第一个扩容的线程需要创建新数组try {
    4.         @SuppressWarnings("unchecked")
    5.             Node<K,V>[] nt = (Node<K,V>[])newNode<?,?>[n << 1];
    6.         nextTab = nt;
    7.     } catch (Throwable ex) {      // try to cope with OOME
    8.         sizeCtl = Integer.MAX_VALUE;
    9.         return;
    10.     }
    11.     nextTable = nextTab;
    12.     transferIndex = n;
    13. }
    14. intnextn= nextTab.length;
    15. ForwardingNode<K,V> fwd = newForwardingNode<K,V>(nextTab);
    16. booleanadvance=true;
    17. booleanfinishing=false; // 用于最后一次检查for (inti=0, bound = 0;;) {
    18.     Node<K,V> f; int fh;
    19.     while (advance) {
    20.         int nextIndex, nextBound;
    21.         if (--i >= bound || finishing) //当前任务是否完成
    22.             advance = false;
    23.         elseif ((nextIndex = transferIndex) <= 0) { // 没有任务了
    24.             i = -1;
    25.             advance = false;
    26.         }
    27.         elseif (U.compareAndSwapInt
    28.                  (this, TRANSFERINDEX, nextIndex,
    29.                   nextBound = (nextIndex > stride ?
    30.                                nextIndex - stride : 0))) { //cas更新transferIndex
    31.             bound = nextBound;
    32.             i = nextIndex - 1;
    33.             advance = false;
    34.         }
    35.     }
    36.     if (i < 0 || i >= n || i + n >= nextn) { // 扩容完毕int sc;
    37.         if (finishing) { // 二次检查后引用新表
    38.             nextTable = null;
    39.             table = nextTab;
    40.             sizeCtl = (n << 1) - (n >>> 1);
    41.             return;
    42.         }
    43.         if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc - 1)) {
    44.             if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT)
    45.                 return;
    46.             finishing = advance = true; 
    47.             i = n; // recheck before commit
    48.         }
    49.     }
    50.     elseif ((f = tabAt(tab, i)) == null) // 当前节点为空，直接赋为fwd
    51.         advance = casTabAt(tab, i, null, fwd);
    52.     elseif ((fh = f.hash) == MOVED) // 其他线程已经迁移好了，此时需要重新分配区间
    53.         advance = true; // already processedelse {
    54.         synchronized (f) { //当前节点开始迁移，这里需要加锁，可能会有读写操作if (tabAt(tab, i) == f) {
    55.                 Node<K,V> ln, hn;
    56.                 if (fh >= 0) { //链表节点 这里只需要判断对应位置是0还是1就可决定迁移到高桶位还是低桶位intrunBit= fh & n;
    57.                     Node<K,V> lastRun = f;
    58.                     for (Node<K,V> p = f.next; p != null; p = p.next) {
    59.                         intb= p.hash & n;
    60.                         if (b != runBit) {
    61.                             runBit = b;
    62.                             lastRun = p;
    63.                         }
    64.                     }
    65.                     if (runBit == 0) {
    66.                         ln = lastRun;
    67.                         hn = null;
    68.                     }
    69.                     else {
    70.                         hn = lastRun;
    71.                         ln = null;
    72.                     }
    73.                     for (Node<K,V> p = f; p != lastRun; p = p.next) {
    74.                         intph= p.hash; Kpk= p.key; Vpv= p.val;
    75.                         if ((ph & n) == 0)
    76.                             ln = newNode<K,V>(ph, pk, pv, ln);
    77.                         else
    78.                             hn = newNode<K,V>(ph, pk, pv, hn);
    79.                     }
    80.                     setTabAt(nextTab, i, ln);
    81.                     setTabAt(nextTab, i + n, hn);
    82.                     setTabAt(tab, i, fwd);
    83.                     advance = true;
    84.                 }
    85.                 elseif (f instanceof TreeBin) { // 红黑树节点，通过判断对应位是否为0决定放到高// 桶位还是低桶位
    86.                     TreeBin<K,V> t = (TreeBin<K,V>)f;
    87.                     TreeNode<K,V> lo = null, loTail = null;
    88.                     TreeNode<K,V> hi = null, hiTail = null;
    89.                     intlc=0, hc = 0;
    90.                     for (Node<K,V> e = t.first; e != null; e = e.next) {
    91.                         inth= e.hash;
    92.                         TreeNode<K,V> p = newTreeNode<K,V>
    93.                             (h, e.key, e.val, null, null);
    94.                         if ((h & n) == 0) {
    95.                             if ((p.prev = loTail) == null)
    96.                                 lo = p;
    97.                             else
    98.                                 loTail.next = p;
    99.                             loTail = p;
    100.                             ++lc;
    101.                         }
    102.                         else {
    103.                             if ((p.prev = hiTail) == null)
    104.                                 hi = p;
    105.                             else
    106.                                 hiTail.next = p;
    107.                             hiTail = p;
    108.                             ++hc;
    109.                         }
    110.                     }
    111.                     ln = (lc <= UNTREEIFY_THRESHOLD) ? untreeify(lo) :
    112.                         (hc != 0) ? newTreeBin<K,V>(lo) : t;
    113.                     hn = (hc <= UNTREEIFY_THRESHOLD) ? untreeify(hi) :
    114.                         (lc != 0) ? newTreeBin<K,V>(hi) : t;
    115.                     setTabAt(nextTab, i, ln);
    116.                     setTabAt(nextTab, i + n, hn);
    117.                     setTabAt(tab, i, fwd);
    118.                     advance = true;
    119.                 }
    120.             }
    121.         }
    122.     }
    123. }

    }
    复制代码

红黑树的读&写

红黑树上的读写操作是基于TreeBin进行的，上文也对其进行了说明。TreeBin其中的lockState表示当前的读写状态

读操作

读操作和写操作可可以是并行的，当有现成正在写或者正在等待写时，读线程可以读，通过代码我们可以发现，此时并没有从红黑树上去读，而是通过链表去读了，这里和IO多路复用里面的epoll函数的底层原理一样。

  1. final Node<K,V> find(int h, Object k) {
  2.     if (k != null) {
  3.         for (Node<K,V> e = first; e != null; ) {
  4.             int s; K ek;
  5.             // WAITER : .....010// WRITER : .....001// READER : .....100if (((s = lockState) & (WAITER|WRITER)) != 0) { //这里表明此时有正在写或者等待写的线程，直接从链表读if (e.hash == h &&
  6.                     ((ek = e.key) == k || (ek != null && k.equals(ek))))
  7.                     return e;
  8.                 e = e.next;
  9.             }
  10.             elseif (U.compareAndSwapInt(this, LOCKSTATE, s, // 表明此时处于无锁或者读锁状态，直接红黑树上查找
  11.                                          s + READER)) {
  12.                 TreeNode<K,V> r, p;
  13.                 try {
  14.                     p = ((r = root) == null ? null :
  15.                          r.findTreeNode(h, k, null));
  16.                 } finally {
  17.                     Thread w;
  18.                     // 读操作完毕后检查是否有写线程在等待，如果有，需要唤醒等待线程// READER|WAITER 表示此时是最后一个读线程if (U.getAndAddInt(this, LOCKSTATE, -READER) ==
  19.                         (READER|WAITER) && (w = waiter) != null)
  20.                         LockSupport.unpark(w);
  21.                 }
  22.                 return p;
  23.             }
  24.         }
  25.     }
  26.     returnnull;
  27. }
  28. 复制代码

写操作

红黑树上的写会先查找是否有对应的值，如果有，则更新值即可，如果没有找到，则插入新的节点，再插入节点的过程中，会调用lockRoot加写锁，如果没有抢到锁，则会调用contentLock方法继续尝试或者将自己挂起

  1. final TreeNode<K,V> putTreeVal(int h, K k, V v) {
  2.     Class<?> kc = null;
  3.     booleansearched=false;
  4.     for (TreeNode<K,V> p = root;;) {
  5.         // 查找是否有值int dir, ph; K pk;
  6.         if (p == null) {
  7.             first = root = newTreeNode<K,V>(h, k, v, null, null);
  8.             break;
  9.         }
  10.         elseif ((ph = p.hash) > h)
  11.             dir = -1;
  12.         elseif (ph < h)
  13.             dir = 1;
  14.         elseif ((pk = p.key) == k || (pk != null && k.equals(pk)))
  15.             return p;
  16.         elseif ((kc == null &&
  17.                   (kc = comparableClassFor(k)) == null) ||
  18.                  (dir = compareComparables(kc, k, pk)) == 0) {
  19.             if (!searched) {
  20.                 TreeNode<K,V> q, ch;
  21.                 searched = true;
  22.                 if (((ch = p.left) != null &&
  23.                      (q = ch.findTreeNode(h, k, kc)) != null) ||
  24.                     ((ch = p.right) != null &&
  25.                      (q = ch.findTreeNode(h, k, kc)) != null))
  26.                     return q;
  27.             }
  28.             dir = tieBreakOrder(k, pk);
  29.         }
  31.         TreeNode<K,V> xp = p;
  32.         if ((p = (dir <= 0) ? p.left : p.right) == null) {
  33.             TreeNode<K,V> x, f = first;
  34.             first = x = newTreeNode<K,V>(h, k, v, f, xp);
  35.             if (f != null)
  36.                 f.prev = x;
  37.             if (dir <= 0)
  38.                 xp.left = x;
  39.             else
  40.                 xp.right = x;
  41.             if (!xp.red)
  42.                 x.red = true;
  43.             else {
  44.                 // 锁住节点，平衡操作可能会导致树结构发生变化
  45.                 lockRoot();
  46.                 try { 
  47.                     root = balanceInsertion(root, x);
  48.                 } finally {
  49.                     unlockRoot();
  50.                 }
  51.             }
  52.             break;
  53.         }
  54.     }
  55.     assertcheckInvariants(root);
  56.     returnnull;
  57. }
  58. 复制代码
  60. privatefinalvoidlockRoot() {
  61.     // 这里尝试去获取写锁，获取不到就调用contenedLock方法if (!U.compareAndSwapInt(this, LOCKSTATE, 0, WRITER))
  62.         contendedLock(); // offload to separate method
  63. }
  65. privatefinalvoidcontendedLock() {
  66.     booleanwaiting=false;
  67.     for (int s;;) {
  68.         // ~WAITER 1111111101// 如果此时处于无锁，则重新获取锁if (((s = lockState) & ~WAITER) == 0) {
  69.             if (U.compareAndSwapInt(this, LOCKSTATE, s, WRITER)) {
  70.                 if (waiting)
  71.                     waiter = null;
  72.                 return;
  73.             }
  74.         } // 此时不是处于waiter状态，即其他线程没有等待，则自己进行等待。如果已经有线程在等待了，会一直自旋，也可看出这里是非公平锁elseif ((s & WAITER) == 0) {
  75.             if (U.compareAndSwapInt(this, LOCKSTATE, s, s | WAITER)) {
  76.                 waiting = true;
  77.                 waiter = Thread.currentThread();
  78.             }
  79.         }
  80.         elseif (waiting) // 将当前线程挂起
  81.             LockSupport.park(this);
  82.     }
  83. }
  85. 复制代码

小结

在红黑树上进行读写时，我们可以发现，当有线程在树上写时，读线程是可以读的，不过不是从红黑树上去读，而不用阻塞，这里可能导致短暂的数据不一致的问题，类似于COW；当有线程在树上读时，此时写线程会将自己挂起，当最后一个读线程查找完毕后会检查是否有些线程在等待，如果有，则唤醒等待写的线程

容器计数

对于一个并发容器来说，当多线程同时写入时，此时容器如何计数成为了一个问题，最简单的是通过AtomicLong来保证原子性与可见性，但是在多线程情况下绝大多数线程会cas失败，然后重试。这无疑是浪费cpu性能的且会有性能瓶颈的。在CHM中引入了，使用分段计数思想，即通过一个数组来计数，当多线程并发计数时，记在数组的不同位置上，最后进行统计。

  1. publicintsize() {
  2.     longn= sumCount();
  3.     return ((n < 0L) ? 0 :
  4.             (n > (long)Integer.MAX_VALUE) ? Integer.MAX_VALUE :
  5.             (int)n);
  6. }
  8. finallongsumCount() {
  9.     CounterCell[] as = counterCells; CounterCell a;
  10.     longsum= baseCount;
  11.     if (as != null) {
  12.         // 累计cells数组for (inti=0; i < as.length; ++i) {
  13.             if ((a = as[i]) != null)
  14.                 sum += a.value;
  15.         }
  16.     }
  17.     return sum;
  18. }
  20. // 计数privatefinalvoidaddCount(long x, int check) {
  21.     CounterCell[] as; long b, s;
  22.     // 如果cells数组不为空或者cas操作baseCount失败，说明此时出现了竞争，需要再cells数组上计数if ((as = counterCells) != null ||
  23.         !U.compareAndSwapLong(this, BASECOUNT, b = baseCount, s = b + x)) {
  24.         CounterCell a; long v; int m;
  25.         booleanuncontended=true;
  26.         if (as == null || (m = as.length - 1) < 0 ||
  27.             (a = as[ThreadLocalRandom.getProbe() & m]) == null ||
  28.             !(uncontended =
  29.               U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))) {
  30.             fullAddCount(x, uncontended);
  31.             return;
  32.         }
  33.         if (check <= 1)
  34.             return;
  35.         s = sumCount();
  36.     }
  37.     // 判断是否需要扩容if (check >= 0) {
  38.         Node<K,V>[] tab, nt; int n, sc;
  39.         while (s >= (long)(sc = sizeCtl) && (tab = table) != null &&
  40.                (n = tab.length) < MAXIMUM_CAPACITY) {
  41.             intrs= resizeStamp(n);
  42.             if (sc < 0) {
  43.                 if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
  44.                     sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||
  45.                     transferIndex <= 0)
  46.                     break;
  47.                 if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))
  48.                     transfer(tab, nt);
  49.             }
  50.             elseif (U.compareAndSwapInt(this, SIZECTL, sc,
  51.                                          (rs << RESIZE_STAMP_SHIFT) + 2))
  52.                 transfer(tab, null);
  53.             s = sumCount();
  54.         }
  55.     }
  56. }
  57. 复制代码

总结

CHM作为线程安全的Map，同时又要兼顾性能，使用了许多巧妙的设计与思想，如位运算，红黑树，无锁并发等等，里面的思想值得我们去学习和借鉴。本篇文章对其进行简单的解读，如有不当之处，还望指出，万分感谢。

作者：code_writer

链接：https://juejin.cn/post/7205455736468668476

发表评论

表情：
评论列表 （有 0 条评论，209人围观）

还没有评论，来说两句吧...

相关阅读