基于JDK1.8的ConcurrentHashMap分析

之前看过ConcurrentHashMap的分析，感觉也了解的七七八八了。但昨晚接到了面试，让我把所知道的ConcurrentHashMap全部说出来。

然后我结结巴巴，然后应该毫无意外的话就G了，今天下定决心好好分析一下，这个万能的并发包，ConcurrentHashMap

分一下几个方面分析ConcurrentHashMap：

• put方法
• remove方法
• get方法

(一)put方法

1 public V put(K key, V value) {
2     return putVal(key, value, false);
3 }

调用了putVal方法，传入三个参数。第一个为key，第二个为val，第三个为onlyIfAbsent(意思为: 如果为true，当插入的key相同时，不替换val值，默认是为false，替换最新的val值)

putVal方法比较多，我们分两个部分讲：

 1 //第一部分
 2 final V putVal(K key, V value, boolean onlyIfAbsent) {
 3     //对传入的参数进行合法性判断
 4     if (key == null || value == null) throw new NullPointerException();
 5     //计算键所对应的 hash 值
 6     int hash = spread(key.hashCode());
 7     int binCount = 0;
 8     for (Node<K,V>[] tab = table;;) {
 9         Node<K,V> f; int n, i, fh;
10         //如果哈希表还未初始化，那么初始化它
11         if (tab == null || (n = tab.length) == 0)
12             tab = initTable();
13         //根据键的 hash 值找到哈希数组相应的索引位置
14         //如果为空，那么以CAS无锁式向该位置添加一个节点
15         else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
16             if (casTabAt(tab, i, null,
17                          new Node<K,V>(hash, key, value, null)))
18                 break;                   
19         }

我们看到第四行，如果key和val都为null，直接抛出异常，所以不能传入key和val都不能为null。

第二个注意点是 散列这个函数

1 static final int spread(int h) {
2     return (h ^ (h >>> 16)) & HASH_BITS;
3 }

我在HashMap里面有介绍，我就不详细说了，反正很重要。

第三个注意点就是初始化table这个函数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         //sizeCtl 小于零说明已经有线程正在进行初始化操作
 6         //当前线程应该放弃 CPU 的使用
 7         if ((sc = sizeCtl) < 0)
 8             Thread.yield(); // lost initialization race; just spin
 9         //否则说明还未有线程对表进行初始化，那么本线程就来做这个工作
10         else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
11             //保险起见，再次判断下表是否为空
12             try {
13                 if ((tab = table) == null || tab.length == 0) {
14                     //sc 大于零说明容量已经初始化了，否则使用默认容量
15                     int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
16                     @SuppressWarnings("unchecked")
17                     //根据容量构建数组
18                     Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
19                     table = tab = nt;
20                     //计算阈值，等效于 n*0.75
21                     sc = n - (n >>> 2);
22                 }
23             } finally {
24                 //设置阈值
25                 sizeCtl = sc;
26             }
27             break;
28         }
29     }
30     return tab;
31 }

我们看到第7，8行。如果有线程在初始化，那么那就等待，让出cpu。

初始化只允许一个线程对表进行初始化，如果不巧有其他线程进来了，那么会让其他线程交出 CPU 等待下次系统调度。这样，保证了表同时只会被一个线程初始化。

默认初始化为大小为16，阕值为0.75

我们重新回到putVal这个方法中去。

 1 //检测到桶结点是 ForwardingNode 类型，协助扩容
 2 else if ((fh = f.hash) == MOVED)
 3      tab = helpTransfer(tab, f);
 4 //桶结点是普通的结点，锁住该桶头结点并试图在该链表的尾部添加一个节点
 5 else {
 6        V oldVal = null;
 7        synchronized (f) {
 8            if (tabAt(tab, i) == f) {
 9               //向普通的链表中添加元素，无需赘述
10               if (fh >= 0) {
11                  binCount = 1;
12                  for (Node<K,V> e = f;; ++binCount) {
13                      K ek;
14                      if (e.hash == hash &&((ek = e.key) == key ||(ek != null && key.equals(ek)))) {
15                          oldVal = e.val;
16                          if (!onlyIfAbsent)
17                             e.val = value;
18                             break;
19                       }
20                       Node<K,V> pred = e;
21                       if ((e = e.next) == null) {
22                          pred.next = new Node<K,V>(hash, key,value, null);
23                          break;
24                       }
25                  }
26            }
27            //向红黑树中添加元素，TreeBin 结点的hash值为TREEBIN（-2）
28            else if (f instanceof TreeBin) {
29                Node<K,V> p;
30                binCount = 2;
31                  if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,                                      value)) != null) {
32                    oldVal = p.val;
33                    if (!onlyIfAbsent)
34                       p.val = value;
35                 }
36            }
37        }
38    }
39   //binCount != 0 说明向链表或者红黑树中添加或修改一个节点成功
40   //binCount  == 0 说明 put 操作将一个新节点添加成为某个桶的首节点
41   if (binCount != 0) {
42          //链表深度超过 8 转换为红黑树
43          if (binCount >= TREEIFY_THRESHOLD)
44              treeifyBin(tab, i);
45          //oldVal != null 说明此次操作是修改操作
46          //直接返回旧值即可，无需做下面的扩容边界检查
47          if (oldVal != null)
48              return oldVal;
49            break;
50         }
51     }
52 }
53 //CAS 式更新baseCount，并判断是否需要扩容
54 addCount(1L, binCount);
55 //程序走到这一步说明此次 put 操作是一个添加操作，否则早就 return 返回了
56 return null;

我们看到第三行，如果f的hash是MOVED，那么就帮助他扩容(说明至少有一个线程在扩容)

这个方法说实话我看的不太懂，我就在网上查了点资料：

首先，每个线程进来会先领取自己的任务区间，然后开始 --i 来遍历自己的任务区间，对每个桶进行处理。如果遇到桶的头结点是空的，那么使用 ForwardingNode 标识该桶已经被处理完成了。如果遇到已经处理完成的桶，直接跳过进行下一个桶的处理。如果是正常的桶，对桶首节点加锁，正常的迁移即可，迁移结束后依然会将原表的该位置标识位已经处理。

当 i < 0，说明本线程处理速度够快的，整张表的最后一部分已经被它处理完了，现在需要看看是否还有其他线程在自己的区间段还在迁移中。

putVal后面的代码就比较清楚了。如果是链表，就找到尾节点，插入即可。如果是红黑树，童谣插入即可。

至此，对于 put 方法的源码分析已经完全结束了，感觉真的很复杂。至此我感觉我都没有完全理解每一行代码是什么意思。

(二)remove方法

1 public V remove(Object key) {
2     return replaceNode(key, null, null);
3 }

三个参数，第一个为key，第二个为val，删除直接置为null，让gc来回收。第三个是Object cv，含义还不是很清楚。先继续看吧

我们还是分为两部分：

 1 //第一部分
 2 final V replaceNode(Object key, V value, Object cv) {
 3     //先找到key的位置 hash散列
 4     int hash = spread(key.hashCode());
 5     for (Node<K,V>[] tab = table;;) {
 6         Node<K,V> f; int n, i, fh;
 7         //如果表为空，直接返回null
 8         if (tab == null || (n = tab.length) == 0 ||
 9             (f = tabAt(tab, i = (n - 1) & hash)) == null)
10             break;
11         //如果有在扩容的线程，帮助他扩容
12         else if ((fh = f.hash) == MOVED)
13             tab = helpTransfer(tab, f);

首先遍历整张表的桶结点，如果表还未初始化或者无法根据参数的 hash 值定位到桶结点，那么将返回 null。

如果定位到的桶结点类型是 ForwardingNode 结点，调用 helpTransfer 协助扩容。

 1 else {
 2     V oldVal = null;
 3     boolean validated = false;
 4     synchronized (f) {
 5         if (tabAt(tab, i) == f) {
 6             if (fh >= 0) {
 7                 validated = true;
 8                 for (Node<K,V> e = f, pred = null;;) {
 9                     K ek;
10                     if (e.hash == hash &&
11                         ((ek = e.key) == key ||
12                          (ek != null && key.equals(ek)))) {
13                         V ev = e.val;
14                         if (cv == null || cv == ev ||
15                             (ev != null && cv.equals(ev))) {
16                             oldVal = ev;
17                             if (value != null)
18                                 e.val = value;
19                             else if (pred != null)
20                                 pred.next = e.next;
21                             else
22                                 setTabAt(tab, i, e.next);
23                         }
24                         break;
25                     }
26                     pred = e;
27                     if ((e = e.next) == null)
28                         break;
29                 }
30             }
31             else if (f instanceof TreeBin) {
32                 validated = true;
33                 TreeBin<K,V> t = (TreeBin<K,V>)f;
34                 TreeNode<K,V> r, p;
35                 if ((r = t.root) != null &&
36                     (p = r.findTreeNode(hash, key, null)) != null) {
37                     V pv = p.val;
38                     if (cv == null || cv == pv ||
39                         (pv != null && cv.equals(pv))) {
40                         oldVal = pv;
41                         if (value != null)
42                             p.val = value;
43                         else if (t.removeTreeNode(p))
44                             setTabAt(tab, i, untreeify(t.first));
45                     }
46                 }
47             }
48         }
49     }
50     if (validated) {
51         if (oldVal != null) {
52             if (value == null)
53                 addCount(-1L, -1);
54             return oldVal;
55         }
56         break;
57     }
58 }

代码很多，但我觉得思路不难。就是找到那个桶以后，直接加锁。判断是链表还是树，然后删除即可。

(三)get方法

 1 public V get(Object key) {
 2     Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
 3     int h = spread(key.hashCode());
 4     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         else if (eh < 0)
11             return (p = e.find(h, key)) != null ? p.val : null;
12         while ((e = e.next) != null) {
13             if (e.hash == h &&
14                 ((ek = e.key) == key || (ek != null && key.equals(ek))))
15                 return e.val;
16         }
17     }
18     return null;
19 }

和HashMap的get方法大同小异。没有涉及到并发操作。直接取到key的hash值，如果是第一个节点，直接返回。否则while循环查找