对于早期的线程安全的容器设计，我们能想到的方法就是HashTable，它的实现机制十分的简单，直接在put，get方法上加上了Synchronized来保证线程安全。但是这样的设计效率并没有让人们所满意，为了解决带来效率问题，便有了ConcurrentHashMap。早起的ConcurrentHashMap早期的设计如下： ![ConcurrentHashMap](//static.xiedaimala.com/xdml/image/561e0daa-ad6a-46a8-bb13-dc1269236b3c/2020-3-12-23-52-50.png) ConcurrentHashMap 此版本的ConcurrentHashMap使用的是分段锁的设计，每个分段锁都可以认为它是一个HashTable，从图中很容易看出来，无论读写，只要我加锁对应的分段即可，没被操作的分段则不需要加锁。这样设计的好处比起HashTable而言，有多少个Segment，效率便提高了多少倍。但是人们并没有满足现有的设计，从Java8开始，ConCurrentHashMap放弃了分段锁的实现方式，毕竟Java7中使用分段锁还是会对吞吐量有影响的。Java8中引入了大量的CAS，volatile的设计来保证线程安全。相比Java7而言，Java8的ConcurrentHashMap做了如下改进： 1.Hash表+链表/红黑树结构 2.不使用分段锁使用CAS volatile Unsafe 3.锁的粒度更细 Java8中设计如下图所示： ![ConcurrentHashMap](//static.xiedaimala.com/xdml/image/561e0daa-ad6a-46a8-bb13-dc1269236b3c/2020-3-12-23-53-22.png) Get方法首先我们来看看get方法 public V get(Object key) { Node[] tab; Node e, p; int n, eh; K ek; int h = spread(key.hashCode()); if ((tab = table) != null && (n = tab.length) > 0 && (e = tabAt(tab, (n - 1) & h)) != null) { if ((eh = e.hash) == h) { if ((ek = e.key) == key || (ek != null && key.equals(ek))) return e.val; } else if (eh < 0) return (p = e.find(h, key)) != null ? p.val : null; while ((e = e.next) != null) { if (e.hash == h && ((ek = e.key) == key || (ek != null && key.equals(ek)))) return e.val; } } return null; } get方法的设计比较简单，代码量比较少，大致介绍下流程： 1.通过spread方法来计算hash值，如果hash值等于表中节点的hash值，则有一下判断刚好匹配值，直接返回 eh<0按对应的的方式查找，这里介绍下为什么eh的值会小于0。 /* * Encodings for Node hash fields. See above for explanation. */ static final int MOVED = -1; // hash for forwarding nodes static final int TREEBIN = -2; // hash for roots of trees static final int RESERVED = -3; // hash for transient reservations static final int HASH_BITS = 0x7fffffff; // usable bits of normal node hash static final int spread(int h) { return (h ^ (h >>> 16)) & HASH_BITS; } 我们能看到在计算Hash值的函数spread中，按位取了hash值，HASH_BITS 的值首位为7，可以保证和它与的值符号位保证为0即正数，而对于hash值为负数的一些情况，定义了三种特殊含义，即MOVED，TREEBIN ，RESERVED。另外有一个很重要的问题，既然get操作没有任何锁，它在读取的过程中有线程写入该怎么办？其实我们简单看一段Node节点的源码就很清楚了。 static class Node implements Map.Entry { final int hash; final K key; volatile V val; volatile Node next; Node(int hash, K key, V val, Node next) { this.hash = hash; this.key = key; this.val = val; this.next = next; } } 可以看到，val值和next是由volatile修饰的，可以保证当有线程修改值或者添加新值的时候，会实现弱一致性。所谓弱，即拿数据的线程还没拿到值table有修改则立刻知晓，拿到值还没返回table有修改的话，则继续返回旧值。 put方法 /** 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()); int binCount = 0; for (Node[] tab = table;;) { Node 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(hash, key, value, null))) break; // no lock when adding to empty bin } 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 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 pred = e; if ((e = e.next) == null) { pred.next = new Node(hash, key, value, null); break; } } } else if (f instanceof TreeBin) { Node p; binCount = 2; if ((p = ((TreeBin)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的put方法实现相对复杂一点，首先我们从源码中可以看到： ConcurrentHashMap不允许插入一个null键，而对于HashMap，允许插入一个null键。我们可以继续简述下put方法的逻辑 1.判断Node[]数组是否被初始化，没有则进行初始化。 2.通过hash定位数组的索引，如果没有的话则使用CAS机制进行添加头节点（可以自旋保证插入） 3.检查到内部在扩容，就帮助它一块扩容。 4.如果发现链表或者红黑树头元素不为空，使用synchronized锁住头元素。 5.判断链表值是否已经达到阈值8，大于则转为红黑树。这里有个天才的设计helpTransfer，因为在扩容的时候所有的线程必须停下来等，所以不如帮忙去扩容，我们简述下helpTransfer所做的事情，因为它代码比较复杂，细节方面太多。首先，使用CAS机制来保证创建一个扩容的新表nextTable，保证这个表创建的是唯一的。之后所有的线程会被指明这个nextTable，并且调用transfer方法，并发的去迁移数据。

详解ConcurrentHashMap