上一篇文章介绍了HashMap，HashMap虽然具有时间复杂度为O(1)的查询优势，但它不是线程安全的，为了适应高并发的应用场景，在此我们一起学习线程安全的ConcurrentHashMap(JDK1.7&JDK1.8)。
ConcurrentHashMap(JDK 1.7)
分段加锁机制
JDK 1.7版的ConcurrentHashMap的核心思路在于分段加锁机制引入“segment”的概念，HashMap由若干segment<K,V>[ ]组成，每个segment数组由桶数组+链表组成，segment是加锁的基本单位，这样避免了给整个HashMap加锁，提供效率，且节约时间，细化加锁粒度，在网上看见一个很好的示意图，如下所示：
segment.png
put方法
put()方法执行时，根据key进行两次hash：第一次通过hash()方法获取segment数组的索引，如果segment还未初始化，通过CAS操作对segment数组先进行初始化；第二次hash操作，目的是为了获取Entry<key,value>真正要插入的数组的索引，此时put()方法会利用继承得到的ReentrantLock的tryLock()方法去获取锁，如果获取成功，则遍历链表（主要目的是希望遍历的链表被CPU cache所缓存，为后续实际put过程中的链表遍历操作提升性能），如果遍历到数组中已存在的待插入的key值，则更新value即可，如果没查到，就将新的键值对插入链表即可（尾插法）。新建过程中如果节点总数（含新建的HashEntry）超过threshold，则调用rehash()方法对Segment进行扩容，最后将新建HashEntry写入到数组中。
get方法
JDK 1.7 版的ConcurrentHashMap的get()方法没有加锁操作，因为它的两个变量（value，next HashEntry）都是valotile修饰的，对其他线程具有可见性。get()时，根据key进行两次hash()，一次定位segment的索引，一次定位到hashEntry的位置，然后通过遍历链表找到目标键值对。
ConcurrentHashMap(JDK 1.8)
Synchronized+CAS操作
JDK 1.8版的ConcurrentHashMap的核心思路在于摒弃了之前版本的segment，直接将Synchronized和CAS操作用于数组+链表+红黑树组成的底层结构，保证它的高并发性。
put方法
首先通过spread(key.hashCode)方法定位key-value在桶数组中插入的位置，如果当前位置没有键值对，则先初始化数组后再插入；如果没有hash冲突就直接CAS插入；如果还在进行扩容操作就先进行扩容；如果存在hash冲突，就加锁来保证线程安全，这里有两种情况，一种是链表形式就直接遍历到尾端插入，一种是红黑树就按照红黑树结构插入；最后一个如果该链表的数量大于阈值8，就要先转换成黑红树的结构，break再一次进入循环；如果添加成功就调用addCount()方法统计size，并且检查是否需要扩容；若索引对应的当前位置已有键值对，否则分情况讨论：如果是红黑树，则按红黑树的方法插入；如果是链表，则把键值对插入链表尾部即可。其实ConcurrentHashMap的put方法HashMap的put方法的思路是一致的，只是ConcurrentHashMap不允许key和value为null，在处理多线程的时候需要注意加锁的情况。
get方法
第一步还是老样子，要先通过key定位数组里的索引，如果是当前位置的节点，就直接返回；如果遇到扩容的时候，会调用标志正在扩容节点Forwarding -Node的find方法，查找该节点，匹配就返回；以上都不符合的话，就往下遍历节点，匹配就返回，否则最后就返回null。
小结
JDK1.7版ConcurrentHashMap：ReentrantLock+Segment分段锁+HashEntry。
JDK1.8版ConcurrentHashMap：synchronized+CAS+HashEntry+红黑树。
数据结构：取消了Segment分段锁的数据结构，取而代之的是数组+链表+红黑树的结构。线程安全机制：JDK1.7采用segment的分段锁机制实现线程安全，其中segment继承自ReentrantLock。JDK1.8采用CAS+Synchronized保证线程安全。锁的粒度：原来是对需要进行数据操作的Segment加锁，现调整为对每个数组元素加锁（Node）。链表转化为红黑树：定位结点的hash算法简化会带来弊端，Hash冲突加剧，因此在链表节点数量大于8时，会将链表转化为红黑树进行存储。查询时间复杂度：遍历链表O(n)，遍历红黑树O(logN)。
网友评论