共计 12932 个字符，预计需要花费 33 分钟才能阅读完成。
简介：他山之石可以攻玉，这些奇妙的设计思维十分有借鉴价值，堪称是最佳实际。然而，大多数无关 Java Map 原理的科普类文章都是专一于“点”，并没有连成“线”，甚至造成“网状结构”。因而，本文基于集体了解，对所浏览的局部源码进行了分类与总结，演绎出 Map 中的几个外围个性。
作者 | 子澐
起源 | 阿里技术公众号
最近拜读了一些 Java Map 的相干源码，不得不惊叹于 JDK 开发者们的巧夺天工。他山之石可以攻玉，这些奇妙的设计思维十分有借鉴价值，堪称是最佳实际。然而，大多数无关 Java Map 原理的科普类文章都是专一于“点”，并没有连成“线”，甚至造成“网状结构”。因而，本文基于集体了解，对所浏览的局部源码进行了分类与总结，演绎出 Map 中的几个外围个性，包含：主动扩容、初始化与懒加载、哈希计算、位运算与并发，并联合源码进行深刻解说，心愿看完本文的你也能从中获取到些许播种（本文默认采纳 JDK1.8 中的 HashMap）。
一 主动扩容
最小可用准则，容量超过肯定阈值便主动进行扩容。
扩容是通过 resize 办法来实现的。扩容产生在 putVal 办法的最初，即写入元素之后才会判断是否须要扩容操作，当自增后的 size 大于之前所计算好的阈值 threshold，即执行 resize 操作。
通过位运算 <<1 进行容量裁减，即扩容 1 倍，同时新的阈值 newThr 也扩容为老阈值的 1 倍。
扩容时，总共存在三种状况：
- 哈希桶数组中某个地位只有 1 个元素，即不存在哈希抵触时，则间接将该元素 copy 至新哈希桶数组的对应地位即可。
- 哈希桶数组中某个地位的节点为树节点时，则执行红黑树的扩容操作。
- 哈希桶数组中某个地位的节点为一般节点时，则执行链表扩容操作，在 JDK1.8 中，为了防止之前版本中并发扩容所导致的死链问题，引入了高下位链表辅助进行扩容操作。
在日常的开发过程中，会遇到一些 bad case，比方：
HashMap hashMap = new HashMap(2);
hashMap.put("1", 1);
hashMap.put("2", 2);
hashMap.put("3", 3);当 hashMap 设置最初一个元素 3 的时候，会发现以后的哈希桶数组大小曾经达到扩容阈值 2 *0.75=1.5，紧接着会执行一次扩容操作，因而，此类的代码每次运行的时候都会进行一次扩容操作，效率低下。在日常开发过程中，肯定要充沛评估好 HashMap 的大小，尽可能保障扩容的阈值大于存储元素的数量，缩小其扩容次数。
二 初始化与懒加载
初始化的时候只会设置默认的负载因子，并不会进行其余初始化的操作，在首次应用
当 new 一个新的 HashMap 的时候，不会立刻对哈希数组进行初始化，而是在首次 put 元素的时候，通过 resize()办法进行初始化。
![上传中 …]()
resize()中会设置默认的初始化容量 DEFAULT_INITIAL_CAPACITY 为 16，扩容的阈值为 0.75*16 = 12，即哈希桶数组中元素达到 12 个便进行扩容操作。
最初创立容量为 16 的 Node 数组，并赋值给成员变量哈希桶 table，即实现了 HashMap 的初始化操作。
三 哈希计算
哈希表以哈希命名，足以阐明哈希计算在该数据结构中的重要水平。而在实现中，JDK 并没有间接应用 Object 的 native 办法返回的 hashCode 作为最终的哈希值，而是进行了二次加工。
以下别离为 HashMap 与 ConcurrentHashMap 计算 hash 值的办法，外围的计算逻辑雷同，都是应用 key 对应的 hashCode 与其 hashCode 右移 16 位的后果进行异或操作。此处，将高 16 位与低 16 位进行异或的操作称之为扰动函数，目标是将高位的特色融入到低位之中，升高哈希抵触的概率。
举个例子来了解下扰动函数的作用：
hashCode(key1) = 0000 0000 0000 1111 0000 0000 0000 0010
hashCode(key2) = 0000 0000 0000 0000 0000 0000 0000 0010若 HashMap 容量为 4，在不应用扰动函数的状况下，key1 与 key2 的 hashCode 注定会抵触（后两位雷同，均为 01）。
通过扰动函数解决后，可见 key1 与 key2 hashcode 的后两位不同，上述的哈希抵触也就防止了。
hashCode(key1) ^ (hashCode(key1) >>> 16)
0000 0000 0000 1111 0000 0000 0000 1101
hashCode(key2) ^ (hashCode(key2) >>> 16)
0000 0000 0000 0000 0000 0000 0000 0010这种增益会随着 HashMap 容量的缩小而减少。《An introduction to optimising a hashing strategy》文章中随机选取了哈希值不同的 352 个字符串，当 HashMap 的容量为 2^9 时，应用扰动函数能够缩小 10% 的碰撞，可见扰动函数的必要性。
此外，ConcurrentHashMap 中通过扰乱函数解决之后，须要与 HASH_BITS 做与运算，HASH_BITS 为 0x7ffffff，即只有最高位为 0，这样运算的后果使 hashCode 永远为负数。在 ConcurrentHashMap 中，预约义了几个非凡节点的 hashCode，如：MOVED、TREEBIN、RESERVED，它们的 hashCode 均定义为负值。因而，将一般节点的 hashCode 限定为负数，也就是为了避免与这些非凡节点的 hashCode 产生抵触。
1 哈希抵触
通过哈希运算，能够将不同的输出值映射到指定的区间范畴内，随之而来的是哈希抵触问题。思考一个极其的 case，假如所有的输出元素通过哈希运算之后，都映射到同一个哈希桶中，那么查问的复杂度将不再是 O(1)，而是 O(n)，相当于线性表的程序遍历。因而，哈希抵触是影响哈希计算性能的重要因素之一。哈希抵触如何解决呢？次要从两个方面思考，一方面是防止抵触，另一方面是在抵触时正当地解决抵触，尽可能进步查问效率。前者在下面的章节中曾经进行介绍，即通过扰动函数来减少 hashCode 的随机性，防止抵触。针对后者，HashMap 中给出了两种计划：拉链表与红黑树。
拉链表
在 JDK1.8 之前，HashMap 中是采纳拉链表的办法来解决抵触，即当计算出的 hashCode 对应的桶上曾经存在元素，但两者 key 不同时，会基于桶中已存在的元素拉出一条链表，将新元素链到已存在元素的后面。当查问存在抵触的哈希桶时，会程序遍历抵触链上的元素。同一 key 的判断逻辑如下图所示，先判断 hash 值是否雷同，再比拟 key 的地址或值是否雷同。
（1）死链
在 JDK1.8 之前，HashMap 在并发场景下扩容时存在一个 bug，造成死链，导致 get 该地位元素的时候，会死循环，使 CPU 利用率高居不下。这也阐明了 HashMap 不适于用在高并发的场景，高并发应该优先思考 JUC 中的 ConcurrentHashMap。然而，精益求精的 JDK 开发者们并没有抉择绕过问题，而是抉择直面问题并解决它。在 JDK1.8 之中，引入了高下位链表（双端链表）。
什么是高下位链表呢？在扩容时，哈希桶数组 buckets 会扩容一倍，以容量为 8 的 HashMap 为例，原有容量 8 扩容至 16，将 [0, 7] 称为低位，[8, 15]称为高位，低位对应 loHead、loTail，高位对应 hiHead、hiTail。
扩容时会顺次遍历旧 buckets 数组的每一个地位下面的元素：
- 若不存在抵触，则从新进行 hash 取模，并 copy 到新 buckets 数组中的对应地位。
- 若存在抵触元素，则采纳高下位链表进行解决。通过 e.hash & oldCap 来判断取模后是落在高位还是低位。举个例子：假如以后元素 hashCode 为 0001（疏忽高位），其运算后果等于 0，阐明扩容后后果不变，取模后还是落在低位[0, 7]，即 0001 & 1000 = 0000，还是原地位，再用低位链表将这类的元素链接起来。假如以后元素的 hashCode 为 1001，其运算后果不为 0，即 1001 & 1000 = 1000，扩容后会落在高位，新的地位刚好是旧数组索引（1）+ 旧数据长度（8）= 9，再用高位链表将这些元素链接起来。最初，将高下位链表的头节点别离放在扩容后数组 newTab 的指定地位上，即实现了扩容操作。这种实现升高了对共享资源 newTab 的拜访频次，先组织抵触节点，最初再放入 newTab 的指定地位。防止了 JDK1.8 之前每遍历一个元素就放入 newTab 中，从而导致并发扩容下的死链问题。
红黑树
在 JDK1.8 之中，HashMap 引入了红黑树来解决哈希抵触问题，而不再是拉链表。那么为什么要引入红黑树来代替链表呢？尽管链表的插入性能是 O(1)，但查问性能确是 O(n)，当哈希抵触元素十分多时，这种查问性能是难以承受的。因而，在 JDK1.8 中，如果抵触链上的元素数量大于 8，并且哈希桶数组的长度大于 64 时，会应用红黑树代替链表来解决哈希抵触，此时的节点会被封装成 TreeNode 而不再是 Node（TreeNode 其实继承了 Node，以利用多态个性），使查问具备 O(logn)的性能。
这里简略地回顾一下红黑树，它是一种均衡的二叉树搜寻树，相似地还有 AVL 树。两者外围的区别是 AVL 树谋求“相对均衡”，在插入、删除节点时，老本要高于红黑树，但也因而领有了更好的查问性能，实用于读多写少的场景。然而，对于 HashMap 而言，读写操作其实难分伯仲，因而抉择红黑树也算是在读写性能上的一种折中。
四 位运算
1 确定哈希桶数组大小
找到大于等于给定值的最小 2 的整数次幂。
tableSizeFor 依据输出容量大小 cap 来计算最终哈希桶数组的容量大小，找到大于等于给定值 cap 的最小 2 的整数次幂。乍眼一看，这一行一行的位运算让人云里雾里，莫不如采纳相似找法则的形式来摸索其中的神秘。
当 cap 为 3 时，计算过程如下：
cap = 3
n = 2
n |= n >>> 1 010 | 001 = 011 n = 3
n |= n >>> 2 011 | 000 = 011 n = 3
n |= n >>> 4 011 | 000 = 011 n = 3
….
n = n + 1 = 4当 cap 为 5 时，计算过程如下：
cap = 5
n = 4
n |= n >>> 1 0100 | 0010 = 0110 n = 6
n |= n >>> 2 0110 | 0001 = 0111 n = 7
….
n = n + 1 = 8因而，计算的意义在于找到大于等于 cap 的最小 2 的整数次幂。整个过程是找到 cap 对应二进制中最高位的 1，而后每次以 2 倍的步长（顺次移位 1、2、4、8、16）复制最高位 1 到前面的所有低位，把最高位 1 前面的所有位全副置为 1，最初进行 +1，即实现了进位。
相似二进制位的变动过程如下：
0100 1010
0111 1111
1000 0000找到输出 cap 的最小 2 的整数次幂作为最终容量能够了解为最小可用准则，尽可能地少占用空间，然而为什么必须要 2 的整数次幂呢？答案是，为了进步计算与存储效率，使每个元素对应 hash 值可能精确落入哈希桶数组给定的范畴区间内。确定数组下标采纳的算法是 hash & (n – 1)，n 即为哈希桶数组的大小。因为其总是 2 的整数次幂，这意味着 n - 1 的二进制模式永远都是 0000111111 的模式，即从最低位开始，间断呈现多个 1，该二进制与任何值进行 & 运算都会使该值映射到指定区间 [0, n-1]。比方：当 n = 8 时，n- 1 对应的二进制为 0111，任何与 0111 进行 & 运算都会落入[0,7] 的范畴内，即落入给定的 8 个哈希桶中，存储空间利用率 100%。举个反例，当 n =7，n- 1 对应的二进制为 0110，任何与 0110 进行 & 运算会落入到第 0、6、4、2 个哈希桶，而不是 [0,6] 的区间范畴内，少了 1、3、5 三个哈希桶，这导致存储空间利用率只有不到 60%，同时也减少了哈希碰撞的几率。
2 ASHIFT 偏移量计算
获取给定值的最高有效位数（移位除了可能进行乘除运算，还能用于保留高、低位操作，右移保留高位，左移保留低位）。
ConcurrentHashMap 中的 ABASE+ASHIFT 是用来计算哈希数组中某个元素在理论内存中的初始地位，ASHIFT 采取的计算形式是 31 与 scale 前导 0 的数量做差，也就是 scale 的理论位数 -1。scale 就是哈希桶数组 Node[]中每个元素的大小，通过 ((long)i << ASHIFT) + ABASE) 进行计算，便可失去数组中第 i 个元素的起始内存地址。
咱们持续看下前导 0 的数量是怎么计算出来的，numberOfLeadingZeros 是 Integer 的静态方法，还是沿用找法则的形式一探到底。
假如 i = 0000 0000 0000 0100 0000 0000 0000 0000，n = 1
i >>> 16 0000 0000 0000 0000 0000 0000 0000 0100 不为 0
i >>> 24 0000 0000 0000 0000 0000 0000 0000 0000 等于 0 右移了 24 位等于 0，阐明 24 位到 31 位之间必定全为 0，即 n = 1 + 8 = 9，因为高 8 位全为 0，并且曾经将信息记录至 n 中，因而能够舍弃高 8 位，即 i <<= 8。此时，
i = 0000 0100 0000 0000 0000 0000 0000 0000相似地，i >>> 28 也等于 0，阐明 28 位到 31 位全为 0，n = 9 + 4 = 13，舍弃高 4 位。此时，
i = 0100 0000 0000 0000 0000 0000 0000 0000持续运算，
i >>> 30 0000 0000 0000 0000 0000 0000 0000 0001 不为 0
i >>> 31 0000 0000 0000 0000 0000 0000 0000 0000 等于 0 最终可得出 n = 13，即有 13 个前导 0。n -= i >>> 31 是查看最高位 31 位是否是 1，因为 n 初始化为 1，如果最高位是 1，则不存在前置 0，即 n = n – 1 = 0。
总结一下，以上的操作其实是基于二分法的思维来定位二进制中 1 的最高位，先看高 16 位，若为 0，阐明 1 存在于低 16 位；反之存在高 16 位。由此将搜寻范畴由 32 位（确切的说是 31 位）缩小至 16 位，进而再一分为二，校验高 8 位与低 8 位，以此类推。
计算过程中校验的位数顺次为 16、8、4、2、1，加起来刚好为 31。为什么是 31 不是 32 呢？因为前置 0 的数量为 32 的状况下 i 只能为 0，在后面的 if 条件中曾经进行过滤。这样一来，非 0 值的状况下，前置 0 只能呈现在高 31 位，因而只须要校验高 31 位即可。最终，用总位数减去计算出来的前导 0 的数量，即可得出二进制的最高有效位数。代码中应用的是 31 – Integer.numberOfLeadingZeros(scale)，而不是总位数 32，这是为了可能失去哈希桶数组中第 i 个元素的起始内存地址，不便进行 CAS 等操作。
五 并发
1 乐观锁
全表锁
HashTable 中采纳了全表锁，即所有操作均上锁，串行执行，如下图中的 put 办法所示，采纳 synchronized 关键字润饰。这样尽管保障了线程平安，然而在多核处理器时代也极大地影响了计算性能，这也以致 HashTable 逐步淡出开发者们的视线。
分段锁
针对 HashTable 中锁粒度过粗的问题，在 JDK1.8 之前，ConcurrentHashMap 引入了分段锁机制。整体的存储构造如下图所示，在原有构造的根底上拆分出多个 segment，每个 segment 下再挂载原来的 entry（上文中常常提到的哈希桶数组），每次操作只须要锁定元素所在的 segment，不须要锁定整个表。因而，锁定的范畴更小，并发度也会失去晋升。
2 乐观锁
Synchronized+CAS
尽管引入了分段锁的机制，即能够保障线程平安，又能够解决锁粒度过粗导致的性能低下问题，然而对于谋求极致性能的工程师来说，这还不是性能的天花板。因而，在 JDK1.8 中，ConcurrentHashMap 摒弃了分段锁，应用了乐观锁的实现形式。放弃分段锁的起因次要有以下几点：
- 应用 segment 之后，会减少 ConcurrentHashMap 的存储空间。
- 当单个 segment 过大时，并发性能会急剧下降。
ConcurrentHashMap 在 JDK1.8 中的实现废除了之前的 segment 构造，沿用了与 HashMap 中的相似的 Node 数组构造。
ConcurrentHashMap 中的乐观锁是采纳 synchronized+CAS 进行实现的。这里次要看下 put 的相干代码。
当 put 的元素在哈希桶数组中不存在时，则间接 CAS 进行写操作。
这里波及到了两个重要的操作，tabAt 与 casTabAt。能够看出，这外面都应用了 Unsafe 类的办法。Unsafe 这个类在日常的开发过程中比拟常见。咱们通常对 Java 语言的认知是：Java 语言是平安的，所有操作都基于 JVM，在平安可控的范畴内进行。然而，Unsafe 这个类会突破这个边界，使 Java 领有 C 的能力，能够操作任意内存地址，是一把双刃剑。这里应用到了前文中所提到的 ASHIFT，来计算出指定元素的起始内存地址，再通过 getObjectVolatile 与 compareAndSwapObject 别离进行取值与 CAS 操作。
在获取哈希桶数组中指定地位的元素时为什么不能间接 get 而是要应用 getObjectVolatile 呢？因为在 JVM 的内存模型中，每个线程有本人的工作内存，也就是栈中的局部变量表，它是主存的一份 copy。因而，线程 1 对某个共享资源进行了更新操作，并写入到主存，而线程 2 的工作内存之中可能还是旧值，脏数据便产生了。Java 中的 volatile 是用来解决上述问题，保障可见性，任意线程对 volatile 关键字润饰的变量进行更新时，会使其它线程中该变量的正本生效，须要从主存中获取最新值。尽管 ConcurrentHashMap 中的 Node 数组是由 volatile 润饰的，能够保障可见性，然而 Node 数组中元素是不具备可见性的。因而，在获取数据时通过 Unsafe 的办法间接到主存中拿，保障获取的数据是最新的。
持续往下看 put 办法的逻辑，当 put 的元素在哈希桶数组中存在，并且不处于扩容状态时，则应用 synchronized 锁定哈希桶数组中第 i 个地位中的第一个元素 f（头节点 2），接着进行 double check，相似于 DCL 单例模式的思维。校验通过后，会遍历以后抵触链上的元素，并抉择适合的地位进行 put 操作。此外，ConcurrentHashMap 也沿用了 HashMap 中解决哈希抵触的计划，链表 + 红黑树。这里只有在产生哈希抵触的状况下才应用 synchronized 锁定头节点，其实是比分段锁更细粒度的锁实现，只在特定场景下锁定其中一个哈希桶，升高锁的影响范畴。
Java Map 针对并发场景解决方案的演进方向能够归结为，从乐观锁到乐观锁，从粗粒度锁到细粒度锁，这也能够作为咱们在日常并发编程中的指导方针。
3 并发求和
CounterCell 是 JDK1.8 中引入用来并发求和的利器，而在这之前采纳的是【尝试无锁求和】+【抵触时加锁重试】的策略。看下 CounterCell 的正文，它是改编自 LongAdder 和 Striped64。咱们先看下求和操作，其实就是取 baseCount 作为初始值，而后遍历 CounterCell 数组中的每一个 cell，将各个 cell 的值进行累加。这里额定阐明下 @sun.misc.Contender 注解的作用，它是 Java8 中引入用来解决缓存行伪共享问题的。什么是伪共享呢？简略说下，思考到 CPU 与主存之间速度的微小差别，在 CPU 中引入了 L1、L2、L3 多级缓存，缓存中的存储单位是缓存行，缓存行大小为 2 的整数次幂字节，32-256 个字节不等，最常见的是 64 字节。因而，这将导致有余 64 字节的变量会共享同一个缓存行，其中一个变量生效会影响到同一个缓存行中的其余变量，以致性能降落，这就是伪共享问题。思考到不同 CPU 的缓存行单位的差异性，Java8 中便通过该注解将这种差异性屏蔽，依据理论缓存行大小来进行填充，使被润饰的变量可能独占一个缓存行。
image.png
再来看下 CounterCell 是如何实现计数的，每当 map 中的容量有变动时会调用 addCount 进行计数，外围逻辑如下：
- 当 counterCells 不为空，或 counterCells 为空且对 baseCount 进行 CAS 操作失败时进入到后续计数解决逻辑，否则对 baseCount 进行 CAS 操作胜利，间接返回。
- 后续计数解决逻辑中会调用外围计数办法 fullAddCount，但须要满足以下 4 个条件中的任意一个：1、counterCells 为空；2、counterCells 的 size 为 0；3、counterCells 对应地位上的 counterCell 为空；4、CAS 更新 counterCells 对应地位上的 counterCell 失败。这些条件背地的语义是，当前情况下，计数曾经或已经呈现过并发抵触，须要优先借助于 CounterCell 来解决。若 counterCells 与对应地位上的元素曾经初始化（条件 4），则先尝试 CAS 进行更新，若失败则调用 fullAddCount 持续解决。若 counterCells 与对应地位上的元素未初始化实现（条件 1、2、3），也要调用 AddCount 进行后续解决。
- 这里确定 cell 下标时采纳了 ThreadLocalRandom.getProbe()作为哈希值，这个办法返回的是以后 Thread 中 threadLocalRandomProbe 字段的值。而且当哈希值抵触时，还能够通过 advanceProbe 办法来更换哈希值。这与 HashMap 中的哈希值计算逻辑不同，因为 HashMap 中要保障同一个 key 进行屡次哈希计算的哈希值雷同并且能定位到对应的 value，即使两个 key 的哈希值抵触也不能轻易更换哈希值，只能采纳链表或红黑树解决抵触。然而在计数场景，咱们并不需要保护 key-value 的关系，只须要在 counterCells 中找到一个适合的地位放入计数 cell，地位的差别对最终的求和后果是没有影响的，因而当抵触时能够基于随机策略更换一个哈希值来防止抵触。
接着，咱们来看下外围计算逻辑 fullAddCount，代码还是比拟多的，外围流程是通过一个死循环来实现的，循环体中蕴含了 3 个解决分支，为了不便解说我将它们顺次定义 A、B、C。
- A：示意 counterCells 曾经初始化实现，因而能够尝试更新或创立对应地位的 CounterCell。
- B：示意 counterCells 未初始化实现，且无抵触（拿到 cellsBusy 锁），则加锁初始化 counterCells，初始容量为 2。
- C：示意 counterCells 未初始化实现，且有抵触（未能拿到 cellsBusy 锁），则 CAS 更新 baseCount，baseCount 在求和时也会被算入到最终后果中，这也相当于是一种兜底策略，既然 counterCells 正在被其余线程锁定，那以后线程也没必要再期待了，间接尝试应用 baseCount 进行累加。
其中，A 分支中波及到的操作又能够拆分为以下几点： - a1：对应地位的 CounterCell 未创立，采纳锁 +Double Check 的策略尝试创立 CounterCell，失败的话则 continue 进行重试。这外面采纳的锁是 cellsBusy，它保障创立 CounterCell 并放入 counterCells 时肯定是串行执行，防止反复创立，其实就是应用了 DCL 单例模式的策略。在 CounterCells 的创立、扩容中都须要应用该锁。
- a2：冲突检测，变量 wasUncontended 是调用方 addCount 中传入的，示意前置的 CAS 更新 cell 失败，有抵触，须要更换哈希值【a7】后持续重试。
- a3：对应地位的 CounterCell 不为空，间接 CAS 进行更新。
- a4：
- 冲突检测，当 counterCells 的援用值不等于以后线程对应的援用值时，阐明有其余线程更改了 counterCells 的援用，呈现抵触，则将 collide 设为 false，下次迭代时可进行扩容。
- 容量限度，counterCells 容量的最大值为大于等于 NCPU（理论机器 CPU 外围的数量）的最小 2 的整数次幂，当达到容量限度时前面的扩容分支便永远不会执行。这里限度的意义在于，实在并发度是由 CPU 外围来决定，当 counterCells 容量与 CPU 外围数量相等时，现实状况下就算所有 CPU 外围在同时运行不同的计数线程时，都不应该呈现抵触，每个线程抉择各自的 cell 进行解决即可。如果呈现抵触，肯定是哈希值的问题，因而采取的措施是从新计算哈希值 a7，而不是通过扩容来解决。工夫换空间，防止不必要的存储空间节约，十分赞的想法~
- a5：更新扩容标记位，下次迭代时将会进行扩容。
- a6：进行加锁扩容，每次扩容 1 倍。
- a7：更换哈希值。
private final void fullAddCount(long x, boolean wasUncontended) {
int h;
// 初始化 probe
if ((h = ThreadLocalRandom.getProbe()) == 0) {ThreadLocalRandom.localInit(); // force initialization
h = ThreadLocalRandom.getProbe();
wasUncontended = true;
}
// 用来管制扩容操作
boolean collide = false; // True if last slot nonempty
for (;;) {CounterCell[] as; CounterCell a; int n; long v;
//【A】counterCells 曾经初始化结束
if ((as = counterCells) != null && (n = as.length) > 0) {
//【a1】对应地位的 CounterCell 未创立
if ((a = as[(n - 1) & h]) == null) {
// cellsBusy 其实是一个锁，cellsBusy= 0 时示意无抵触
if (cellsBusy == 0) { // Try to attach new Cell
// 创立新的 CounterCell
CounterCell r = new CounterCell(x); // Optimistic create
// Double Check，加锁（通过 CAS 将 cellsBusy 设置 1）if (cellsBusy == 0 &&
U.compareAndSwapInt(this, CELLSBUSY, 0, 1)) {
boolean created = false;
try { // Recheck under lock
CounterCell[] rs; int m, j;
// Double Check
if ((rs = counterCells) != null &&
(m = rs.length) > 0 &&
rs[j = (m - 1) & h] == null) {
// 将新创建的 CounterCell 放入 counterCells 中
rs[j] = r;
created = true;
}
} finally {
// 解锁，这里为什么不必 CAS？因为以后流程中须要在获取锁的前提下进行，即串行执行，因而不存在并发更新问题，只须要失常更新即可
cellsBusy = 0;
}
if (created)
break;
// 创立失败则重试
continue; // Slot is now non-empty
}
}
// cellsBusy 不为 0，阐明被其余线程争抢到了锁，还不能思考扩容
collide = false;
}
//【a2】冲突检测
else if (!wasUncontended) // CAS already known to fail
// 调用方 addCount 中 CAS 更新 cell 失败，有抵触，则持续尝试 CAS
wasUncontended = true; // Continue after rehash
//【a3】对应地位的 CounterCell 不为空，间接 CAS 进行更新
else if (U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))
break;
//【a4】容量限度
else if (counterCells != as || n >= NCPU)
// 阐明 counterCells 容量的最大值为大于 NCPU（理论机器 CPU 外围的数量）最小 2 的整数次幂。// 这里限度的意义在于，并发度是由 CPU 外围来决定，当 counterCells 容量与 CPU 外围数量相等时，实践上讲就算所有 CPU 外围都在同时运行不同的计数线程时，都不应该呈现抵触，每个线程抉择各自的 cell 进行解决即可。如果呈现抵触，肯定是哈希值的问题，因而采取的措施是从新计算哈希值（h = ThreadLocalRandom.advanceProbe(h)），而不是通过扩容来解决
// 当 n 大于 NCPU 时前面的分支就不会走到了
collide = false; // At max size or stale
//【a5】更新扩容标记位
else if (!collide)
// 阐明映射到 cell 地位不为空，并且尝试进行 CAS 更新时失败了，则阐明有竞争，将 collide 设置为 true，下次迭代时执行前面的扩容操作，升高竞争度
// 有竞争时，执行 rehash+ 扩容，当容量大于 CPU 外围时则进行扩容只进行 rehash
collide = true;
//【a6】加锁扩容
else if (cellsBusy == 0 &&
U.compareAndSwapInt(this, CELLSBUSY, 0, 1)) {
// 加锁扩容
try {if (counterCells == as) {// Expand table unless stale
// 扩容 1 倍
CounterCell[] rs = new CounterCell[n << 1];
for (int i = 0; i < n; ++i)
rs[i] = as[i];
counterCells = rs;
}
} finally {cellsBusy = 0;}
collide = false;
continue; // Retry with expanded table
}
//【a7】更换哈希值
h = ThreadLocalRandom.advanceProbe(h);
}
//【B】counterCells 未初始化实现，且无抵触，则加锁初始化 counterCells
else if (cellsBusy == 0 && counterCells == as &&
U.compareAndSwapInt(this, CELLSBUSY, 0, 1)) {
boolean init = false;
try { // Initialize table
if (counterCells == as) {CounterCell[] rs = new CounterCell[2];
rs[h & 1] = new CounterCell(x);
counterCells = rs;
init = true;
}
} finally {cellsBusy = 0;}
if (init)
break;
}
//【C】counterCells 未初始化实现，且有抵触，则 CAS 更新 baseCount
else if (U.compareAndSwapLong(this, BASECOUNT, v = baseCount, v + x))
break; // Fall back on using base
}CounterCell 的设计很奇妙，它的背地其实就是 JDK1.8 中的 LongAdder。核心思想是：在并发较低的场景下间接采纳 baseCount 累加，否则联合 counterCells，将不同的线程散列到不同的 cell 中进行计算，尽可能地确保拜访资源的隔离，缩小抵触。LongAdder 相比拟于 AtomicLong 中无脑 CAS 的策略，在高并发的场景下，可能缩小 CAS 重试的次数，进步计算效率。
六 结语
以上可能只是 Java Map 源码中的冰山一角，然而根本包含了大部分的外围个性，涵盖了咱们日常开发中的大部分场景。读源码跟读书一样，好像逾越了历史长河与作者进行近距离对话，琢磨他的心理，学习他的思维并加以传承。信息加工转化为常识并使用的过程是苦楚的，然而痛并高兴着。
原文链接
本文为阿里云原创内，未经容许不得转载。
