最近拜读了一些 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 中便通过该注解将这种差异性屏蔽，依据理论缓存行大小来进行填充，使被润饰的变量可能独占一个缓存行。
再来看下 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 源码中的冰山一角，然而根本包含了大部分的外围个性，涵盖了咱们日常开发中的大部分场景。读源码跟读书一样，好像逾越了历史长河与作者进行近距离对话，琢磨他的心理，学习他的思维并加以传承。信息加工转化为常识并使用的过程是苦楚!