本篇文章主要介绍一下JDK1.7中的ConcurrentHashMap的一些代码结构。ConcurrentHashMap顾名思义就是线程安全的HashMap，相对于HashMap来说，可以保证线程安全的问题；对于HashTable来说可以提高存取的效率。
基本结构
从上述类图可以看出，ConcurrentHashMap除了Map通用的get()、put()等方法外，还有一个重要的属性Segment数组。每个Segment又是一个ReentrantLock，其内部又有一个HashEntry数组，HashEntry是最终key-value的存储单元。可以看出，HashEntry是一个链表结构。从而可以大致的得到如下结构图：
初始化
ConcurrentHashMap构造方法的3个入参分别是：initialCapacity、loadFactor、concurrencyLevel，用于初始化segment数组、segmentShift、segmentMask等数据。构造方法如下：
public ConcurrentHashMap(int initialCapacity, float loadFactor, int concurrencyLevel) {
// 1、参数校验
if (!(loadFactor > 0) || initialCapacity < 0 || concurrencyLevel <= 0)
throw new IllegalArgumentException();
if (concurrencyLevel > MAX_SEGMENTS)
concurrencyLevel = MAX_SEGMENTS;
// 2、ssize是segments数组的大小，这里取的是大于concurrencyLevel的2^n的一个值
int sshift = 0;
int ssize = 1;
while (ssize < concurrencyLevel) {
++sshift;
ssize <<= 1;
}
// 3、sshift就是上面描述中的n值，默认情况下concurrencyLevel等于16，sshift就等于4。因此默认情况下segmentShift的值就是28，这个值会参与hash运算。
// segmentMask是hash运算的掩码，默认情况下等于16-1=15，类似于网络中的子网掩码，segmentMask的二进制最后几位都是1，最大值是末尾16个1（65535）。
this.segmentShift = 32 - sshift;
this.segmentMask = ssize - 1;
// 4、下面的代码主要是用来初始化segment，其中cap是segment里面的HashEntry数组的长度。它取的是大于等于c（Map容量/ssize）的2^N的一个值。
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
int c = initialCapacity / ssize;
if (c * ssize < initialCapacity)
++c;
int cap = MIN_SEGMENT_TABLE_CAPACITY;
while (cap < c)
cap <<= 1;
// 5、创建segments和segments[0]（这里面只初始化了一个segments数组中的第0个元素）
Segment<K,V> s0 =
new Segment<K,V>(loadFactor, (int)(cap * loadFactor),
(HashEntry<K,V>[])new HashEntry[cap]);
Segment<K,V>[] ss = (Segment<K,V>[])new Segment[ssize];
UNSAFE.putOrderedObject(ss, SBASE, s0); // ordered write of segments[0]
this.segments = ss;
}
initialCapacity：ConcurrentHashMap的初始化容量，默认值是16（DEFAULT_INITIAL_CAPACITY）；
loadFactor：负载因子，默认值是0.75f，当ConcurrentHashMap中的HashEntry数量到达 loadFactor * 当前容量 时，就会进行rehash()进行扩容；
concurrencyLevel：并发的级别，也就是Segment数组的大小（ConcurrentHashMap是对每个Segment加锁，因此得名并发级别），默认值是16（DEFAULT_CONCURRENCY_LEVEL）。这里需要注意的是concurrencyLevel的大小都是2^n，concurrencyLevel会取大于传入值的邻近的一个值。如：传入15，则concurrencyLevel=16（2^4）。
下面介绍一下构造函数中的初始化流程：
（1）参数校验。
（2）设置ssize的值，ssize是segments数组的大小，这里取的是大于concurrencyLevel的2^n的一个值。
（3）设置segmentShift和segmentMask的值，sshift就是上面描述中的n值，默认情况下concurrencyLevel等于16，sshift就等于4。因此默认情况下segmentShift的值就是28，这个值会参与hash运算。segmentMask是hash运算的掩码，默认情况下等于16-1=15，类似于网络中的子网掩码，segmentMask的二进制最后几位都是1，最大值是末尾16个1（65535）。
（4）初始化segment，其中cap是segment里面的HashEntry数组的长度。它取的是大于等于c（Map容量/ssize）的2^N的一个值。
（5）创建segments和segments[0]（这里面只初始化了一个segments数组中的第0个元素）。
定位Segment
ConcurrentHashMap使用分段锁Segment来保护不同的数据，下面简单的描述一下定位的流程。
第一步是获取key的hash值，代码如下：
private int hash(Object k) {
int h = hashSeed;
if ((0 != h) && (k instanceof String)) {
return sun.misc.Hashing.stringHash32((String) k);
}
h ^= k.hashCode();
// 将key的hash值打开到segment分段中去
// 使用了Wang/Jenkins hash的变体算法
h += (h << 15) ^ 0xffffcd7d;
h ^= (h >>> 10);
h += (h << 3);
h ^= (h >>> 6);
h += (h << 2) + (h << 14);
return h ^ (h >>> 16);
}第二步，通过上面的散列算法得到的值，然后进行一下位移操作，取高位数值。
int index = (h >>> segmentShift) & segmentMask;默认情况下segmentShift为28，segmentMask为15（低位有1111），从而可以得到h的高四位的值。
常用方法
get()
get操作是先定位到segment，然后再到segment中去获取对应的value值。代码如下：
public V get(Object key) {
Segment<K,V> s; // manually integrate access methods to reduce overhead
HashEntry<K,V>[] tab;
int h = hash(key);
// 根据Segment的索引（(h >>> segmentShift) & segmentMask）算出在Segment[]上的偏移量
long u = (((h >>> segmentShift) & segmentMask) << SSHIFT) + SBASE;
if ((s = (Segment<K,V>)UNSAFE.getObjectVolatile(segments, u)) != null &&
(tab = s.table) != null) {
// 若Segment存在，则继续查找table[]的索引位置；
// 根据table的索引（(tab.length - 1) & h）算出在table[]上的偏移量，循环链表找出结果
for (HashEntry<K,V> e = (HashEntry<K,V>) UNSAFE.getObjectVolatile
(tab, ((long)(((tab.length - 1) & h)) << TSHIFT) + TBASE);
e != null; e = e.next) {
K k;
if ((k = e.key) == key || (e.hash == h && key.equals(k)))
return e.value;
}
}
return null;
}通过上面代码可以看出：
（1）首先，根据Segment的索引（(h >>> segmentShift) & segmentMask）算出在Segment[]上的偏移量。然后根据偏移量，调用UNSAFE.getObjectVolatile()判断其是否存在。
（2）若Segment存在，则继续查找table[]的索引位置；根据table的索引（(tab.length - 1) & h）算出在table[]上的偏移量，循环链表找出结果。
从上面步骤可以看出，整个过程中读取并未加锁。所以在读取的过程中，如果出现HashEntry的变更，则无法得到真正的结果。这一点是ConcurrentHashMap在弱一致性上的体现。如果要求强一致性，就必须要加锁控制。
put()
对于put()操作，前面的定位Segment的操作都是和put()相同的。找到Segment以后，然后对整个Segment加锁，然后再进行后续的操作。下面详细介绍一下：
public V put(K key, V value) {
Segment<K,V> s;
if (value == null)
throw new NullPointerException();
// 定位Segment，并判断其是否存在
int hash = hash(key);
int j = (hash >>> segmentShift) & segmentMask;
if ((s = (Segment<K,V>)UNSAFE.getObject // nonvolatile; recheck
(segments, (j << SSHIFT) + SBASE)) == null) // in ensureSegment
s = ensureSegment(j);// 如果不存在，则创建；这是因为在构造ConcurrentHashMap的时候，只创建了segment[0]这个元素
return s.put(key, hash, value, false);// 提交给Segment去处理
}可以看出，首先定位Segment，并判断其是否存在；如果不存在，则创建（这是因为在构造ConcurrentHashMap的时候，只创建了segment[0]这个元素）；然后再提交给Segment去处理。下面看一下创建Segment的过程：
private Segment<K,V> ensureSegment(int k) {
final Segment<K,V>[] ss = this.segments;
// 定位Segment里面table的位置
long u = (k << SSHIFT) + SBASE; // raw offset
Segment<K,V> seg;
if ((seg = (Segment<K,V>)UNSAFE.getObjectVolatile(ss, u)) == null) {
Segment<K,V> proto = ss[0]; // 使用segment[0]作为原型创建，这里面免去了一些计算
int cap = proto.table.length; // 2^n的一个值
float lf = proto.loadFactor; // 默认0.75f
int threshold = (int)(cap * lf);
HashEntry<K,V>[] tab = (HashEntry<K,V>[])new HashEntry[cap];
if ((seg = (Segment<K,V>)UNSAFE.getObjectVolatile(ss, u))
== null) { // 准备创建前，再去检查是否已经创建
// 使用CAS创建，直至成功
Segment<K,V> s = new Segment<K,V>(lf, threshold, tab);
while ((seg = (Segment<K,V>)UNSAFE.getObjectVolatile(ss, u))
== null) {
if (UNSAFE.compareAndSwapObject(ss, u, null, seg = s))
break;
}
}
}
return seg;
}上述首先定位出了table在segment中的位置；然后使用segment[0]作为原型创建元素（这里面免去了一些计算）；然后使用CAS创建，直至成功。
下面看一下具体的put方法，由Segment实现：
final V put(K key, int hash, V value, boolean onlyIfAbsent) {
// 尝试加锁，首先尝试tryLock()，多次失败以后使用lock()；同时会查找HashEntry，如果没有找到，创建并返回一个
HashEntry<K,V> node = tryLock() ? null : scanAndLockForPut(key, hash, value);
V oldValue;
try {
HashEntry<K,V>[] tab = table;
int index = (tab.length - 1) & hash;
HashEntry<K,V> first = entryAt(tab, index);
// 循环定位链表中的HashEntry位置，然后执行变更
for (HashEntry<K,V> e = first;;) {
if (e != null) {// 查找key，若找到直接修改value值
K k;
if ((k = e.key) == key ||
(e.hash == hash && key.equals(k))) {
oldValue = e.value;
if (!onlyIfAbsent) {
e.value = value;
++modCount;
}
break;
}
e = e.next;
}
else {// 到达链表尾部
if (node != null)// node如果不等于null，说明之前已经预热完成，可以直接插入
node.setNext(first);
else
node = new HashEntry<K,V>(hash, key, value, first);
int c = count + 1;
// 检查是否到达threshold，到达后则进行rehash()
if (c > threshold && tab.length < MAXIMUM_CAPACITY)
rehash(node);
else
setEntryAt(tab, index, node);
++modCount;
count = c;
oldValue = null;
break;
}
}
} finally {
unlock();
}
return oldValue;
}从上面Segment的put操作可以看出：
（1）首先，segment尝试tryLock()，多次失败以后使用lock()，同时会查找HashEntry，如果没有找到，创建并返回一个（预热操作）。
（2）然后，循环定位链表中的HashEntry位置。如果查找到key，若找到直接修改value值，并退出。如果找不到则在链表头部新增一个HashEntry节点。
（3）在新增节点的之后，会检查是否会达到threshold，如果到达则进行rehash()扩容。
关于rehash()操作，后面单独介绍。下面介绍一下scanAndLockForPut()的实现。
private HashEntry<K,V> scanAndLockForPut(K key, int hash, V value) {
HashEntry<K,V> first = entryForHash(this, hash);
HashEntry<K,V> e = first;
HashEntry<K,V> node = null;
int retries = -1; // 定位node时为负值
while (!tryLock()) {// 这里首先尝试使用tryLock()，达到最大重试次数MAX_SCAN_RETRIES后，转为lock()的阻塞操作
HashEntry<K,V> f; // to recheck first below
if (retries < 0) {// 定位node的位置，若找不到则创建一个HashEntry
if (e == null) {
if (node == null) // speculatively create node
node = new HashEntry<K,V>(hash, key, value, null);
retries = 0;
}
else if (key.equals(e.key))
retries = 0;
else
e = e.next;
}
else if (++retries > MAX_SCAN_RETRIES) {// 达到MAX_SCAN_RETRIES时，进行阻塞加锁
lock();
break;
}
else if ((retries & 1) == 0 &&
(f = entryForHash(this, hash)) != first) {
e = first = f; // 如果加锁过程中，node有新增，则重新遍历链表，（这里可以解释对于链表的插入位置总是head的问题了）
retries = -1;
}
}
return node;
}从上述代码可以看出，执行步骤大概如下：
（1）这里首先尝试使用tryLock()，达到最大重试次数MAX_SCAN_RETRIES后，转为lock()的阻塞操作；
（2）定位node位置的时候，如果找不到则创建一个HashEntry；
（3）如果加锁过程中，node有新增，则重新遍历链表，（这里可以解释对于链表的插入位置总是head的问题了）。
