1.

2. jdk8

2.1 重要的属性与内部类

  1. // 当初始化或扩容完成后，下一次扩容的阈值大小
  2. // 默认为0；初始化时，为-1；扩容时，为-（1+扩容线程数）
  3. private transient volatile int sizeCtl;
  5. // 整个concurrentHashmap就是一个 node[] 数组
  6. static class Node<K,V> implements Map.Entry<K,V> { }
  8. // hash表
  9. transient volatile Node<K,V>[] table;
  10. // 扩容时的新hash表
  11. private transient volatile Node<K,V>[] nextTable;
  13. // 扩容时如果整个bin迁移完毕，用ForwardingNode作为旧table bin的头结点（做个标记）
  14. static final class ForwardingNode<K,V> extends Node<K,V> {}
  16. // 用在compute以及conputeIfAbsent时，用来占位，计算完成后替换为普通Node
  17. static final class ReservationNode<K,V> extends Node<K,V> { }
  19. // 作为treebin的头结点，存储root和first（红黑树）
  20. static final class TreeBin<K,V> extends Node<K,V> { }
  22. //  作为treebin的结点，存储parent ,left, right（红黑树）
  23. static final class TreeNode<K,V> extends Node<K,V> { }
  25. // 获取node[]中第i个node
  26. static final <K,V> Node<K,V> tabAt(Node<K,V>[] tab, int i) { }
  28. // cas修改node[]中第i个node的值，c为旧值，v为新值
  29. static final <K,V> boolean casTabAt(Node<K,V>[] tab, int i,
  30.                                         Node<K,V> c, Node<K,V> v) { }
  32. // 直接修改node[]中第i个node的值，v为新值
  33.  static final <K,V> void setTabAt(Node<K,V>[] tab, int i, Node<K,V> v) { }

2.2 构造方法

懒惰初始化，构造房中仅仅计算了table的大小，以后在第一次使用时才会真正创建

  1.    public ConcurrentHashMap(int initialCapacity,
  2.                              float loadFactor, int concurrencyLevel) {
  3.         if (!(loadFactor > 0.0f) || initialCapacity < 0 || concurrencyLevel <= 0)
  4.             throw new IllegalArgumentException();
  5.         if (initialCapacity < concurrencyLevel)   // Use at least as many bins
  6.             initialCapacity = concurrencyLevel;   // as estimated threads
  7.         long size = (long)(1.0 + (long)initialCapacity / loadFactor);
  8.         // 2的幂次方
  9.         int cap = (size >= (long)MAXIMUM_CAPACITY) ?
  10.             MAXIMUM_CAPACITY : tableSizeFor((int)size);
  11.         this.sizeCtl = cap;
  12.     }

2.3 get方法

  • 计算hash值，定位到该table索引位置，如果是首节点符合就返回
  • 如果遇到扩容的时候，会调用标志正在扩容节点ForwardingNode的find方法，查找该节点，匹配就返回
  • 以上都不符合的话，就往下遍历节点，匹配就返回，否则最后就返回null
  1. public V get(Object key) {
  2.         Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
  3.         // spread方法保证返回结果是正数
  4.         int h = spread(key.hashCode());
  5.         // table 不为空 && 长度>0 && 当前数组位置有元素
  6.         if ((tab = table) != null && (n = tab.length) > 0 &&
  7.             (e = tabAt(tab, (n - 1) & h)) != null) {
  8.             // 如果头结点e的hash是已经要找的key，就判断内容是否相等
  9.             if ((eh = e.hash) == h) {
  10.                 if ((ek = e.key) == key || (ek != null && key.equals(ek)))
  11.                     return e.val;
  12.             }
  13.             // 如果e的hash为负数表示改bin在扩容中（扩容的ForwardingNode就是-1）在新table中找，
  14.             // 或者是treebin(-2)，这时调用find方法查找
  15.             else if (eh < 0)
  16.                 return (p = e.find(h, key)) != null ? p.val : null;
  17.             // 正常遍历链表
  18.             while ((e = e.next) != null) {
  19.                 if (e.hash == h &&
  20.                     ((ek = e.key) == key || (ek != null && key.equals(ek))))
  21.                     return e.val;
  22.             }
  23.         }
  24.         return null;
  25.     }

2.4 put方法

  1. public V put(K key, V value) {
  2.         return putVal(key, value, false);
  3.     }
  1. // onlyIfAbsent值表示遇到相同的key是否用新值代替旧值(false就是代替，true就是不代替）
  2. final V putVal(K key, V value, boolean onlyIfAbsent) {
  3.         // 不允许有null的键值对
  4.         if (key == null || value == null) throw new NullPointerException();
  5.         // 保证key的hashcode为正数
  6.         int hash = spread(key.hashCode());
  7.         int binCount = 0;
  8.         // 死循环
  9.         for (Node<K,V>[] tab = table;;) {
  10.             // f是链表头结点，fh是链表头结点的hash，i是链表在table中的下标
  11.             Node<K,V> f; int n, i, fh;
  12.             // table为null，创建table
  13.             if (tab == null || (n = tab.length) == 0)
  14.                 // 初始化table使用cas，无需synchronized，创建成功，进入下一轮循环
  15.                 tab = initTable();
  16.             // 否则，查看该位置index是否是null的，如果是创建链表头结点
  17.             else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
  18.                 // 添加链表头使用cas，无需synchronized
  19.                 if (casTabAt(tab, i, null,
  20.                              new Node<K,V>(hash, key, value, null)))
  21.                     // 成功就break，失败就继续循环
  22.                     break;                   // no lock when adding to empty bin
  23.             }
  24.             // 头结点不为null
  25.             // 帮忙扩容，看这个节点是不是forwardNode，如果是，就知道别的线程正在扩容
  26.             else if ((fh = f.hash) == MOVED)
  27.                 // 帮忙扩容，进行下一轮循环
  28.                 tab = helpTransfer(tab, f);
  29.             else {
  30.                 // 正式扩容
  31.                 V oldVal = null;
  32.                 // 锁住链表头结点
  33.                 synchronized (f) {
  34.                     // 再次确认链表头节点没有被移动
  35.                     if (tabAt(tab, i) == f) {
  36.                         // 链表
  37.                         if (fh >= 0) {
  38.                             // 链表长度，初始值为1
  39.                             binCount = 1;
  40.                             // 遍历链表
  41.                             for (Node<K,V> e = f;; ++binCount) {
  42.                                 K ek;
  43.                                 // 找到相同的key
  44.                                 if (e.hash == hash &&
  45.                                     ((ek = e.key) == key ||
  46.                                      (ek != null && key.equals(ek)))) {
  47.                                     oldVal = e.val;
  48.                                     // 更新并break
  49.                                     if (!onlyIfAbsent)
  50.                                         e.val = value;
  51.                                     break;
  52.                                 }
  53.                                 Node<K,V> pred = e;
  54.                                 // 最后一个节点，新增node，追加至链表尾部
  55.                                 if ((e = e.next) == null) {
  56.                                     pred.next = new Node<K,V>(hash, key,
  57.                                                               value, null);
  58.                                     break;
  59.                                 }
  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.                 // 树化
  78.                 if (binCount != 0) {
  79.                     // 如果链表长度 >= 树化阈值（8），链表转换成红黑树（总数组长度>=64才转换，不然就扩容）
  80.                     if (binCount >= TREEIFY_THRESHOLD)
  81.                         treeifyBin(tab, i);
  82.                     if (oldVal != null)
  83.                         return oldVal;
  84.                     break;
  85.                 }
  86.             }
  87.         }
  88.         // 增加size计数，多个累加单元进行计数。
  89.         addCount(1L, binCount);
  90.         return null;
  91.     }

initTable方法

  1. private final Node<K,V>[] initTable() {
  2.         Node<K,V>[] tab; int sc;
  3.         // 没有被创建
  4.         while ((tab = table) == null || tab.length == 0) {
  5.             // 让其他线程yield，节约资源
  6.             if ((sc = sizeCtl) < 0)
  7.                 Thread.yield(); // lost initialization race; just spin
  8.             // 尝试将 sizeCtl设置为-1，表示初始化
  9.             else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
  10.                 // 获得锁，创建table，这是其他线程cas失败会在while中yield直至table创建
  11.                 try {
  12.                     // 确认没有创建
  13.                     if ((tab = table) == null || tab.length == 0) {
  14.                         // sc是初始容量，没有给就用默认值16
  15.                         int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
  16.                         @SuppressWarnings("unchecked")
  17.                         Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
  18.                         table = tab = nt;
  19.                         // 下次扩容时的阈值
  20.                         sc = n - (n >>> 2);
  21.                     }
  22.                 } finally {
  23.                     // 恢复成正数，使其他忙等待的线程进入compareAndSwapInt比较，此时sc的值改变了，就退出来了
  24.                     sizeCtl = sc;
  25.                 }
  26.                 break;
  27.             }
  28.         }
  29.         return tab;
  30.     }

addCount方法

  1. // check 是之前binCount的个数
  2. private final void addCount(long x, int check) {
  3.         CounterCell[] as; long b, s;
  4.         // 累加单元数组不为null，已经有了，向cell累加
  5.         if ((as = counterCells) != null ||
  6.             // 还没有，向baseCount累加
  7.             !U.compareAndSwapLong(this, BASECOUNT, b = baseCount, s = b + x)) {
  8.             // 累加失败了
  9.             CounterCell a; long v; int m;
  10.             boolean uncontended = true;
  11.             // 还没有counterCells
  12.             if (as == null || (m = as.length - 1) < 0 ||
  13.                 // 还没有cell
  14.                 (a = as[ThreadLocalRandom.getProbe() & m]) == null ||
  15.                 // cell cas增加计数失败
  16.                 !(uncontended =
  17.                   U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))) {
  18.                 // 创建累加单元数组和cell，累加重试
  19.                 fullAddCount(x, uncontended);
  20.                 return;
  21.             }
  22.             // 检查链表长度
  23.             if (check <= 1)
  24.                 return;
  25.             // 获取元素个数
  26.             s = sumCount();
  27.         }
  28.         if (check >= 0) {
  29.             Node<K,V>[] tab, nt; int n, sc;
  30.             while (s >= (long)(sc = sizeCtl) && (tab = table) != null &&
  31.                    (n = tab.length) < MAXIMUM_CAPACITY) {
  32.                 int rs = resizeStamp(n);
  33.                 // sc改成-1，扩容标识
  34.                 if (sc < 0) {
  35.                     if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
  36.                         sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||
  37.                         transferIndex <= 0)
  38.                         break;
  39.                     // newtable已经创建了，帮忙扩容
  40.                     if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))
  41.                         transfer(tab, nt);
  42.                 }
  43.                 // 需要扩容，这时newtable未创建（懒惰初始化）
  44.                 else if (U.compareAndSwapInt(this, SIZECTL, sc,
  45.                                              (rs << RESIZE_STAMP_SHIFT) + 2))
  46.                     transfer(tab, null);
  47.                 s = sumCount();
  48.             }
  49.         }
  50.     }

2.5 size计算流程

size计算实际发生在put、remove改变集合元素的操作之中

  • 没有竞争发生时，向baseCount累加计数
  • 有竞争发生，新建counterCells，向其中一个cell累加计数
    • counterCells初始有两个cell
    • 如果计数竞争比较激烈，会创建新的cell来累加计数
  • 注意：size计数结果有一定误差，多线程条件下，容易出现误差。 ```java public int size() {
    1.   long n = sumCount();
    2.   return ((n < 0L) ? 0 :
    3.           (n > (long)Integer.MAX_VALUE) ? Integer.MAX_VALUE :
    4.           (int)n);
    }

final long sumCount() { CounterCell[] as = counterCells; CounterCell a; long sum = baseCount; // 将baseCount与所有cell计数累加 if (as != null) { for (int i = 0; i < as.length; ++i) { if ((a = as[i]) != null) sum += a.value; } } return sum; }

  1. <a name="H4xsb"></a>
  2. ## 2.6 transfer扩容
  3. ```java
  4. private final void transfer(Node<K,V>[] tab, Node<K,V>[] nextTab) {
  5.         int n = tab.length, stride;
  6.         if ((stride = (NCPU > 1) ? (n >>> 3) / NCPU : n) < MIN_TRANSFER_STRIDE)
  7.             stride = MIN_TRANSFER_STRIDE; // subdivide range
  8.         // 初始化新table
  9.         if (nextTab == null) {            // initiating
  10.             try {
  11.                 @SuppressWarnings("unchecked")
  12.                 Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n << 1];
  13.                 nextTab = nt;
  14.             } catch (Throwable ex) {      // try to cope with OOME
  15.                 sizeCtl = Integer.MAX_VALUE;
  16.                 return;
  17.             }
  18.             nextTable = nextTab;
  19.             transferIndex = n;
  20.         }
  21.         // 移动数据
  22.         int nextn = nextTab.length;
  23.         ForwardingNode<K,V> fwd = new ForwardingNode<K,V>(nextTab);
  24.         boolean advance = true;
  25.         boolean finishing = false; // to ensure sweep before committing nextTab
  26.         for (int i = 0, bound = 0;;) {
  27.             Node<K,V> f; int fh;
  28.             while (advance) {
  29.                 int nextIndex, nextBound;
  30.                 if (--i >= bound || finishing)
  31.                     advance = false;
  32.                 else if ((nextIndex = transferIndex) <= 0) {
  33.                     i = -1;
  34.                     advance = false;
  35.                 }
  36.                 else if (U.compareAndSwapInt
  37.                          (this, TRANSFERINDEX, nextIndex,
  38.                           nextBound = (nextIndex > stride ?
  39.                                        nextIndex - stride : 0))) {
  40.                     bound = nextBound;
  41.                     i = nextIndex - 1;
  42.                     advance = false;
  43.                 }
  44.             }
  45.             if (i < 0 || i >= n || i + n >= nextn) {
  46.                 int sc;
  47.                 if (finishing) {
  48.                     nextTable = null;
  49.                     table = nextTab;
  50.                     sizeCtl = (n << 1) - (n >>> 1);
  51.                     return;
  52.                 }
  53.                 if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc - 1)) {
  54.                     if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT)
  55.                         return;
  56.                     finishing = advance = true;
  57.                     i = n; // recheck before commit
  58.                 }
  59.             }
  60.             // 链表头是null，说明处理完了，就把他替换成ForwardingNode
  61.             else if ((f = tabAt(tab, i)) == null)
  62.                 advance = casTabAt(tab, i, null, fwd);
  63.             // 如果已经是ForwardingNode，就处理下一个链表
  64.             else if ((fh = f.hash) == MOVED))
  65.                 advance = true; // already processed
  66.             else {
  67.                 // 链表头有元素，锁住链表
  68.                 synchronized (f) {
  69.                     // 
  70.                     if (tabAt(tab, i) == f) {
  71.                         Node<K,V> ln, hn;
  72.                         // 普通节点，转移节点类似hashmap里的，高位低位链表转移
  73.                         if (fh >= 0) {
  74.                             int runBit = fh & n;
  75.                             Node<K,V> lastRun = f;
  76.                             for (Node<K,V> p = f.next; p != null; p = p.next) {
  77.                                 int b = p.hash & n;
  78.                                 if (b != runBit) {
  79.                                     runBit = b;
  80.                                     lastRun = p;
  81.                                 }
  82.                             }
  83.                             if (runBit == 0) {
  84.                                 ln = lastRun;
  85.                                 hn = null;
  86.                             }
  87.                             else {
  88.                                 hn = lastRun;
  89.                                 ln = null;
  90.                             }
  91.                             for (Node<K,V> p = f; p != lastRun; p = p.next) {
  92.                                 int ph = p.hash; K pk = p.key; V pv = p.val;
  93.                                 if ((ph & n) == 0)
  94.                                     ln = new Node<K,V>(ph, pk, pv, ln);
  95.                                 else
  96.                                     hn = new Node<K,V>(ph, pk, pv, hn);
  97.                             }
  98.                             setTabAt(nextTab, i, ln);
  99.                             setTabAt(nextTab, i + n, hn);
  100.                             setTabAt(tab, i, fwd);
  101.                             advance = true;
  102.                         }
  103.                         // 红黑树，类似hashmap里面的红黑树转移，隐藏的双向链表，高低位链表转移
  104.                         else if (f instanceof TreeBin) {
  105.                             TreeBin<K,V> t = (TreeBin<K,V>)f;
  106.                             TreeNode<K,V> lo = null, loTail = null;
  107.                             TreeNode<K,V> hi = null, hiTail = null;
  108.                             int lc = 0, hc = 0;
  109.                             for (Node<K,V> e = t.first; e != null; e = e.next) {
  110.                                 int h = e.hash;
  111.                                 TreeNode<K,V> p = new TreeNode<K,V>
  112.                                     (h, e.key, e.val, null, null);
  113.                                 if ((h & n) == 0) {
  114.                                     if ((p.prev = loTail) == null)
  115.                                         lo = p;
  116.                                     else
  117.                                         loTail.next = p;
  118.                                     loTail = p;
  119.                                     ++lc;
  120.                                 }
  121.                                 else {
  122.                                     if ((p.prev = hiTail) == null)
  123.                                         hi = p;
  124.                                     else
  125.                                         hiTail.next = p;
  126.                                     hiTail = p;
  127.                                     ++hc;
  128.                                 }
  129.                             }
  130.                             ln = (lc <= UNTREEIFY_THRESHOLD) ? untreeify(lo) :
  131.                                 (hc != 0) ? new TreeBin<K,V>(lo) : t;
  132.                             hn = (hc <= UNTREEIFY_THRESHOLD) ? untreeify(hi) :
  133.                                 (lc != 0) ? new TreeBin<K,V>(hi) : t;
  134.                             setTabAt(nextTab, i, ln);
  135.                             setTabAt(nextTab, i + n, hn);
  136.                             setTabAt(tab, i, fwd);
  137.                             advance = true;
  138.                         }
  139.                     }
  140.                 }
  141.             }
  142.         }
  143.     }