ConcurrentHashMap实现源码

Posted on |

在阅读源码的过程中，推荐一个idea的翻译插件TranslationPlugin，方便阅读源码的注释。本篇主要介绍ConcurrentHashMap在JDK1.8中的实现。

ConcurrentHashMap静态常量

ConcurrentHashMap在设计的过程中涉及到扩容和容器收缩等策略，在静态常量中定义了一些比较关键的阈值，这里介绍几个主要的：

  • private static final int DEFAULT_CAPACITY=16，默认表大小，默认初始化的时候没有传递capacity和concurrentlevel会提供16个hash桶进行映射。否则会根据capacity或者concurrentlevel来确定size的值。

  • private static final int MAXIMUM_CAPACITY = 1 << 30，最大表容量，扩容时会判断最大容量。

  • static final int MIN_TREEIFY_CAPACITY = 64，链表树化时的最小表（数组）容量。在列表树化的时候会检测当前的表（数组）容量，如果小于这个数值会首先进行扩容，扩容之后再进行树化。n为表（数组）长度。

    1
    2
    if ((n = tab.length) < MIN_TREEIFY_CAPACITY)
                  tryPresize(n << 1);

  • private static final float LOAD_FACTOR = 0.75f，装载因子，当数组中已经映射的hash桶已经达到百分之75以上时会自动扩容。代码中可以用 {@code n - (n >>> 2)}代替运算，n为表（数组）的长度。

  • static final int TREEIFY_THRESHOLD = 8，链表调整为tree阈值。当链表中的节点数量超过这个数值的时候会调整为树结构。这个数量至少为2最好是大于8。

  • static final int UNTREEIFY_THRESHOLD = 6，当链表的长度小于这个值的时候自动调节树结构为列表结构。

方法解析

分析一下数组的扩容方法tryPresize，源代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
/**
    * Tries to presize table to accommodate the given number of elements.
    *
    * @param size number of elements (doesn't need to be perfectly accurate)
    */
   private final void tryPresize(int size) {
       int c = (size >= (MAXIMUM_CAPACITY >>> 1)) ? MAXIMUM_CAPACITY :
     	//判断是否为最大超过最大容量的八倍，超过了直接扩容到最大容量。最大容量为1<<30
           tableSizeFor(size + (size >>> 1) + 1);
     	//这里只需要提供一个大概的size，tableSizeFor函数会根据当前的size值匹配一个最近的表大小值，因为我们规定表的大小只能是2的倍数（为了保证在取模进行hash运算的时候可以用（hashcode & n-1） ）
       int sc;
       while ((sc = sizeCtl) >= 0) {
           Node<K,V>[] tab = table; int n;
           if (tab == null || (n = tab.length) == 0) {
             	//如果当前table并没有被初始化，例如在putAll方法中传入一个map，首先进行table的初始化tab
               n = (sc > c) ? sc : c;
               if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
                 //这里采用了循环cas来替换sc的值，最后将sizeCtl赋值为sc的值
                   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;
                   }
               }
           }
           else if (c <= sc || n >= MAXIMUM_CAPACITY)
               break;
           else if (tab == table) {
               int rs = resizeStamp(n);
               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))
                   transfer(tab, null);
           }
       }
   }

再看一下主要的putVal方法，源代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
/** Implementation for put and putIfAbsent */
   final V putVal(K key, V value, boolean onlyIfAbsent) {
       if (key == null || value == null) throw new NullPointerException();
       int hash = spread(key.hashCode());//获取hash映射桶，对hashcode做了扰动保证散列的均匀度
       int binCount = 0;
       for (Node<K,V>[] tab = table;;) {
           Node<K,V> f; int n, i, fh;
           if (tab == null || (n = tab.length) == 0)
               tab = initTable();//如果当前未被初始化过，进行初始化。
           else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
               if (casTabAt(tab, i, null,
                            new Node<K,V>(hash, key, value, null)))
                   break;                   // no lock when adding to empty bin,采用无锁的方式，如果无锁置换成功就直接break出循环，代表成功插入。如果失败，表明有竞争发生，继续执行后续代码，会进行插入。
           }
           else if ((fh = f.hash) == MOVED)//表明当前表正在进行扩容。检测到当前映射节点正在进行扩容的时候，当前线程加入帮忙进行扩容工作。
               tab = helpTransfer(tab, f);
           else {
               V oldVal = null;
               synchronized (f) {//相当于锁住一条链表，这里有一个偏向锁到轻量级锁到重量级锁的升级过程
                   if (tabAt(tab, i) == f) {
                       if (fh >= 0) {
                           binCount = 1;
                           for (Node<K,V> e = f;; ++binCount) {
                               K ek;
                               if (e.hash == hash &&
                                   ((ek = e.key) == key ||
                                    (ek != null && key.equals(ek)))) {
                                   oldVal = e.val;
                                   if (!onlyIfAbsent)
                                       e.val = value;
                                   break;
                               }
                               Node<K,V> pred = e;
                               if ((e = e.next) == null) {
                                   pred.next = new Node<K,V>(hash, key,
                                                             value, null);
                                   break;
                               }
                           }
                       }
                       else if (f instanceof TreeBin) //如果已经被树化，以红黑树的方式增加一个节点。
                           Node<K,V> p;
                           binCount = 2;
                           if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
                                                          value)) != null) {
                               oldVal = p.val;
                               if (!onlyIfAbsent)
                                   p.val = value;
                           }
                       }
                   }
               }
               if (binCount != 0) {
                   if (binCount >= TREEIFY_THRESHOLD)//如果达到树化的阈值，将链表进行树化。
                       treeifyBin(tab, i);
                   if (oldVal != null)
                       return oldVal;
                   break;
               }
           }
       }
       addCount(1L, binCount);
       return null;
   }

总结

​ 从ConcurrentHashMap的多个版本演变中，最终java9采用了synchronized和cas来实现，之后会抽写一篇对几种版本迭代过程中性能的优异比较。