ConcurrentHashMap

ConcurrentHashMap的实现原理与使用

ConcurrentHashMap是线程安全且高效的HashMap,并发编程中使用HashMap可能导致程序死循环，线程安全的HashTable效率低下，基于上述原因，有了ConcurrentHashMap.

HashTable容器效率低下的原因是所有访问HashTable的线程都必须竞争同一把锁,假如容器里有多把锁,每一把锁用于锁容器其中一部分数据,那么当多线程访问容器里不同数据段的数据时,线程间就不会存在锁竞争,从而可以有效提高并发访问效率,这就是ConcurrentHashMap所使用的锁分段技术。首先将数据分成一段一段地存储,然后给每一段数据配一把锁,当一个线程占用锁访问其中一个段数据的时候,其他段的数据也能被其他线程访问。

结构

ConcurrentHashMap是由Segment数组结构和HashEntry数组结构组成。Segment是一种可重入锁, 在ConcurrentHashMap里扮演锁的角色; HashEntry则用于存储键值对数据。一个ConcurrentHashMap里包含一个Segment数组。

segment 本身就相当于一个HashMap对象

像这样的Segment对象，有2的N次方个，共同保存在一个名为segments的数组中。

所以可以说，ConcurrentHashMap是一个二级哈希表，在一个总的哈希表下面，有若干个子哈希表。

Segment的结构和HashMap类似,是一种数组和链表结构。一个Segment里包含一个HashEntry数组,每个HashEntry是一个链表结构的元素,每个Segment守护着一个HashEntry数组里的元素,当对HashEntry数组的数据进行修改时,必须首先获得与它对应的Segment锁,如下图所示。

ConcurrentHashMap的优势就是采用了锁分段技术，每一个Segment就像一个自治区，读写操作高度自治，segement之间互不影响。

ConcurrentHashMap的初始化

初始化方法通过initialCapacity，loadFactor和concurrencyLevel等几个参数来初始化Segment数组，段偏移量segmentshift,段掩码segmentMask 和每个Segment里的HashEntry数组。

定位Segment

ConcurrentHashMap使用分段锁来保护不同段的数据，在插入和获取的时候，必须先通过散列算法定位到Segment，所以可以直到ConcurrentHashMap会首先使用Wang/Jenkins hash 的变种算法对元素的hashCode进行一次再散列。进行再散列的目的是为了减少散列冲突，使元素可以均匀的分布在不同的Segment中，从而提升容器存储效率。

ConcurrentHashMap的操作

get

get的高效之处在于整个get过程没有加锁，除非读到空值才会加锁重读，ConcurrentHashMap中的get方法里要使用的共享变量都被定义为volatile类型，volatile类型的变量可以在线程间保持可见性。能够同时被多线程读。并且不会读到过期的值，但是只能被单线程写。get操作里只需要读不需要写，所以可以不用加锁。

get过程为

• 为输入的key做哈希运算，得到Hash值。
• 通过hash值，定位到对应的Segment对象
• 再次通过hash值，定位到Segment当中数组的具体位置。

put

put要对共享变量进行写入操作，所以为了线程安全，在操作共享变量的时候必须加锁，put方法首先定位到Segment，然后在Segment里进行插入操作，插入操作需要经过两个步骤，第一步需要对Segment里的hashEntry数组进行扩容，第二部需要定位添加元素的位置，然后将其放在HashEntry数组里。

put 过程为

• 为输入的key做hash运算，得到hash值
• 通过hash值，定位到Segment对象
• 获取可重入锁
• 再次通过hash值，定位到Segment中数组的具体位置
• 插入或者覆盖HashEntry对象
• 释放锁

size

要统计整个ConcurrentHashMap里元素的大小，就必须统计所有Segment里元素的大小后求和，Segment里的全局变量count是一个volatile变量。不能把所有Segment里的count相加得到size,因为可能累加前使用的count发生了变化。

最安全的做法是统计size时，把所有Segment的put,remove,clean方法全锁住，但是这样十分低效

ConcurrentHashMap的做法是先尝试2次通过不锁住Segment的方式来统计各个Segment大小,如果统计的过程中,容器的count发生了变化,则再采用加锁的方式来统计所有Segment的大小。那么ConcurrentHashMap是如何判断在统计的时候容器是否发生了变化呢?使用modCount变量,在put、remove和clean方法里操作元素前都会将变量modCount进行加1,那么在统计size前后比较modCount是否发生变化,从而得知容器的大小是否发生变化。（乐观锁的思想）

size方法过程

• 遍历所有的Segment
• 把Segment的元素数量累加起来
• 把Segment的修改次数累加起来
• 判断所有Segment的总修改次数是否大于上一次的总修改次数，如果大于，说明统计过程中有修改，重新统计，尝试次数加1，如果不是，说明没有修改，统计结束。
• 如果尝试次数超过阀值，则对每一个Segment加锁，再重新统计。
• 再次判断所有Segment的总修改次数是否大于上一次的总修改次数，由于已经加锁，次数一定和上次相等。
• 释放锁，统计结束。