内容基于JDK1.7。ConcurrentHashMap在JDK1.8中有了完全不一样的实现，值得重新学习。
在JDK8中，使用了CAS技术。并且hash碰撞后节点链表优化也借鉴了JDK8中对HashMap，当增加到一定数量以后，改为红黑树。
并发编程实战中，ConcurrentHashMap 是经常被使用的数据结构。
相比于 HashTable 和 Collections.synchronizedMap()，ConcurrentHashMap在 线程安全的基础上，提供了更好的写并发能力，但降低了读一致性的要求 。
内部大量利用了 volatile, final, CAS 等lock-free技术，来减少锁竞争对性能的影响。
实现原理
在多线程环境中HashTable 和 Collections.synchronizedMap() 由于是在单个对象上加锁，所以会带来严重的锁竞争。而ConcurrentHashMap的关键之处在于，它采用了分段锁的锁分离机制，使用多个锁来控制对hash表的不同部分的修改。
在这种机制中，任意数量的读取线程可以并发地访问Map，执行读取操作的线程和执行写入操作的线程可以并发地访问Map，并且一个数量的写入线程可以并发地修改Map。
由一个内部类Segment来保存每个分段的数据，每个分段的内部结构都类似于一个HashMap，都是数组+链表的实现。(只不过Entry不一样)，同时Segment继承了ReetrantLock(可重入锁)。
对于一个Key，需要经过三次hash才能最终确定最终存储的位置：
1，第一次hash是key的hashCode()方法，我们称为h1。
2，第二次hash是将h1的高位进行第二次hash，得到hash值h2，h2用来确定该元素在哪个分段。
3，第三次hash就是根据第二次hash得到的h2，和分段内的table长度取模运算，最终确定存储数组中的Index。
以下是部分源码：
// ConcurrentHashMap 的 put方法
public V put(K key, V value) {
Segment<K,V> s;
if (value == null)
throw new NullPointerException();
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);
return s.put(key, hash, value, false);
}
//Segment的put方法
final V put(K key, int hash, V value, boolean onlyIfAbsent) {
//这一行 ReentrantLock.tryLock() 获取锁
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);
for (HashEntry<K,V> e = first;;) {
//此处源码不放了
...
}
} finally {
unlock(); //最后释放锁 调用的是ReentrantLock.unlock()
}
return oldValue;
}
// 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();
// Spread bits to regularize both segment and index locations,
// using variant of single-word 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);
}
ConcurrentHashMap的主要实体有三个：
- ConcurrentHashMap（整个Hash表）
- Segment（桶）
- HashEntry（节点）
以下源码可以看出三个实体的对应关系。
源码如下(JDK1.7)：
final Segment<K,V>[] segments;
static final class Segment<K,V> extends ReentrantLock implements Serializable {
transient volatile HashEntry<K,V>[] table;
...
todo thing
}
static final class HashEntry<K,V> {
final int hash;
final K key;
volatile V value;
volatile HashEntry<K,V> next;
...
todo thing
}
ConcurrentHashMap的读操作不需要加锁，HashEntry的 value 和 next节点使用volatile修饰，在多线程下保证了可见性。但同时牺牲了一致性。（具体可参考volatile关键字解析）
而HashMap的Entry中，只有Key是final的
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
Entry<K,V> next;
int hash;
}
初始化
ConcurrentHashMap有三个初始化参数
public ConcurrentHashMap(int initialCapacity,
float loadFactor, int concurrencyLevel) {
...... //something
}
跟HashMap一样，initialCapacity 和 loadFactor 是初始容量和加载因此，默认为16 和 0.75。
不同的是第三个参数 concurrencyLevel ，表示并发度，用来指定分片的个数。分片个数，是一个大于等于concurrencyLevel的最小2次幂数。（例如并发度=5，那么分片个数是8。并发度=9，分片个数是16）
并发度的设置直接影响ConcurrentHashMap的性能，如果并发度设置过小，那么将会带来严重的锁竞争。如果并发度设置过大，那么本来再一个分片内的元素，将分散到多个分片，CPUcache命中率下降，引起性能下降。
分段锁
在JDK1.7中，除了第一个Segment之外，其余的Segment使用了延迟初始化的机制：每次put之前，都要检查对应key的分段是否被创建，如果为null，则调用 s = ensureSegment(j); 确保分段锁被创建
ensureSegment() 可能在并发情况下被调用，但是它没有使用锁来控制竞争，而是使用了Unsafe对象的getObjectVolatile提供原子读语义，结合CAS来确保Segment创建的原子性。
需要注意的事情
ConcurrentHashMap 的key 和 value 都不能为null
（如果有什么错误或者建议，欢迎留言指出）
（本文内容是对各个知识点的转载整理，用于个人技术沉淀，以及大家学习交流用）
参考资料：
ConcurrentHashMap总结
ConcurrentHashMap原理分析
ConcurrentHashMap在JDK1.7和1.8的不同实现
J.U.C之并发容器ConcurrentHashMap-基于JDK1.8
网友评论