趣谈ConcurrentHashMap
whtqsq 2019-06-28
最近准备面试，一谈到java基础，大部分面试官上来就java数据结构素质三连：ArrayList与LinkedList区别，HashMap底层数据结构，ConcurrentHashMap为什么能保证线程安全。
刚毕业的应届生，或者基础不好程序员（比如：本尊，对没错就是我~），只了解皮毛，一稍微深入就gg思密达。面试官：嗯...回头等通知吧~ 基本一首《凉凉》送我到门外了。
不好意思，扯远了！ 前两个问题很简单，一个数组一个链表。
数组顺序存储，内存连续，查询快，插入删除效率稍微低（System.copyArray），不过现在略有改善。
链表插入删除快速高效，查询效率差了点意思，存储不连续。
总之，各有利弊吧，根据业务场景选择适合自己的存储结构，不过现在也出现很多类似的改进版本，暂时不谈了（其实我也没了解过，啊哈哈哈~有点尴尬）
HashMap JDK1.8以前基本都是数组＋链表实现，JDK1.8开始改为数组+列表，当列表长度大于某个值（具体忘了），链表转化为一个X爆了的数据结构————红黑树（我都吓尿了反正，看了几百遍没记住这玩意各种算法）
其实今天主要是想聊一下这个叫做ConcurrentHashMap的数据结构，看过网上几篇文章实在是看的蛋疼，一来写的一般，对于源码的复制粘贴，最为我看起来吃力；二来红黑树太难，看着难受的一比。是在无法理解这个数据结构的精髓所在，故而想自己写篇文章来记录自己学习的过程，就好比孙悟空去了一趟五指山下，做个标记！
废话少说直接先上jb：
如图所示，相比传统HashMap，jdk1.8之前 ConcurrentHashMap 在传统HashEntry之前增加了一个segment数组。Segment数组的意义就是将一个大的table分割成多个小的table来进行加锁，Segment数组中每一个元素就是一把锁，每一个Segment元素存储的是HashEntry数组+链表。而在jdk1.8开始，ConcurrentHashMap是由CAS和Synchronized的方式去实现高并发下的线程安全。
我们主要从的get，put等方法来学习ConcurrentHashMap，是如何插入和获取元素，以及如何保证线程安全。
先看下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;
}我看上面的代码好多中间变量，很影响我这种菜鸟分析逻辑，于是我按照自己的编码风格，重写了一下：
public V get(Object key) {
int h = (key.hashCode() ^ (key.hashCode() >>> 16)) & 0x7fffffff;// 2 ^31 -1
Node<K,V>[] tab = table;
// 一般对哈希表的散列很自然地会想到用hash值对length取模（即除法散列法）
// Hashtable中也是这样实现的，这种方法基本能保证元素在哈希表中散列的比较均匀，
// 但取模会用到除法运算，效率很低，HashMap中则通过h&(length-1)的方法来代替取模，
// 同样实现了均匀的散列，但效率要高很多，这也是HashMap对Hashtable的一个改进。
Node<K,V> e = tabAt(tab, (tab.length - 1) & h);
if (tab == null || tab.length <= 0 ||e == null) {
return null;
}
if (e.hash == h) {
if (e.getKey() == key || (e.getKey() != null && key.equals(e.getKey()))){
return e.getValue();
}
} else if (e.hash < 0) {
Node<K,V> p = e.find(h, key);
return p!= null ? p.getValue() : null;
}
e = e.next;
while (e != null) {
if (e.hash != h) {
return null;
}
if (e.getKey() == key || (e.getKey() != null && key.equals(e.getKey())))
return e.getValue();
}
return null;
}int h = (key.hashCode() ^ (key.hashCode() >>> 16)) & 0x7fffffff;// 2 ^31 -1
代码的意思————通过哈希值二进制异或该哈希值二进制右移动16位 是为了计算哈希值 再和 上面那玩意进行与运算并不知道是什么鬼。如下图：
计算出Hash值之后要通过hash值找到对应数组的下标进而找到数组元素：
Node<K,V> e = tabAt(tab, (tab.length - 1) & h);
(tab.length - 1) & h 根据计算出来的hash值从HashMap的“骨干”——bucket数组找到对应的bucket
java.util.HashMap （ConcurrentHashMap同样）保证bucket数组的长度是2的幂方，所以本来应该写成：
index = n % length的，变为可以写成：index = n & (length - 1) ，“&”效率会高一点。
说了这么多我们来看下tabAt方法:
public static int numberOfLeadingZeros(int i) {
// HD, Figure 5-6
if (i == 0)
return 32;
int n = 1;
if (i >>> 16 == 0) { n += 16; i <<= 16; }
if (i >>> 24 == 0) { n += 8; i <<= 8; }
if (i >>> 28 == 0) { n += 4; i <<= 4; }
if (i >>> 30 == 0) { n += 2; i <<= 2; }
n -= i >>> 31;
return n;
}
U = sun.misc.Unsafe.getUnsafe(); // 获取unsafe类的实例 单例模式
@CallerSensitive
public static Unsafe getUnsafe() {
Class arg = Reflection.getCallerClass();//获取调用者方法的类
if (!VM.isSystemDomainLoader(arg.getClassLoader())) {
throw new SecurityException("Unsafe");
} else {
return theUnsafe;
}
}
Class<?> ak = Node[].class;
ABASE = U.arrayBaseOffset(ak);
int scale = U.arrayIndexScale(ak);
ASHIFT = 31 - Integer.numberOfLeadingZeros(scale);
@SuppressWarnings("unchecked")
static final <K,V> Node<K,V> tabAt(Node<K,V>[] tab, int i) {
return (Node<K,V>)U.getObjectVolatile(tab, ((long)i << ASHIFT) + ABASE);
} 