ConcurrentHashMap的实现原理与使用(二)
上篇已经分析了HashMap在多线程环境下死循环的原因，HashTable使用synchronized来保证线程安全，但是相对来说效率低下，而ConcurrentHashMap是线程安全且高效的HashMap，这第一篇我们来看看ConcurrentHashMap
这篇同样使用上一篇的java环境：
java环境为jdk1.7.0_67
ConcurrentHashMap的结构
ConcurrentHashMap中包含Segment数组，Segment中包含HashEntry数组。
Segment结构
源码如下：
final Segment<K,V>[] segments;
...
static final class Segment<K,V> extends ReentrantLock implements Serializable {
...
transient volatile HashEntry<K,V>[] table;
...
}
Segment继承了ReentrantLock，ReentrantLock是一个可重入的互斥锁，ReentrantLock的详情以后有时间再聊，在这里简单说一下，ReentrantLock实现了Lock接口，从Java官方API中粘过来说明：A reentrant mutual exclusion Lock
with the same basic behavior and semantics as the implicit monitor lock accessed using synchronized methods and statements, but with extended capabilities.在这里翻一下（英文不好，强行使用百度翻译加上自己组织）：一个可重入的互斥锁，和关键词synchronized修饰的方法与语句访问隐式监视锁（可能翻译错了，就理解为和synchronized具有相同作用吧）具有相同的功能和语义，但具有扩展功能，翻译完毕。那么我们可以分析出Segment在ConcurrentHashMap作为锁，保证了ConcurrentHashMap的线程安全。
HashEntry结构
HashEntry是一个单链表结构，使用HashEntry<K,V>键值对存数据，next节点指向下一个节点，与HashMap不同的是，存值的value变量、存下一个节点的变量next使用了关键字volatile（volatile 自行百度吧）修饰，源码如下：
static final class HashEntry<K,V> {
final int hash;
final K key;
volatile V value;
volatile HashEntry<K,V> next;
HashEntry(int hash, K key, V value, HashEntry<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
...
}
分段锁技术保证了线程安全并提高了ConcurrentHashMap的并发访问率
通过分析了Segment、HashEntry结构与源码，可以得出，因为Segment继承了ReentrantLock，所以ConcurrentHashMap使用了分段锁的技术。把数据分为一段一段，也就是Segment数组，每个Segment中都有一个HashEntry数组，当对HashEntry进行数据存与读的时候，先要获取与之相对应的Segment锁，这样当多线程环境下，一个线程获得锁，访问这一段的数据的时候，其他线程也可以访问其他段的数据，所以保证了线程安全的同时提高了ConcurrentHashMap的并发访问率。
灵魂画师这次使用了做图工具
ConcurrentHashMap的put、get方法
分析一下ConcurrentHashMap的put、get方法源码
put方法
先算出数据要存到哪段中，通过算法去定位Segment，然后调用Segment对象的put方法去存储数据
public V put(K key, V value) {
Segment<K,V> s;
if (value == null)
throw new NullPointerException();
//hash算法算出key的哈希值
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
//定位Segment数组中的Segment
s = ensureSegment(j);
return s.put(key, hash, value, false);
}
再来看Segment的put方法
final V put(K key, int hash, V value, boolean onlyIfAbsent) {
//先对当前的Segment的进行加锁，保证线程安全
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;;) {
if (e != null) {
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.setNext(first);
else
node = new HashEntry<K,V>(hash, key, value, first);
int c = count + 1;
//判断是否需要HashEntry是否需要扩容
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方法，进行了加锁保证了线程安全，再添加的过程中，判断是否需要扩容，扩容过程中也会进行数据转存，但是已经进行了加锁，所以不会再发生HashMap中死循环的现象，而且，扩容不是针对于整个ConcurrentHashMap容器的扩容，而是针对于某个Segment中的HashEntry数组进行了扩容，这样提高了ConcurrentHashMap的效率。
get方法
先通过算法去定位Segment，然后在通再算法定位元素
public V get(Object key) {
Segment<K,V> s; // manually integrate access methods to reduce overhead
HashEntry<K,V>[] tab;
int h = hash(key);
long u = (((h >>> segmentShift) & segmentMask) << SSHIFT) + SBASE;
if ((s = (Segment<K,V>)UNSAFE.getObjectVolatile(segments, u)) != null &&
(tab = s.table) != null) {
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;
}
get过程没有加锁，保证了高效，但是怎么保证线程安全的呢？记得上面分析Segment结构与HashEntry结构的时候，Segment中HashEntry数组变量table使用了volatile修饰，HashEntry中用来存值的value变量也使用了volatile修饰，保证了table变量与value变量在线程间的相互可见性，就算是多个线程修改了HashEntry中的value，get方法也能读取到value在内存中的最新值，所以既保证了线程安全又保证了高效。
ConcurrentHashMap的实现原理与使用是说完了。
欢迎大家来交流，指出文中一些说错的地方，希望大家多多提出，让我加深认识。
谢谢大家！
