由于HashMap在并发中会出现一些问题,所以JDK中提供了并发容器ConcurrentHashMap。有关HashMap并发中的问题和原理,强烈建议查看这篇文章进行复习。
ConcurrentHashMap使用分段锁技术,将整个数据结构分段(默认为16段)进行存储,然后给每一段数据配一把锁(继承ReentrantLock),当一个线程占用锁访问其中一个段的数据的时候,其他段的数据仍然能被其他线程访问,能够实现真正的并发访问。下图为JDK7的数据结构。
get操作和put操作类似,也是要两次hash。但是get操作的concurrenthashmap不需要加锁,原因是将存储元素都标记了volatile。要是不明白volatile,欢迎复习这篇博客
在写操作put,remove,扩容的时候,会对Segment加锁,只影响当前Segment,其他的Segment还是可以并发的
JDK8的ConcurrentHashMap的数据结构已经接近对应版本的HashMap,了解Hashmap的结构,就基本了解了Concurrenthashmap了,只是增加了同步的操作来控制并发。从JDK7版本的ReentrantLock+Segment+HashEntry,到JDK8版本中synchronized+CAS+HashEntry+红黑树。
Node类成员变量Node的元素val和指针next都标注volatile,目的是在多线程环境下线程A修改结点的val或者新增节点的时候是对线程B可见的。
ConcurrentHashMap有成员变量transient volatile Node<K,V>[] table,目的是为了使Node数组在扩容的时候对其他线程具有可见性而加的volatile。(例如:volatile int array[10]是指array的地址是volatile的而不是数组元素的值是volatile的.)
写到这的时候,笔者建议大家去了解下Redis的渐进式扩容,是另一种思想,都值得学习。一句话帮助理解Redis的渐进式扩容:由于Redis是单线程,而且数据量较大时,无法一次性快速扩容,所以Redis首先申请一个新的容量加倍的哈希表,然后在插入,删除,更新操作的时候,调用rehash函数(dictRehash函数),将原有操作单元的链表移植到新的哈希表中,当原有哈希表全部移植过去,扩容结束。
两个重要变量:
counterCell类使用了 @sun.misc.Contended 标记的类,内部一个 volatile变量。这个注解标识着这个类需要避免 "伪共享".
避免伪共享(false sharing)。缓存系统中是以缓存行(cache line)为单位存储的。缓存行是2的整数幂个连续字节, 一般为32-256个字节。最常见的缓存行大小是64个字节。当多线程修改互相独立的变量时,如果这些变量共享同一个缓存行,就会无意中影响彼此的性能,这就是伪共享。所以伪共享对性能危害很大。 没有这个注解之前,是通过使用拼接把缓存行加满来解决这个问题,让缓存之间的修改互不影响。
ConcurrentHashMap节点的数量 = baseCount+counterCells每个cell记录下来的节点数量
由于JDK8在统计这个数量的时候并没有进行加锁,所以这个结果并不是绝对准确的。原理都是相通的,可以顺道看看LongAdder的longValue方法。
总体的原则就是:先尝试更新baseCount,失败再利用CounterCell。
对当前的table进行无条件自循环直到put成功
ConcurrentHashMap迭代器是弱一致性,hashmap迭代器是强一直性。
ConcurrentHashMap可以支持在迭代过程中,向map添加新元素,而HashMap则抛出了ConcurrentModificationException,因为HashMap包含一个修改计数器,当你调用他的next()方法来获取下一个元素时,迭代器将会用到这个计数器。
ConcurrentHashMap使用不当,也会造成死循环的。以后会有博客来介绍~