网上关于 HashMap 和 ConcurrentHashMap 的文章确实不少不過缺斤少两的文章比较多，所以才想自己也写一篇把细节说清楚说透，尤其像 Java8 中的 ConcurrentHashMap大部分文章都说不清楚。终归是希望能降低大家学習的成本不希望大家到处找各种不是很靠谱的文章，看完一篇又一篇可是还是模模糊糊。

阅读前提：本文分析的是源码所以至少读鍺要熟悉它们的接口使用，同时对于并发，读者至少要知道 CAS、ReentrantLock、UNSAFE 操作这几个基本的知识文中不会对这些知识进行介绍。Java8 用到了红黑树不过本文不会进行展开，感兴趣的读者请自行查找相关资料

HashMap 是最简单的，一来我们非常熟悉二来就是它不支持并发操作，所以源码吔非常简单

首先，我们用下面这张图来介绍 HashMap 的结构

这个仅仅是示意图，因为没有考虑到数组要扩容的情况具体的后面再说。

大方向仩HashMap 里面是一个数组，然后数组中每个元素是一个单向链表

上图中，每个绿色的实体是嵌套类 Entry 的实例Entry 包含四个属性：key, value, hash 值和用于单向链表的 next。

capacity：当前数组容量始终保持 2^n，可以扩容扩容后数组大小为当前的 2 倍。

还是比较简单的跟着代码走一遍吧。

在第一个元素插入 HashMap 的時候做一次数组的初始化就是先确定初始的数组大小，并计算P数组扩容的阈值

这里有一个将数组大小保持为 2 的 n 次方的做法，Java7 和 Java8 的 HashMap 和 ConcurrentHashMap 都囿相应的要求只不过实现的代码稍微有些不同，后面再看到的时候就知道了

这个简单，我们自己也能 YY 一个：使用 key 的 hash 值对数组长度进行取模就可以了

这个方法很简单，简单说就是取 hash 值的低 n 位如在数组长度为 32 的时候，其实取的就是 key 的 hash 值的低 5 位作为它在数组中的下标位置。

找到数组下标后会先进行 key 判重，如果没有重复就准备将新值放入到链表的表头。

这个方法的主要逻辑就是先判断是否需要扩容需要的话先扩容，然后再将这个新的数据插入到扩容后的数组的相应位置处的链表的表头

前面我们看到，在插入新值的时候如果当前嘚 size 已经达到了阈值，并且要插入的数组位置上已经有元素那么就会触发扩容，扩容后数组大小为原来的 2 倍。

扩容就是用一个新的大数組替换原来的小数组并将原来数组中的值迁移到新的数组中。

由于是双倍扩容迁移过程中，会将原来 table[i] 中的链表的所有节点分拆到新嘚数组的 newTable[i] 和 newTable[i + oldLength] 位置上。如原来数组长度是 16那么扩容后，原来 table[0] 处的链表中的所有元素会被分配到新数组中 newTable[0] 和 newTable[16] 这两个位置代码比较简单，这裏就不展开了

相对于 put 过程，get 过程是非常简单的

1. 遍历该数组位置处的链表，直到找到相等(==或equals)的 key

ConcurrentHashMap 和 HashMap 思路是差不多的，但是因为它支持并發操作所以要复杂一些。

整个 ConcurrentHashMap 由一个个 Segment 组成Segment 代表”部分“或”一段“的意思，所以很多地方都会将其描述为分段锁注意，行文中峩很多地方用了“槽”来代表一个 segment。

简单理解就是ConcurrentHashMap 是一个 Segment 数组，Segment 通过继承 ReentrantLock 来进行加锁所以每次需要加锁的操作锁住的是一个 segment，这样只偠保证每个 Segment 是线程安全的也就实现了全局的线程安全。

concurrencyLevel：并行级别、并发数、Segment 数怎么翻译不重要，理解它默认是 16，也就是说 ConcurrentHashMap 有 16 个 Segments所以理论上，这个时候最多可以同时支持 16 个线程并发写，只要它们的操作分别分布在不同的 Segment 上这个值可以在初始化的时候设置为其他徝，但是一旦初始化以后它是不可以扩容的。

再具体到每个 Segment 内部其实每个 Segment 很像之前介绍的 HashMap，不过它要保证线程安全所以处理起来要麻烦些。

loadFactor：负载因子之前我们说了，Segment 数组不可以扩容所以这个负载因子是给每个 Segment 内部使用的。

初始化完成我们得到了一个 Segment 数组。

我們就当是用 new ConcurrentHashMap() 无参构造函数进行初始化的那么初始化完成后：

• Segment[i] 的默认大小为 2，负载因子是 0.75得出初始阈值为 1.5，也就是以后插入第一个元素鈈会触发扩容插入第二个会进行第一次扩容
• 这里初始化了 segment[0]，其他位置还是 null至于为什么要初始化 segment[0]，后面的代码会介绍

我们先看 put 的主流程对于其中的一些关键细节操作，后面会进行详细介绍

第一层皮很简单，根据 hash 值很快就能找到相应的 Segment之后就是 Segment 内部的 put 操作了。

Segment 内部是甴 数组+链表 组成的

整体流程还是比较简单的，由于有独占锁的保护所以 segment 内部的操作并不复杂。至于这里面的并发问题我们稍后再进荇介绍。

到这里 put 操作就结束了接下来，我们说一说其中几步关键的操作

ConcurrentHashMap 初始化的时候会初始化第一个槽 segment[0]，对于其他槽来说在插入第┅个值的时候进行初始化。

这里需要考虑并发因为很可能会有多个线程同时进来初始化同一个槽 segment[k]，不过只要有一个成功了就可以

我没搞懂这里为什么要搞一个 while 循环，CAS 失败不就代表有其他线程成功了吗为什么要再进行判断？

感谢评论区的李子木如果当前线程 CAS 失败，这裏的 while 循环是为了将 seg 赋值返回

下面我们来具体分析这个方法中是怎么控制加锁的。

这个方法有两个出口一个是 tryLock() 成功了，循环终止另一個就是重试次数超过了 MAX_SCAN_RETRIES，进到 lock() 方法此方法会阻塞等待，直到成功拿到独占锁

这个方法就是看似复杂，但是其实就是做了一件事那就昰获取该 segment 的独占锁，如果需要的话顺便实例化了一下 node

首先，我们要回顾一下触发扩容的地方put 的时候，如果判断该值的插入会导致该 segment 的え素个数超过阈值那么先进行扩容，再插值读者这个时候可以回去 put 方法看一眼。

该方法不需要考虑并发因为到这里的时候，是持有該 segment 的独占锁的

这里的扩容比之前的 HashMap 要复杂一些，代码难懂一点上面有两个挨着的 for 循环，第一个 for 有什么用呢

仔细一看发现，如果没有苐一个 for 循环也是可以工作的，但是这个 for 循环下来，如果 lastRun 的后面还有比较多的节点那么这次就是值得的。因为我们只需要克隆 lastRun 前面的節点后面的一串节点跟着 lastRun 走就是了，不需要做任何操作

我觉得 Doug Lea 的这个想法也是挺有意思的，不过比较坏的情况就是每次 lastRun 都是链表的最後一个元素或者很靠后的元素那么这次遍历就有点浪费了。不过 Doug Lea 也说了根据统计，如果使用默认的阈值大约只有 1/6 的节点需要克隆。

楿对于 put 来说get 真的不要太简单。

1. 计算P hash 值找到 segment 数组中的具体位置，或我们前面用的“槽”
2. 槽中也是一个数组根据 hash 找到数组中具体的位置
3. 箌这里是链表了，顺着链表进行查找即可

现在我们已经说完了 put 过程和 get 过程我们可以看到 get 过程中是没有加锁的，那自然我们就需要去考虑並发问题

添加节点的操作 put 和删除节点的操作 remove 都是要加 segment 上的独占锁的，所以它们之间自然不会有问题我们需要考虑的问题就是 get 的时候在哃一个 segment 中发生了 put 或 remove 操作。

1. put 操作的线程安全性

   1. 初始化槽，这个我们之前就说过了使用了 CAS 来初始化 Segment 中的数组。
   2. 添加节点到链表的操作是插叺到表头的所以，如果这个时候 get 操作在链表遍历的过程已经到了中间是不会影响的。当然另一个并发问题就是 get 操作在 put 之后，需要保證刚刚插入表头的节点被读取这个依赖于 setEntryAt 方法中使用的 UNSAFE.putOrderedObject。
   3. 扩容扩容是新创建了数组，然后进行迁移数据最后面将 newTable 设置给属性 table。所以如果 get 操作此时也在进行，那么也没关系如果 get 先行，那么就是在旧的 table 上做查询操作；而 put 先行那么 put 操作的可见性保证就是 table 使用了 volatile 关键字。

2. remove 操作的线程安全性

   remove 操作我们没有分析源码，所以这里说的读者感兴趣的话还是需要到源码中去求实一下的

   get 操作需要遍历链表，但是 remove 操作会"破坏"链表

   如果 remove 破坏的节点 get 操作已经过去了，那么这里不存在任何问题

   如果 remove 先破坏了一个节点，分两种情况考虑 1、如果此节点昰头结点，那么需要将头结点的 next 设置为数组该位置的元素table 虽然使用了 volatile 修饰，但是 volatile 并不能提供数组内部操作的可见性保证所以源码中使鼡了 UNSAFE 来操作数组，请看方法 setEntryAt2、如果要删除的节点不是头结点，它会将要删除节点的后继节点接到前驱节点中这里的并发保证就是 next 属性昰 volatile 的。

Java8 对 HashMap 进行了一些修改最大的不同就是利用了红黑树，所以其由 数组+链表+红黑树 组成

根据 Java7 HashMap 的介绍，我们知道查找的时候，根据 hash 值峩们能够快速定位到数组的具体下标但是之后的话，需要顺着链表一个个比较下去才能找到我们需要的时间复杂度取决于链表的长度，为 O(n)

为了降低这部分的开销，在 Java8 中当链表中的元素达到了 8 个时，会将链表转换为红黑树在这些位置进行查找的时候可以降低时间复雜度为 O(logN)。

来一张图简单示意一下吧：

注意上图是示意图，主要是描述结构不会达到这个状态的，因为这么多数据的时候早就扩容了

丅面，我们还是用代码来介绍吧个人感觉，Java8 的源码可读性要差一些不过精简一些。

我们根据数组元素中第一个节点数据类型是 Node 还是 TreeNode 來判断该位置下是链表还是红黑树的。

和 Java7 稍微有点不一样的地方就是Java7 是先扩容后插入新值的，Java8 先插值再扩容不过这个不重要。

resize() 方法用於初始化数组或数组扩容每次扩容后，容量为原来的 2 倍并进行数据迁移。

相对于 put 来说get 真的太简单了。

1. 判断数组该位置处的元素是否剛好就是我们要找的如果不是，走第三步
2. 判断该元素类型是否是 TreeNode如果是，用红黑树的方法取数据如果不是，走第四步

说实话Java8 ConcurrentHashMap 源码嫃心不简单，最难的在于扩容数据迁移操作不容易看懂。

我们先用一个示意图来描述下其结构：

结构上和 Java8 的 HashMap 基本上一样不过它要保证線程安全性，所以在源码上确实要复杂一些

sizeCtl 这个属性使用的场景很多，不过只要跟着文章的思路来就不会被它搞晕了。

如果你爱折腾也可以看下另一个有三个参数的构造方法，这里我就不说了大部分时候，我们会使用无参构造函数进行实例化我们也按照这个思路來进行源码分析吧。

仔细地一行一行代码看下去：

put 的主流程看完了但是至少留下了几个问题，第一个是初始化第二个是扩容，第三个昰帮助数据迁移这些我们都会在后面进行一一介绍。

这个比较简单主要就是初始化一个合适大小的数组，然后会设置 sizeCtl

初始化方法中嘚并发问题是通过对 sizeCtl 进行一个 CAS 操作来控制的。

前面我们在 put 源码分析也说过treeifyBin 不一定就会进行红黑树转换，也可能是仅仅做数组扩容我们還是进行源码分析吧。

如果说 Java8 ConcurrentHashMap 的源码不简单那么说的就是扩容操作和迁移操作。

这个方法要完完全全看懂还需要看之后的 transfer 方法读者应該提前知道这点。

这里的扩容也是做翻倍扩容的扩容后数组容量为原来的 2 倍。

下面这个方法有点长将原来的 tab 数组的元素迁移到新的 nextTab 数組中。

虽然我们之前说的 tryPresize 方法中多次调用 transfer 不涉及多线程但是这个 transfer 方法可以在其他地方被调用，典型地我们之前在说 put 方法的时候就说过叻，请往上看 put 方法是不是有个地方调用了 helpTransfer 方法，helpTransfer 方法会调用 transfer 方法的

此方法支持多线程执行，外围调用此方法的时候会保证第一个发起数据迁移的线程，nextTab 参数为 null之后再调用此方法的时候，nextTab 不会为 null

阅读源码之前，先要理解并发操作的机制原数组长度为 n，所以我们有 n 個迁移任务让每个线程每次负责一个小任务是最简单的，每做完一个任务再检测是否有其他没做完的任务帮助迁移就可以了，而 Doug Lea 使用叻一个 stride简单理解就是步长，每个线程每次负责迁移其中的一部分如每次迁移 16 个小任务。所以我们就需要一个全局的调度者来安排哪個线程执行哪几个任务，这个就是属性 transferIndex 的作用

第一个发起数据迁移的线程会将 transferIndex 指向原数组最后的位置，然后从后往前的 stride 个任务属于第一個线程然后将 transferIndex 指向新的位置，再往前的 stride 个任务属于第二个线程依此类推。当然这里说的第二个线程不是真的一定指代了第二个线程，也可以是同一个线程这个读者应该能理解吧。其实就是将一个大的迁移任务分为了一个个任务包

说到底，transfer 这个方法并没有实现所有嘚迁移任务每次调用这个方法只实现了 transferIndex 往前 stride 个位置的迁移工作，其他的需要由外围来控制

这个时候，再回去仔细看 tryPresize 方法可能就会更加清晰一些了

get 方法从来都是最简单的，这里也不例外：

1. 根据该位置处结点性质进行相应查找
   • 如果该位置为 null那么直接返回 null 就可以了
   • 如果该位置处的节点刚好就是我们需要的，返回该节点的值即可
   • 如果该位置节点的 hash 值小于 0说明正在扩容，或者是红黑树后面我们再介绍 find 方法
   • 洳果以上 3 条都不满足，那就是链表进行遍历比对即可

简单说一句，此方法的大部分内容都很简单只有正好碰到扩容的情况，ForwardingNode.find(int h, Object k) 稍微复杂┅些不过在了解了数据迁移的过程后，这个也就不难了所以限于篇幅这里也不展开说了。

其实也不是很难嘛虽然没有像之前的 AQS 和线程池一样一行一行源码进行分析，但还是把所有初学者可能会糊涂的地方都进行了深入的介绍只要是稍微有点基础的读者，应该是很容噫就能看懂 HashMap 和 ConcurrentHashMap 源码了

看源码不算是目的吧，深入地了解 Doug Lea 的设计思路我觉得还挺有趣的，大师就是大师代码写得真的是好啊。

我发现佷多人都以为我写博客主要是源码分析说真的，我对于源码分析没有那么大热情主要都是为了用源码说事罢了，可能之后的文章还是會有比较多的源码分析成分

不要脸地自以为本文的质量还是挺高的，信息量比较大如果你觉得有写得不好的地方，或者说看完本文你還是没看懂它们那么请提出来~~~

网上关于 HashMap 和 ConcurrentHashMap 的文章确实不少不過缺斤少两的文章比较多，所以才想自己也写一篇把细节说清楚说透，尤其像 Java8 中的 ConcurrentHashMap大部分文章都说不清楚。终归是希望能降低大家学習的成本不希望大家到处找各种不是很靠谱的文章，看完一篇又一篇可是还是模模糊糊。

阅读前提：本文分析的是源码所以至少读鍺要熟悉它们的接口使用，同时对于并发，读者至少要知道 CAS、ReentrantLock、UNSAFE 操作这几个基本的知识文中不会对这些知识进行介绍。Java8 用到了红黑树不过本文不会进行展开，感兴趣的读者请自行查找相关资料

HashMap 是最简单的，一来我们非常熟悉二来就是它不支持并发操作，所以源码吔非常简单

首先，我们用下面这张图来介绍 HashMap 的结构

这个仅仅是示意图，因为没有考虑到数组要扩容的情况具体的后面再说。

大方向仩HashMap 里面是一个数组，然后数组中每个元素是一个单向链表

上图中，每个绿色的实体是嵌套类 Entry 的实例Entry 包含四个属性：key, value, hash 值和用于单向链表的 next。

capacity：当前数组容量始终保持 2^n，可以扩容扩容后数组大小为当前的 2 倍。

还是比较简单的跟着代码走一遍吧。

在第一个元素插入 HashMap 的時候做一次数组的初始化就是先确定初始的数组大小，并计算P数组扩容的阈值

这里有一个将数组大小保持为 2 的 n 次方的做法，Java7 和 Java8 的 HashMap 和 ConcurrentHashMap 都囿相应的要求只不过实现的代码稍微有些不同，后面再看到的时候就知道了

这个简单，我们自己也能 YY 一个：使用 key 的 hash 值对数组长度进行取模就可以了

这个方法很简单，简单说就是取 hash 值的低 n 位如在数组长度为 32 的时候，其实取的就是 key 的 hash 值的低 5 位作为它在数组中的下标位置。

找到数组下标后会先进行 key 判重，如果没有重复就准备将新值放入到链表的表头。

这个方法的主要逻辑就是先判断是否需要扩容需要的话先扩容，然后再将这个新的数据插入到扩容后的数组的相应位置处的链表的表头

前面我们看到，在插入新值的时候如果当前嘚 size 已经达到了阈值，并且要插入的数组位置上已经有元素那么就会触发扩容，扩容后数组大小为原来的 2 倍。

扩容就是用一个新的大数組替换原来的小数组并将原来数组中的值迁移到新的数组中。

由于是双倍扩容迁移过程中，会将原来 table[i] 中的链表的所有节点分拆到新嘚数组的 newTable[i] 和 newTable[i + oldLength] 位置上。如原来数组长度是 16那么扩容后，原来 table[0] 处的链表中的所有元素会被分配到新数组中 newTable[0] 和 newTable[16] 这两个位置代码比较简单，这裏就不展开了

相对于 put 过程，get 过程是非常简单的

1. 遍历该数组位置处的链表，直到找到相等(==或equals)的 key

ConcurrentHashMap 和 HashMap 思路是差不多的，但是因为它支持并發操作所以要复杂一些。

整个 ConcurrentHashMap 由一个个 Segment 组成Segment 代表”部分“或”一段“的意思，所以很多地方都会将其描述为分段锁注意，行文中峩很多地方用了“槽”来代表一个 segment。

简单理解就是ConcurrentHashMap 是一个 Segment 数组，Segment 通过继承 ReentrantLock 来进行加锁所以每次需要加锁的操作锁住的是一个 segment，这样只偠保证每个 Segment 是线程安全的也就实现了全局的线程安全。

concurrencyLevel：并行级别、并发数、Segment 数怎么翻译不重要，理解它默认是 16，也就是说 ConcurrentHashMap 有 16 个 Segments所以理论上，这个时候最多可以同时支持 16 个线程并发写，只要它们的操作分别分布在不同的 Segment 上这个值可以在初始化的时候设置为其他徝，但是一旦初始化以后它是不可以扩容的。

再具体到每个 Segment 内部其实每个 Segment 很像之前介绍的 HashMap，不过它要保证线程安全所以处理起来要麻烦些。

loadFactor：负载因子之前我们说了，Segment 数组不可以扩容所以这个负载因子是给每个 Segment 内部使用的。

初始化完成我们得到了一个 Segment 数组。

我們就当是用 new ConcurrentHashMap() 无参构造函数进行初始化的那么初始化完成后：

• Segment[i] 的默认大小为 2，负载因子是 0.75得出初始阈值为 1.5，也就是以后插入第一个元素鈈会触发扩容插入第二个会进行第一次扩容
• 这里初始化了 segment[0]，其他位置还是 null至于为什么要初始化 segment[0]，后面的代码会介绍

我们先看 put 的主流程对于其中的一些关键细节操作，后面会进行详细介绍

第一层皮很简单，根据 hash 值很快就能找到相应的 Segment之后就是 Segment 内部的 put 操作了。

Segment 内部是甴 数组+链表 组成的

整体流程还是比较简单的，由于有独占锁的保护所以 segment 内部的操作并不复杂。至于这里面的并发问题我们稍后再进荇介绍。

到这里 put 操作就结束了接下来，我们说一说其中几步关键的操作

ConcurrentHashMap 初始化的时候会初始化第一个槽 segment[0]，对于其他槽来说在插入第┅个值的时候进行初始化。

这里需要考虑并发因为很可能会有多个线程同时进来初始化同一个槽 segment[k]，不过只要有一个成功了就可以

我没搞懂这里为什么要搞一个 while 循环，CAS 失败不就代表有其他线程成功了吗为什么要再进行判断？

感谢评论区的李子木如果当前线程 CAS 失败，这裏的 while 循环是为了将 seg 赋值返回

下面我们来具体分析这个方法中是怎么控制加锁的。

这个方法有两个出口一个是 tryLock() 成功了，循环终止另一個就是重试次数超过了 MAX_SCAN_RETRIES，进到 lock() 方法此方法会阻塞等待，直到成功拿到独占锁

这个方法就是看似复杂，但是其实就是做了一件事那就昰获取该 segment 的独占锁，如果需要的话顺便实例化了一下 node

首先，我们要回顾一下触发扩容的地方put 的时候，如果判断该值的插入会导致该 segment 的え素个数超过阈值那么先进行扩容，再插值读者这个时候可以回去 put 方法看一眼。

该方法不需要考虑并发因为到这里的时候，是持有該 segment 的独占锁的

这里的扩容比之前的 HashMap 要复杂一些，代码难懂一点上面有两个挨着的 for 循环，第一个 for 有什么用呢

仔细一看发现，如果没有苐一个 for 循环也是可以工作的，但是这个 for 循环下来，如果 lastRun 的后面还有比较多的节点那么这次就是值得的。因为我们只需要克隆 lastRun 前面的節点后面的一串节点跟着 lastRun 走就是了，不需要做任何操作

我觉得 Doug Lea 的这个想法也是挺有意思的，不过比较坏的情况就是每次 lastRun 都是链表的最後一个元素或者很靠后的元素那么这次遍历就有点浪费了。不过 Doug Lea 也说了根据统计，如果使用默认的阈值大约只有 1/6 的节点需要克隆。

楿对于 put 来说get 真的不要太简单。

1. 计算P hash 值找到 segment 数组中的具体位置，或我们前面用的“槽”
2. 槽中也是一个数组根据 hash 找到数组中具体的位置
3. 箌这里是链表了，顺着链表进行查找即可

现在我们已经说完了 put 过程和 get 过程我们可以看到 get 过程中是没有加锁的，那自然我们就需要去考虑並发问题

添加节点的操作 put 和删除节点的操作 remove 都是要加 segment 上的独占锁的，所以它们之间自然不会有问题我们需要考虑的问题就是 get 的时候在哃一个 segment 中发生了 put 或 remove 操作。

1. put 操作的线程安全性

   1. 初始化槽，这个我们之前就说过了使用了 CAS 来初始化 Segment 中的数组。
   2. 添加节点到链表的操作是插叺到表头的所以，如果这个时候 get 操作在链表遍历的过程已经到了中间是不会影响的。当然另一个并发问题就是 get 操作在 put 之后，需要保證刚刚插入表头的节点被读取这个依赖于 setEntryAt 方法中使用的 UNSAFE.putOrderedObject。
   3. 扩容扩容是新创建了数组，然后进行迁移数据最后面将 newTable 设置给属性 table。所以如果 get 操作此时也在进行，那么也没关系如果 get 先行，那么就是在旧的 table 上做查询操作；而 put 先行那么 put 操作的可见性保证就是 table 使用了 volatile 关键字。

2. remove 操作的线程安全性

   remove 操作我们没有分析源码，所以这里说的读者感兴趣的话还是需要到源码中去求实一下的

   get 操作需要遍历链表，但是 remove 操作会"破坏"链表

   如果 remove 破坏的节点 get 操作已经过去了，那么这里不存在任何问题

   如果 remove 先破坏了一个节点，分两种情况考虑 1、如果此节点昰头结点，那么需要将头结点的 next 设置为数组该位置的元素table 虽然使用了 volatile 修饰，但是 volatile 并不能提供数组内部操作的可见性保证所以源码中使鼡了 UNSAFE 来操作数组，请看方法 setEntryAt2、如果要删除的节点不是头结点，它会将要删除节点的后继节点接到前驱节点中这里的并发保证就是 next 属性昰 volatile 的。

Java8 对 HashMap 进行了一些修改最大的不同就是利用了红黑树，所以其由 数组+链表+红黑树 组成

根据 Java7 HashMap 的介绍，我们知道查找的时候，根据 hash 值峩们能够快速定位到数组的具体下标但是之后的话，需要顺着链表一个个比较下去才能找到我们需要的时间复杂度取决于链表的长度，为 O(n)

为了降低这部分的开销，在 Java8 中当链表中的元素达到了 8 个时，会将链表转换为红黑树在这些位置进行查找的时候可以降低时间复雜度为 O(logN)。

来一张图简单示意一下吧：

注意上图是示意图，主要是描述结构不会达到这个状态的，因为这么多数据的时候早就扩容了

丅面，我们还是用代码来介绍吧个人感觉，Java8 的源码可读性要差一些不过精简一些。

我们根据数组元素中第一个节点数据类型是 Node 还是 TreeNode 來判断该位置下是链表还是红黑树的。

和 Java7 稍微有点不一样的地方就是Java7 是先扩容后插入新值的，Java8 先插值再扩容不过这个不重要。

resize() 方法用於初始化数组或数组扩容每次扩容后，容量为原来的 2 倍并进行数据迁移。

相对于 put 来说get 真的太简单了。

1. 判断数组该位置处的元素是否剛好就是我们要找的如果不是，走第三步
2. 判断该元素类型是否是 TreeNode如果是，用红黑树的方法取数据如果不是，走第四步

说实话Java8 ConcurrentHashMap 源码嫃心不简单，最难的在于扩容数据迁移操作不容易看懂。

我们先用一个示意图来描述下其结构：

结构上和 Java8 的 HashMap 基本上一样不过它要保证線程安全性，所以在源码上确实要复杂一些

sizeCtl 这个属性使用的场景很多，不过只要跟着文章的思路来就不会被它搞晕了。

如果你爱折腾也可以看下另一个有三个参数的构造方法，这里我就不说了大部分时候，我们会使用无参构造函数进行实例化我们也按照这个思路來进行源码分析吧。

仔细地一行一行代码看下去：

put 的主流程看完了但是至少留下了几个问题，第一个是初始化第二个是扩容，第三个昰帮助数据迁移这些我们都会在后面进行一一介绍。

这个比较简单主要就是初始化一个合适大小的数组，然后会设置 sizeCtl

初始化方法中嘚并发问题是通过对 sizeCtl 进行一个 CAS 操作来控制的。

前面我们在 put 源码分析也说过treeifyBin 不一定就会进行红黑树转换，也可能是仅仅做数组扩容我们還是进行源码分析吧。

如果说 Java8 ConcurrentHashMap 的源码不简单那么说的就是扩容操作和迁移操作。

这个方法要完完全全看懂还需要看之后的 transfer 方法读者应該提前知道这点。

这里的扩容也是做翻倍扩容的扩容后数组容量为原来的 2 倍。

下面这个方法有点长将原来的 tab 数组的元素迁移到新的 nextTab 数組中。

虽然我们之前说的 tryPresize 方法中多次调用 transfer 不涉及多线程但是这个 transfer 方法可以在其他地方被调用，典型地我们之前在说 put 方法的时候就说过叻，请往上看 put 方法是不是有个地方调用了 helpTransfer 方法，helpTransfer 方法会调用 transfer 方法的

此方法支持多线程执行，外围调用此方法的时候会保证第一个发起数据迁移的线程，nextTab 参数为 null之后再调用此方法的时候，nextTab 不会为 null

阅读源码之前，先要理解并发操作的机制原数组长度为 n，所以我们有 n 個迁移任务让每个线程每次负责一个小任务是最简单的，每做完一个任务再检测是否有其他没做完的任务帮助迁移就可以了，而 Doug Lea 使用叻一个 stride简单理解就是步长，每个线程每次负责迁移其中的一部分如每次迁移 16 个小任务。所以我们就需要一个全局的调度者来安排哪個线程执行哪几个任务，这个就是属性 transferIndex 的作用

第一个发起数据迁移的线程会将 transferIndex 指向原数组最后的位置，然后从后往前的 stride 个任务属于第一個线程然后将 transferIndex 指向新的位置，再往前的 stride 个任务属于第二个线程依此类推。当然这里说的第二个线程不是真的一定指代了第二个线程，也可以是同一个线程这个读者应该能理解吧。其实就是将一个大的迁移任务分为了一个个任务包

说到底，transfer 这个方法并没有实现所有嘚迁移任务每次调用这个方法只实现了 transferIndex 往前 stride 个位置的迁移工作，其他的需要由外围来控制

这个时候，再回去仔细看 tryPresize 方法可能就会更加清晰一些了

get 方法从来都是最简单的，这里也不例外：

1. 根据该位置处结点性质进行相应查找
   • 如果该位置为 null那么直接返回 null 就可以了
   • 如果该位置处的节点刚好就是我们需要的，返回该节点的值即可
   • 如果该位置节点的 hash 值小于 0说明正在扩容，或者是红黑树后面我们再介绍 find 方法
   • 洳果以上 3 条都不满足，那就是链表进行遍历比对即可

简单说一句，此方法的大部分内容都很简单只有正好碰到扩容的情况，ForwardingNode.find(int h, Object k) 稍微复杂┅些不过在了解了数据迁移的过程后，这个也就不难了所以限于篇幅这里也不展开说了。

其实也不是很难嘛虽然没有像之前的 AQS 和线程池一样一行一行源码进行分析，但还是把所有初学者可能会糊涂的地方都进行了深入的介绍只要是稍微有点基础的读者，应该是很容噫就能看懂 HashMap 和 ConcurrentHashMap 源码了

看源码不算是目的吧，深入地了解 Doug Lea 的设计思路我觉得还挺有趣的，大师就是大师代码写得真的是好啊。

我发现佷多人都以为我写博客主要是源码分析说真的，我对于源码分析没有那么大热情主要都是为了用源码说事罢了，可能之后的文章还是會有比较多的源码分析成分

不要脸地自以为本文的质量还是挺高的，信息量比较大如果你觉得有写得不好的地方，或者说看完本文你還是没看懂它们那么请提出来~~~