共计 6346 个字符，预计需要花费 16 分钟才能阅读完成。
ConcurrentHashMap 原理 是面试的一个高频知识点，这属于第一阶段的过招。
如果你答上来了，之后面试官可能会趁势诘问一下，如何进步 ConcurrentHashMap 的插入效率？于是一个接着一个，连环问就开始了，直到探到你的老底才罢休。
明天咱们用一篇文章把 ConcurrentHashMap 讲清楚，帮你在面试时镇定自若，从容应对。
1、ConcurrentHashMap 原理概述
ConcurrentHashMap 是一个存储 key/value 对的容器，并且是线程平安的。咱们先看 ConcurrentHashMap 的存储构造，如下图：
这是经典的数组加链表的模式。并且在链表长度过长时转化为红黑树存储（Java 8 的优化），放慢查找速度。
存储构造定义了容器的“形态”，那容器内的货色依照什么规定来放呢？换句话讲，某个 key 是依照什么逻辑放入容器的对应地位呢？
咱们假如要存入的 key 为对象 x，这个过程如下：
- 通过对象 x 的 hashCode () 办法获取其 hashCode；
- 将 hashCode 映射到数组的某个地位上；
- 把该元素存储到该地位的链表中。
从容器取数的逻辑如下：
- 通过对象 x 的 hashCode () 办法获取其 hashCode；
- 将 hashCode 映射到数组的某个地位上；
- 遍历该地位的链表或者从红黑树中找到匹配的对象返回。
这个数组 + 链表的存储构造其实是一个哈希表。
把对象 x 映射到数组的某个地位的函数，叫做 hash 函数。
这个函数的好坏决定元素在哈希表中散布是否平均，如果元素都沉积在一个地位上，那么在取值时须要遍历很长的链表。
但元素如果是平均的散布在数组中，那么链表就会较短，通过哈希函数定位地位后，可能疾速找到对应的元素。
具体 ConcurrentHashMap 中的哈希函数如何实现咱们前面会具体讲到。
扩容
咱们大抵理解了 ConcurrentHashMap 的存储构造。
那么咱们思考一个问题，当数组中保留的链表越来越多，那么再存储进来的元素大概率会插入到现有的链表中，而不是应用数组中剩下的空位。
这样会造成数组中保留的链表越来越长，由此导致哈希表查找速度降落，从 O (1) 缓缓趋近于链表的工夫复杂度 O (n/2)，这显然违反了哈希表的初衷。
所以 ConcurrentHashMap 会做一个操作，称为扩容。
也就是把数组长度变大，减少更多的空位进去，最终目标就是预防链表过长，这样查找的工夫复杂度才会趋向于 O (1)。
扩容的操作并不会在数组没有空位时才进行，因为在桶位快满时，新保留元素更大的概率会命中曾经应用的地位，那么可能最初几个桶位很难被应用，而链表却越来越长了。ConcurrentHashMap 会在更适合的机会进行扩容，通常是在数组中 75% 的地位被应用时。
另外 ConcurrentHashMap 还会有链表转红黑树的操作，以进步查找的速度，红黑树工夫复杂度为 O (logn)，而链表是 O (n/2)，因而只在 O (logn)<O (n/2) 时才会进行转换，也就是以 8 作为分界点。
其实以上内容和 HashMap 相似，ConcurrentHashMap 此外提供了线程平安的保障，它次要是通过 CAS 和 Synchronized 关键字来实现，咱们在源码剖析中再具体来看。
咱们做一下总结：
- ConcurrentHashMap 采纳数组 + 链表 + 红黑树的存储构造；
- 存入的 Key 值通过本人的 hashCode 映射到数组的相应地位；
- ConcurrentHashMap 为保障查问效率，在特定的时候会对数据减少长度，这个操作叫做扩容；
- 当链表长度减少到 8 时，可能会触发链表转为红黑树（数组长度如果小于 64，优先扩容，具体看前面源码剖析）。
接下来，咱们的源码剖析就从 ConcurrentHashMap 的形成、保留元素、哈希算法、扩容、查找数据这几个方面来进行。
2、ConcurrentHashMap 的形成
2.1 重要属性
咱们来看看 ConcurrentHashMap 的几个重要属性
1、transient volatile Node<K,V>[] table
这个 Node 数组就是 ConcurrentHashMap 用来存储数据的哈希表。
2、private static final int DEFAULT_CAPACITY = 16;
这是默认的初始化哈希表数组大小
3、static final int TREEIFY_THRESHOLD = 8
转化为红黑树的链表长度阈值
4、static final int MOVED = -1
这个标识位用于辨认扩容时正在转移数据
5、static final int HASH_BITS = 0x7fffffff;
计算哈希值时用到的参数，用来去除符号位
6、private transient volatile Node<K,V>[] nextTable;
数据转移时，新的哈希表数组
可能有些属性看完解释你还摸不到头脑。没关系，咱们在前面源码剖析时，具体应用的中央还会做相应解说。
2.2 重要组成元素
Node
链表中的元素为 Node 对象。他是链表上的一个节点，外部存储了 key、value 值，以及他的下一个节点的援用。这样一系列的 Node 就串成一串，组成一个链表。
ForwardingNode
当进行扩容时，要把链表迁徙到新的哈希表，在做这个操作时，会在把数组中的头节点替换为 ForwardingNode 对象。ForwardingNode 中不保留 key 和 value，只保留了扩容后哈希表（nextTable）的援用。此时查找相应 node 时，须要去 nextTable 中查找。
TreeBin
当链表转为红黑树后，数组中保留的援用为 TreeBin，TreeBin 外部不保留 key/value，他保留了 TreeNode 的 list 以及红黑树 root。
TreeNode
红黑树的节点。
3、put 办法源码剖析
put 办法用来把一个键值对存储到 map 中。代码如下：
public V put(K key, V value) {return putVal(key, value, false);
}理论调用的是 putVal 办法，第三个参数传入 false，管制 key 存在时笼罩原来的值。
咱们接下来看 putVal 的代码，代码比拟多，我把解释间接放到代码中：
final V putVal(K key, V value, boolean onlyIfAbsent) {
//key 和 value 不能为空
if (key == null || value == null) throw new NullPointerException();
// 计算 key 的 hash 值，前面咱们会看 spread 办法的实现
int hash = spread(key.hashCode());
int binCount = 0;
// 开始自旋，table 属性采取懒加载，第一次 put 的时候进行初始化
for (Node<K,V>[] tab = table;;) {
Node<K,V> f; int n, i, fh;
// 如果 table 未被初始化，则初始化 table
if (tab == null || (n = tab.length) == 0)
tab = initTable();
// 通过 key 的 hash 值映射 table 地位，如果该地位的值为空，那么生成新的 node 来存储该 key、value，放入此地位
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
}
// 如果该地位节点元素的 hash 值为 MOVED，也就是 -1，代表正在做扩容的复制。那么该线程参加复制工作。else if ((fh = f.hash) == MOVED)
tab = helpTransfer(tab, f);
// 上面分支解决 table 映射的地位曾经存在 node 的状况
else {
V oldVal = null;
synchronized (f) {
// 再次确认该地位的值是否曾经产生了变动
if (tabAt(tab, i) == f) {
//fh 大于 0，示意该地位存储的还是链表
if (fh >= 0) {
binCount = 1;
// 遍历链表
for (Node<K,V> e = f;; ++binCount) {
K ek;
// 如果存在一样 hash 值的 node，那么依据 onlyIfAbsent 的值抉择笼罩 value 或者不笼罩
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;
// 如果找到最初一个元素，也没有找到雷同 hash 的 node，那么生成新的 node 存储 key/value，作为尾节点放入链表。if ((e = e.next) == null) {
pred.next = new Node<K,V>(hash, key,
value, null);
break;
}
}
}
// 上面的逻辑解决链表曾经转为红黑树时的 key/value 保留
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;
}
}
}
}
//node 保留实现后，判断链表长度是否曾经超出阈值，则进行哈希表扩容或者将链表转化为红黑树
if (binCount != 0) {if (binCount >= TREEIFY_THRESHOLD)
treeifyBin(tab, i);
if (oldVal != null)
return oldVal;
break;
}
}
}
// 计数，并且判断哈希表中应用的桶位是否超出阈值，超出的话进行扩容
addCount(1L, binCount);
return null;
}主线流程梳理如下图：
其实 put 的核心思想都在这里了。接下来咱们别离看一下要害节点的办法源码。
4、spread 办法源码剖析
哈希算法的逻辑，决定 ConcurrentHashMap 保留和读取速度。hash 算法是 hashmap 的外围算法，JDK 的实现非常奇妙，值得咱们学习。
spreed 办法源代码如下：
static final int spread(int h) {return (h ^ (h >>> 16)) & HASH_BITS;
}传入的参数 h 为 key 对象的 hashCode，spreed 办法对 hashCode 进行了加工。从新计算出 hash。咱们先暂不剖析这一行代码的逻辑，先持续往下看如何应用此 hash 值。
hash 值是用来映射该 key 值在哈希表中的地位。取出哈希表中该 hash 值对应地位的代码如下。
tabAt(tab, i = (n – 1) & hash)
咱们先看这一行代码的逻辑，第一个参数为哈希表，第二个参数是哈希表中的数组下标。
通过 (n – 1) & hash 计算下标。
n 为数组长度，咱们以默认大小 16 为例，那么 n-1 = 15，咱们能够假如 hash 值为 100，那么 15 & 100 为多少呢？
& 把它左右数值转化为二进制，按位进行与操作，只有两个值都为 1 才为 1，有一个为 0 则为 0。
那么咱们把 15 和 100 转化为二进制来计算，java 中 int 类型为 8 个字节，一共 32 个 bit 位。
n 的值 15 转为二进制：
0000 0000 0000 0000 0000 0000 0000 1111
hash 的值 100 转为二进制：
0000 0000 0000 0000 0000 0000 0110 0100。
计算结果：
0000 0000 0000 0000 0000 0000 0000 0100
对应的十进制值为 4
是不是曾经看出点什么了？
15 的二进制高位都为 0，低位都是 1。
那么通过 & 计算后，hash 值 100 的高位全副被清零，低位则放弃不变，并且肯定是小于（n-1）的。
也就是说通过如此计算，通过 hash 值得到的数组下标相对不会越界。
这里我提出两个问题：
1、数组大小能够为 17，或者 18 吗？
2、如果为了保障不越界为什么不间接用 % 计算取余数？
3、为什么不间接用 key 的 hashCode，而是应用经 spreed 办法加工后的 hash 值？
这几个问题是面试常常会问到的相干问题。咱们一个个来解答。
4.1 数组大小必须为 2 的 n 次方
第一个问题的答案是数组大小必须为 2 的 n 次方，也就是 16、32、64…. 不能为其余值。
因为如果不是 2 的 n 次方，那么通过计算的数组下标会增大碰撞的几率，例如数组长度为 21，那么 n-1=20，对应的二进制为：
10100
那么 hash 值的二进制如果是 10000（十进制 16）、10010（十进制 18）、10001（十进制 17），和 10100 做 & 计算后，都是 10000，也就是都被映射到数组 16 这个下标上。这三个值会以链表的模式存储在数组 16 下标的地位。这显然不是咱们想要的后果。
但如果数组长度 n 为 2 的 n 次方，2 进制的数值为 10，100，1000，10000……n-1 后对应二进制为 1，11，111，1111…… 这样和 hash 值低位 & 后，会保留原来 hash 值的低位数值，那么只有 hash 值的低位不一样，就不会产生碰撞。
其实如果数组长度为 2 的 n 次方，那么 (n – 1) & hash 等价于 hash% n。那么为什么不间接用 hash% n 呢？这是因为按位的操作效率会更高，通过我本地测试，& 计算速度大略是 % 操作的 50 倍左右。
所以 JDK 为了性能，而应用这种奇妙的算法，在确保元素均匀分布的同时，还保障了效率。
4.2 为什么不间接用 key 的 hashCode？
原本咱们要剖析 spreed 办法的代码，然而当初看起来这个办法如同并没有什么用途，间接用 key 的 hashCode 来定位哈希表的地位就能够了啊，为什么还要通过 spreed 办法的加工呢？
其实说到底还是为了缩小碰撞的概率。咱们先看看 spreed 办法中的代码做了什么事件：
1、h ^ (h >>> 16)
h >>> 16 的意思是把 h 的二进制数值向右挪动 16 位。咱们晓得整形为 32 位，那么右移 16 位后，就是把高 16 位移到了低 16 位。而高 16 位清 0 了。
^ 为异或操作，二进制按位比拟，如果雷同则为 0，不同则为 1。这行代码的意思就是把高下 16 位做异或。如果两个 hashCode 值的低 16 位雷同，然而高位不同，通过如此计算，低 16 位会变得不一样了。
为什么要把低位变得不一样呢？
这是因为哈希表数组长度 n 会是偏小的数值，那么进行 (n – 1) & hash 运算时，始终应用的是 hash 较低位的值。那么即便 hash 值不同，但如果低位相当，也会产生碰撞。而进行 h ^ (h >>> 16) 加工后的 hash 值，让 hashCode 高位的值也参加了哈希运算，因而缩小了碰撞的概率。
2、(h ^ (h >>> 16)) & HASH_BITS
咱们再看残缺的代码，为何高位移到低位和原来低位做异或操作后，还须要和 HASH_BITS 这个常量做 & 计算呢？
HASH_BITS 这个常量的值为 0x7fffffff，转化为二进制为 0111 1111 1111 1111 1111 1111 1111 1111。
这个操作后会把最高位转为 0，其实就是打消了符号位，失去的都是负数。
这是因为负的 hashCode 在 ConcurrentHashMap 中有非凡的含意，因而咱们须要失去一个正的 hashCode。
总结
通过以上剖析咱们曾经分明 ConcurrentHashMap 中是如何通过 Hash 值来映射数组地位的，这外面的算法设计的确非常的奇妙。可能平时咱们编码用不到，但也要熟记于心，置信在面试中肯定用失去。
本文作者|李一鸣
内容起源|慕课网，程序员的梦工厂
本文由 mdnice 多平台公布
