java的hashmap怎么遍历（Java高级程序员必备ConcurrentHashMap实现原理）

Java高级程序员必备的ConcurrentHashMap深度实现原理：扩容、遍历与计数

作者：吴潇

职位：Java高级工程师

原创声明

这是本人署名原创文章，未经许可不支持转载且请勿抄袭。本公众号的所有文章均原创。为了容易理解和记忆，文章以图解为主、代码为辅。如果您感兴趣，欢迎关注！

ConcurrentHashMap是大多数Java程序员经常使用的集合类，它的实现原理经常出现在很多Java技术面试中，在工作中也时而用到，有必要掌握。在之前的一篇公众号文章中，我们分析了ConcurrentHashMap部分实现原理，涉及到内部数据结构、get操作和put操作这3个方面。基本上，掌握这3点基本可以应付大多数面试和工作需求了。如果你对ConcurrentHashMap的实现原理还有浓厚兴趣，想要进一步了解的话，本文适合你阅读。

在这篇文章中，我们将分析ConcurrentHashMap的以下性能优化措施：

1. 协助搬运（针对resize的优化）

2. 如何遍历

3. 计数器

约定：后文中table指的是ConcurrentHashMap最外层数组，bin指table数组的每个元素。

ConcurrentHashMap中最耗时的操作莫过于扩容（resize），所以对扩容操作进行优化能在很大程度上提高性能，而这个优化手段就是让并发执行put操作的线程协助搬运bin中的Node，把数据项从老数组转移到新数组，从而加速resize操作。具体方案是：在执行put操作的线程中，第一个发现需要扩容的线程负责分配新数组、开始转移部分Node，每次处理一个bin；此后，其他发现有resize正在进行中的线程参与到转移Node工作；其他也在执行put操作但不参与转移工作的线程继续执行原来的put操作（先在原数组中找到bin，如果遇到FowardingNode，则在新数组中插入）；执行get操作的线程不参与转移工作，遇到FordwardingNode则到新数组查询。

这种方式相对于JDK 1.7 ConcurrentHashMap的Segment机制有很大性能提升（在JDK1.7的ConcurrentHashMap中，put遇到扩容，只会阻塞等待，直到扩容完成再继续），因为其他并发访问的线程分摊了部分扩容工作。

具体怎么转移：参与转移的线程通过transferIndex字段声明自己要转移哪些bin。同时，为了防止这些线程所转移的bin有重叠的，转移线程会在sizeCtl变量中保存一个stamp提供区分的作用。为了不影响正在对ConcurrentHashMap进行遍历操作的线程，转移工作从最后一个bin开始（table.length -1），逐步往前处理，直到处理完第1个。每转移完成一个bin或正在转移当前bin，这里的位置就被放入一个FordwardingNode。因为转移Node操作需要较长时间，FordwardingNode让其他执行put/get/遍历操作的线程可以继续访问。

ConcurrentHashMap的扩容操作需多个put线程密切配合，且需考虑遍历线程、get线程、及其他不参与搬运的put的线程执行，其中还涉及到sizectl和transferIndex等控制变量的取值和判断，机制比较复杂将在下一篇文章中分析，如果感兴趣请关注本公众号以及时了解ConcurrentHashMap的扩容机制。

跟HashMap一样，ConcurrentHashMap也支持遍历操作，主要实现位于Traverser类（这个类也是ConcurrentHashMap内部所有iterator的基类）。因为ConcurrentHashMap默认不提供全表加锁特性，所以在遍历过程中，如果有新key value被存入，并且这个新key value存入的是已经访问过的bin，那么这个新key value不会被访问到。这是符合ConcurrentHashMap设计目标的，不是bug。

假如没有扩容操作，那么遍历操作非常简单，即直接从第1个bin开始，访问其中的Node，直到访问完最后一个bin，如下图所示。

在此基础上，为了与扩容操作并发执行，遍历操作这样执行：

1） 依然是从前往后逐个访问每个bin，

2） 如果遇到FordwardingNode，则把当前table引用、当前bin的访问位置和当前table总长度保存到table stack中，然后跳转到FordwardingNode所指向的新table，

3） 当前的索引index保持不变，在新table中按这个index访问（因为map每次扩容都是大小扩展为原来的2倍，每个Node在新table中的索引要么保持不变要么后移），

4） 访问完新table中的index位置的bin之后，再访问index baseSize这个位置上的bin (baseSize是老table的总长度)；

5） 从table stack还原出之前的table引用、index访问位置和table总长度，继续向后遍历。

这样就可以在有扩容操作也在进行的条件下，同时支持遍历操作，且保证每个Node只被访问一次。因为Node在老table和新table之间有固定对应关系，用这个条件保证。

没错，原来位于同一个bin的节点，在扩容以后只可能位于2个bin中，你可以尝试几个hash值测试一下（ps. 这或许是一道很有挑战性的考试题）。

另外，还需要注意：

1） ConcurrentHashMap迭代器不支持并发访问，如果不小心让多个线程并发访问从ConcurrentHashMap创建的同一个iterator，那么遍历提前结束，导致不能访问到所有元素。

2） 如果你查看ConcurrentHashMap的源码，有一处很恶心的错误（耗费了我很多时间才把它揪出来）。首先，Traverser类的构造函数如下：

注意这3个参数。然后是Traverser的子类：

到目前为止还没什么问题，但是再往下继承，问题来了：

看出问题了吗？子类中的index和size跟父类的index和size彻底交换了。不知道这是不是JDK的一个恶作剧还是一个bug。找来JDK 10的源码查看，发现这里的bug已经被修复了。虽然大家一直在使用JDK，但是它的确是包含bug的，而分析它的代码不仅能帮助你更好的使用，也可以避免踩到bug。

为了能够记录ConcurrentHashMap中的key-value个数，ConcurrentHashMap在它的内部实现了一个类似于LongAdder的高性能计数器（不了解LongAdder的同学，请阅读此文），但略有不同，比直接使用AtomicLong来进行计数的性能高出很多。与AtomicLong的不同点是，ConcurrentHashMap计数机制可以间接感知到线程竞争性，尽量减少CounterCell创建。

这里再简单说明一下LongAdder是如何相对于AtomicLong提高性能的，如下图所示。

上图已基本说明LongAdder提高性能的核心思想了，即把对一个原子变量的写入拆分到多个原子变量，这样就用空间换取了时间性能。更进一步，上图中只把一个AtomicLong替换成了3个AtomicLong。这个拆分个数是固定的，当并发访问的负载进一步提高，又会有性能瓶颈。因此，JDK 为了把LongAdder的未来改进空间全部榨干，引入了在这几年很火的"弹性扩展"思想，让拆分数量根据CPU核数和并发负载动态扩展，如下图所示。

这样JDK并发包中的一个不起眼的计数器也具备了强大的扩展性能，所以LongAdder的实现原理也是非常值得学习的，建议看完本文去研究一下。