前言
之前，我们已经在HashMap上面暴打了面试官，没看过的读者可以看看哦HashMap 怎么聊出花来?。今天！，辉先森带读者一起解读ConcurrentHashMap!
一、为什么有CurrentHashMap？
通过前章的学习哦，我们有了解到，HashMap做的优化以及其遗留的线程安全的问题。
那为什么要多线程呢？
1. 更好的利用处理器
在多核场景下，使用多线程技术，将计算逻辑分配搭配多个处理器核心，就会显著减少程序的处理时间，并且随核数的加入而变得更加的有效率。
2. 更快的相应时间
在多线程下，可将数据一致性不强的操作派给其他线程处理。好处：相应用户请求线程能更快的处理完成，缩短响应时间，提高用户体验。
二、解决HashMap线程不安全
1.HashTable
hashtable对 get/put所有相关的操作都加上synchronized标志。虽然实现了线程安全，但是代价太大了。相当于对整个哈希表加了一把大锁，这样在竞争激烈的并发场景性能太差了。（不推荐考虑）
2.ConcurrentHashMap
- 使用Segment分段锁技术，将数据分成一段一段的存储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一段数据时，不阻塞访问其他段的数据，可以看成是有多个hashtable。好处：使用Segment分段锁技术减少了锁的粒度提高了并发的能力。
- JDK1.8升级：在JDK1.8的HashMap的基础上套一个安全措施。采用CAS+Synchronize来保障线程的安全，使得性能进一步的提高。
我们来看看put（）与get（）的流程吧。
put()的流程
1. 如果没有初始化就先去调用initTable()方法进行初始化的过程。
2. 如果有其他线程在扩容，就将当前线程加入到扩容任务中，帮助正在扩容的线程移动数据，提高效率。
3. 无hash冲突就进行CAS插入。
4. 有hash冲突，就调用Synchronize标记锁住当前的位桶，然后在进行插入-->(Entry过8就变红黑树)。
5. 在检查是否需要扩容。
public V put(K key, V value) {
return putVal(key, value, false);
}
final V putVal(K key, V value, boolean onlyIfAbsent) {
//数据不合法，抛出异常
if (key == null || value == null) throw new NullPointerException();
//计算索引的第一步，传入键值的hash值
int hash = spread(key.hashCode());
int binCount = 0; //保存当前节点的长度
for (Node<K,V>[] tab = table;;) {
Node<K,V> f; int n, i, fh; K fk; V fv;
if (tab == null || (n = tab.length) == 0)
tab = initTable(); //初始化Hash表
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
//利用CAS操作将元素插入到Hash表中
if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value)))
break; // no lock when adding to empty bin(插入null的节点，无需加锁)
}
else if ((fh = f.hash) == MOVED) //f.hash == -1
//正在扩容，当前线程加入扩容
tab = helpTransfer(tab, f);
else if (onlyIfAbsent && fh == hash && // check first node
((fk = f.key) == key || fk != null && key.equals(fk)) &&
(fv = f.val) != null)
return fv;
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;
//插入的元素键值的hash值有节点中元素的hash值相同，替换当前元素的值
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);
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;
}
}
else if (f instanceof ReservationNode)
throw new IllegalStateException("Recursive update");
}
}
if (binCount != 0) {
//如果节点长度大于8,转化为树
if (binCount >= TREEIFY_THRESHOLD)
treeifyBin(tab, i);
if (oldVal != null)
return oldVal;
break;
}
}
}
addCount(1L, binCount);
return null;
}get（）的流程
1. 通过键值的hash计算索引位置，如果满足条件，直接返回对应的值；
2. 如果相应节点的hash值小于0 ，即该节点在进行扩容，直接在调用ForwardingNodes节点的find方法进行查找。
3. 否则不在扩容的话，遍历当前节点直到找到对应的元素。
ConcurrentHashMap的get方法就是从Hash表中读取数据，而且与扩容不冲突。该方法没有同步锁。
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;
}
//e.hash<0，正在扩容
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;
}三、当被问到怎么设计一个哈希表，我们应该考虑哪些。
- 先把HashMap的原理一股脑砸给他。因为java1.8的HashMap设计是真的精妙，种种的优化都可以砸。
- 接着引申到线程安全的问题，把ConcurrentHashMap的原理丢给他。
- 杀手锏，解决高并发的问题。通过上面分析ConcurrentHashMap的原理，我们可以发现,put（）操作是带锁的而get（）操作是不需要带锁的，我们可以在这里搞搞事情。我们可以在ConcurrentHashMap的基础上在加一个位桶数组去解决高并发的问题，我们看看怎么操作吧。
1. 假如当前的一号位桶数组需要扩容了，一般我们是重新创建一个2倍长度的数组地址去扩容，当此时是不能进行put（）操作的。现在我们改变策略，将二号位桶数组进行长度的增加。
2. 接下来如果遇到put（）操作，就先去一号位桶数组查找是否存在相同的Entry和二号位桶数组查找是否存在相同的Entry。如果都没有就将这个要插入进来的节点放在二号位桶数组里面，在一号位桶数组查到，就移动节点到二号数组里面。
3. 如果是遇到get（）操作，先去一号数组里面查找时候是否存在该节点。如果有该节点，就将这节点从一号位桶数组移到二号位桶数组，然后返回该节点；如果在一号位桶数组找不到，就去二号位桶数组找找看有没有，没有就没有了，有就有。
4. 我们可以运用Mysql数据库在设计redo log的思想，当空闲的时候将一号位桶数组的数据搬去二号位桶数据里面。
5. 当一号位桶数组为空时，我们在进行长度*2的扩张。
总结
我们分析了ConcurrentHashMap原理和如何设计一个哈希表。我们来看看如何回答可以暴打面试官。
1. 先来个预热hashtable。（面试官：只知道hashtable，这么菜，这人没了）
2. 整一个分段锁的JDK1.7 的ConcurrentHashMap。（面试官：哟，知道这个数据结构，还行，就是优化没有说。）
3. 暴击JDK1.8的ConcurrentHashMap。（面试官：这个靓仔可以啊。）
4. 说出在高并发怎么优化的ConcurrentHashMap猜想。（面试官：输了输了，我输了。）
