从HashMap到ConcurrentHashMap
HashMap
《HashMap》中已经分析了HashMap的实现，jdk1.7与jdk1.8的实现有很多区别，现在我们分析一下两个版本的差异：
- jdk1.7采用数组+链表实现，jdk1.8采用数组+链表+红黑树实现，当HashMap中元素不断增多时，发生碰撞的概率会增大，1.7版本会退出成链表，时间复制度为O(N)，而1.8版本当同一个hash上的数量超过阈值（8）时，将链表变成红黑树，时间复杂度为O(logN)，性能得到很大的提升；
- jdk1.7与jdk1.8的hash计算有一点不同，jdk1.8简化了hash值计算过程，用了两次位运算，jdk1.7用了9次，在hash计算上，jdk1.8的效率也得到了提升；
- 当jdk1.7与jdk1.8发生碰撞时，插入到链表的方式也不相同，jdk1.7是向链表的头部插入新元素，而jdk1.8是向尾部插入新元素；
- 当HashMap每次需要扩容时，jdk1.7与jdk1.8增长为原来的2倍，但jdk1.7是重新按照新长度重新计算下标，而jdk1.8是用原下标+原容量得到新下标，计算相对简化，性能也得到了提升；
- 当HashMap进行rehash操作时，jdk1.7针对新链表的操作，还是插入头部，但遍历原来的链表是从头部开始遍历，相当于对原来链表进行了倒序操作，而jdk1.8还是按照原来链表的顺序重新放到新的链表中的，依次向新的链表尾部插入元素；
- jdk1.7版本的HashMap在多线程环境下，rehash会引起死循环，而jdk1.8版本的HashMap，并发环境也不能保证线程安全。
在多线程环境下，JDK并发包里提供了ConcurrentHashMap来保证线程安全性，也就是HashMap的线程安全版本，下面结合源码分析一下原理：
ConcurrentHashMap
- ConcurrentHashMap 1.7
构造方法
ConcurrentHashMap相比于HashMap多了并发级别—DEFAULT_CONCURRENCY_LEVEL（默认16），根据并发级别创建Segment数组及Segment数组的第一个元素，我们看一下Segment的结构：
Segment继承自ReentrantLock，包含一个HashMap的节点结构HashEntry，每个Segment有自己的负载因子和扩容阈值，感觉Segment就像一个实现了锁功能的HashMap。
put方法
1、首先是计算hash和下标，ConcurrentHashMap是根据Segment的长度，计算hash值在Segment数组中的下标，并且返回一个Segment对象，如果得到下标位置在Segment数组的元素为空，将以初始化时创建的Segment[0]为原型创建一个新的Segment对象，放入Segment数组并返回；
2、然后是执行Segment的put操作：
final V put(K key, int hash, V value, boolean onlyIfAbsent) {
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;
if (c > threshold && tab.length < MAXIMUM_CAPACITY)
rehash(node);
else
setEntryAt(tab, index, node);
++modCount;
count = c;
oldValue = null;
break;
}
}
} finally {
unlock();
}
return oldValue;
}3、尝试获得锁，如果获取不到，采用自旋方式尝试获取锁，超过尝试次数则阻塞；
4、重新计算在Segment元素中的HashEntry<K,V>[] table中的下标，和HashMap1.7版本一样，向链表的头部插入；
5、最后，释放锁；
6、rehash操作也是在持有锁的状态下，才允许操作；
7、大量使用Unsafe的putOrderXXX和putXXXVolatile方法，此方法是Java操作内存的方法，支持在内存上增加内存屏障，也就是线程安全的原子操作；
get方法
public V get(Object key) {
Segment<K,V> s;
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;
}1、首先，使用UNSAFE.getObjectVolatile方法，读取主存中segments数组的元素，就是确定访问整个ConcurrentHashMap分段锁中的锁对象；
2、然后，拿到分段锁中的table[]，计算下标，拿出链表HashEntry；
3、根据key和hash值，返回对应的value值。
4、get方法并没有使用锁，但使用了UNSAFE.getObjectVolatile方法。
- ConcurrentHashMap 1.8
Jdk1.8版本的ConcurrentHashMap，相比于jdk1.7去掉了分段锁，也和jdk1.8版本的HashMap一样，采用了数组+链表+红黑树的结构，所以较jdk1.7版本，变化较大，下面结合源码分析一下：
关键属性——sizeCtl
// volatile修饰的状态变量，保存下次扩容的对象
private transient volatile int sizeCtl;
// sizeCtl的取值意义
static final int MOVED = -1;
static final int TREEBIN = -2;
static final int RESERVED = -3;
// 存储元素时数组，每个元素为一个链表或者红黑树
transient volatile Node<K,V>[] table;
// 扩容时转移元素时使用
private transient volatile Node<K,V>[] nextTable;
// 计算map长度
private transient volatile long baseCount;sizeCtl默认值为0；
sizeCtl大于0时，代表扩容的阈值；
sizeCtl为-1时，说明进行初始化或扩容操作；
sizeCtl为-2时，说明进行树化操作；
sizeCtl为-3时，说明当前key与函数做映射运算；
put方法与初始化
final V putVal(K key, V value, boolean onlyIfAbsent) {
if (key == null || value == null) throw new NullPointerException();
int hash = spread(key.hashCode());
int binCount = 0;
for (Node<K,V>[] tab = table;;) {
Node<K,V> f; int n, i, fh;
if (tab == null || (n = tab.length) == 0)
tab = initTable();
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
if (casTabAt(tab, i, null,
new Node<K,V>(hash, key, value, null)))
break; // no lock when adding to empty bin
}
else if ((fh = f.hash) == MOVED)
tab = helpTransfer(tab, f);
else {
V oldVal = null;
synchronized (f) {
if (tabAt(tab, i) == f) {
if (fh >= 0) {
binCount = 1;
for (Node<K,V> e = f;; ++binCount) {
K ek;
if (e.hash == hash &&
((ek = e.key) == key ||
(ek != null && key.equals(ek)))) {
oldVal = e.val;
if (!onlyIfAbsent)
e.val = value;
break;
}
Node<K,V> pred = e;
if ((e = e.next) == null) {
pred.next = new Node<K,V>(hash, key,
value, null);
break;
}
}
}
else if (f instanceof TreeBin) {
Node<K,V> p;
binCount = 2;
if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
value)) != null) {
oldVal = p.val;
if (!onlyIfAbsent)
p.val = value;
}
}
}
}
if (binCount != 0) {
if (binCount >= TREEIFY_THRESHOLD)
treeifyBin(tab, i);
if (oldVal != null)
return oldVal;
break;
}
}
}
addCount(1L, binCount);
return null;
}1、ConcurrentHashMap不支持key和value为null；
2、使用spread计算hash值，spread方法进行了两次位运算，又和HASH_BITS，做与操作，降低Hash冲突，是元素分配更均匀；
3、ConcurrentHashMap采用的也是延迟初始化，也就是在put时，如果table数组为空，才进行初始化时；
4、如果数组下标位置为null，则将新建一个Node节点，使用CAS方式写入到数组下标位置；
5、如果正在扩容，则调用helpTransfer方法，协助扩容；
6、如果找到数组下标位置元素为正常状态，则需要加锁进行线程安全的插入元素，可以看到ConcurrentHashMap使用的是synchronize，锁对象是数组下标位置的节点对象，这样的锁比，jdk1.7版本的锁更细化，具体插入操作与jdk1.8版本HashMap插入元素类似，如果是链表插入链表的尾部，如果是红黑树，则按照红黑树方式插入节点，如果超过树化阈值，进行树化处理；
7、最后使用cas方式，更新ConcurrentHashMap的长度属性baseCount；
get方法
public V get(Object key) {
Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
int h = spread(key.hashCode());
if ((tab = table) != null && (n = tab.length) > 0 &&
(e = tabAt(tab, (n - 1) & h)) != null) {
if ((eh = e.hash) == h) {
if ((ek = e.key) == key || (ek != null && key.equals(ek)))
return e.val;
}
else if (eh < 0)
return (p = e.find(h, key)) != null ? p.val : null;
while ((e = e.next) != null) {
if (e.hash == h &&
((ek = e.key) == key || (ek != null && key.equals(ek))))
return e.val;
}
}
return null;
}1、先使用spread方法计算hash值，spread方法进行了两次位运算，又和HASH_BITS，做与操作，降低Hash冲突，是元素分配更均匀；
2、根据hash值，计算数组下标，如果下标处无元素，则返回；
3、如果下标处有元素，且hash、key值相同，则表示数组下标位置的元素，就是要获取的元素，直接返回；
4、如果hash值为负数，则表示可能正在扩容，或者是树形节点，调用对应结构的find方法获取元素；
5、如果hash值不相等，也不为负数，说明是链表结构，则遍历链表以得到要获取的元素。
总结
- 1.8版本ConcurrentHashMap比jdk1.7版本结构更加简单，采用了和jdk1.8版本的HashMap一样的数组+链表+红黑树，1.7主要是Segment+HashEntry；
- 1.8主要依赖synchronize和CAS方式，保证线程安全，1.7采用分段锁，分段锁内部也是一个1.7版本的HashMap（数组+链表），使用synchronize相比于Segment，锁的粒度也降低了；
- 而内置锁synchronize替换ReentrantLock的子类Segment，也说明synchronize的性能再持续优化中。
- 《Java并发编程的艺术》
- https://www.ibm.com/developerworks/cn/java/java-lo-concurrenthashmap/index.html
- https://www.cnblogs.com/throwable/p/9139947.html
- https://www.cnblogs.com/study-everyday/p/6430462.html
腾讯云开发者
