java新建数组-​Java Map中那些巧妙的设计

最近拜读了一些Java Map的相关源码，不得不惊叹于JDK开发者们的鬼斧神工。他山之石可以攻玉，这些巧妙的设计思想非常有借鉴价值，可谓是最佳实践。然而，大多数有关Java Map原理的科普类文章都是专注于“点”，并没有连成“线”，甚至形成“网状结构”。因此，本文基于个人理解，对所阅读的部分源码进行了分类与总结，归纳出Map中的几个核心特性，包括：自动扩容、初始化与懒加载、哈希计算、位运算与并发，并结合源码进行深入讲解，希望看完本文的你也能从中获取到些许收获（本文默认采用JDK1.8中的HashMap）。

一 自动扩容

最小可用原则，容量超过一定阈值便自动进行扩容。

扩容是通过resize方法来实现的。扩容发生在putVal方法的最后，即写入元素之后才会判断是否需要扩容操作，当自增后的size大于之前所计算好的阈值threshold，即执行resize操作。

通过位运算>> 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，不需要锁定整个表。因此，锁定的范围更小java新建数组，并发度也会得到提升。

2 乐观锁

Synchronized+CAS

虽然引入了分段锁的机制，即可以保证线程安全，又可以解决锁粒度过粗导致的性能低下问题，但是对于追求极致性能的工程师来说，这还不是性能的天花板。因此，在JDK1.8中，ConcurrentHashMap摒弃了分段锁，使用了乐观锁的实现方式。放弃分段锁的原因主要有以下几点：

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的元素在哈希桶数组中存在java新建数组，并且不处于扩容状态时，则使用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进行计数，核心逻辑如下：

接着，我们来看下核心计算逻辑fullAddCount，代码还是比较多的，核心流程是通过一个死循环来实现的，循环体中包含了3个处理分支，为了方便讲解我将它们依次定义A、B、C。

其中，A分支中涉及到的操作又可以拆分为以下几点：

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源码中的冰山一角，但是基本包括了大部分的核心特性，涵盖了我们日常开发中的大部分场景。读源码跟读书一样，仿佛跨越了历史长河与作者进行近距离对话，揣摩他的心思，学习他的思想并加以传承。信息加工转化为知识并运用的过程是痛苦的，但是痛并快乐着。

电子书免费下载

《开源大数据前瞻与应用实战》

Flink社区重磅推出2021理论与实战精解系列电子书！第1期《开源大数据前瞻与理论实战》收录了多位大数据领域行业开拓者对未来前沿趋势的洞察，揭秘Apache Flink及开源生态的前沿独家应用！

限时特惠：本站每日持续更新海量设计资源，一年会员只需29.9元，全站资源免费下载
站长微信：ziyuanshu688

htebazile永久VIP

收藏 海报 链接