HashMap

HashMap 底层是基于 数组 + 链表 组成的，不过在 jdk1.7 和 1.8 中具体实现稍有 不同

其实1.7一个很明显需要优化的地方就是：

当 Hash 冲突严重时，在桶上形成的链表会变的越来越长，这样在查询时的效 率就会越来越低；时间复杂度为 O(N)。

因此 1.8 中重点优化了这个查询效率。

1.8 HashMap 结构图

• JDK 1.8 对 HashMap 进行了修改：

  最大的不同就是利用了红黑树，其由数组+链表+红黑树组成。

  JDK 1.7 中，查找元素时，根据 hash 值能够快速定位到数组的具体下标， 但之后需要顺着链表依次比较才能查找到需要的元素，时间复杂度取决于链 表的长度，为 O(N)。 为了降低这部分的开销，在 JDK 1.8 中，当链表中的元素超过 8 个以后，会 将链表转换为红黑树，在这些位置进行查找的时候可以降低时间复杂度为 O(logN)。

• JDK 1.8 使用 Node（1.7 为 Entry） 作为链表的数据结点，仍然包含 key， value，hash 和 next 四个属性。

  红黑树的情况使用的是 TreeNode。

• 根据数组元素中，第一个结点数据类型是 Node 还是 TreeNode 可以判断该位 置下是链表还是红黑树。

• 核心成员变量于 1.7 类似，增加了核心变量，如下表。

put步骤：

1. 判断当前桶是否为空，空的就需要初始化（resize 中会判断是否进行初始 化）。

2. 根据当前 key 的 hashcode 定位到具体的桶中并判断是否为空，为空表明没有 Hash 冲突就直接在当前位置创建一个新桶即可。

3. 如果当前桶有值（ Hash 冲突），那么就要比较当前桶中的 key、key 的 hashcode 与写入的 key 是否相等，相等就赋值给 e,在第 8 步的时候会统一进 行赋值及返回。

4. 如果当前桶为红黑树，那就要按照红黑树的方式写入数据。

5. 如果是个链表，就需要将当前的 key、value 封装成一个新节点写入到当前桶的 后面（形成链表）。

6. 接着判断当前链表的大小是否大于预设的阈值，大于时就要转换为红黑树。

7. 如果在遍历过程中找到 key 相同时直接退出遍历。

8. 如果 e != null 就相当于存在相同的 key,那就需要将值覆盖。

9. 后判断是否需要进行扩容.

get 方法看起来就要简单许多了。

• 首先将 key hash 之后取得所定位的桶。

• 如果桶为空则直接返回 null 。 否则判断桶的第一个位置(有可能是链表、红黑树)的 key 是否为查询的 key，是 就直接返回 value。

• 如果第一个不匹配，则判断它的下一个是红黑树还是链表。

• 红黑树就按照树的查找方式返回值。

• 不然就按照链表的方式遍历匹配返回值。

从这两个核心方法（get/put）可以看出 1.8 中对大链表做了优化，修改为红黑树之 后查询效率直接提高到了 O(logn)。 但是 HashMap 原有的问题也都存在，比如在并发场景下使用时容易出现死循环。

但是为什么呢？简单分析下。 看过上文的还记得在 HashMap 扩容的时候会调用 resize() 方法，就是这里的并 发操作容易在一个桶上形成环形链表；这样当获取一个不存在的 key 时，计算出的 index 正好是环形链表的下标就会出现死循环。 如下图：

HashTable

• HashTable 容器使用 synchronized来保证线程安全，但在线程竞争激烈的情况下 HashTable 的效 率非常低下。

  当一个线程访问 HashTable 的同步方法时，其他线程访问 HashTable 的同步方 法可能会进入阻塞或轮询状态。

• HashTable 容器在竞争激烈的并发环境下表现出效率低下的原因，是因为所有 访问它的线程都必须竞争同一把锁，假如容器里有多把锁，每一把锁用于锁容 器其中一部分数据，那么当多线程访问容器里不同数据段的数据时，线程间就 不会存在锁竞争，从而可以有效的提高并发访问效率，这就是 ConcurrentHashMap（JDK 1.7） 使用的 锁分段技术。

• ConcurrentHashMap 将数据分成一段一段的存储，然后给每一段数据配一把 锁，当一个线程占用锁访问其中一个段数据的时候，其他段的数据也能被其他 线程访问。

• 有些方法需要跨段，比如 size() 和 containsValue()，它们可能需要锁定整个表 而不仅仅是某个段，这需要按顺序锁定所有段，操作完毕后，又按顺序释放所 有段的锁。

• 按顺序 很重要，否则极有可能出现死锁，在 ConcurrentHashMap 内部，段数 组是 final 的，并且其成员变量实际也是 final 的，但是，仅仅是将数组声明为 final 的并不保证数组成员也是 final 的，需要实现上的保证。这可以确保不会 出现死锁，因为获得锁的顺序是固定的。

• HashTable 的迭代器是强一致性的，而 ConcurrentHashMap 是弱一致的。

• ConcurrentHashMap 的 get，clear，iterator 方法都是弱一致性的。

初识ConcurrentHashMap

Concurrent翻译过来是并发的意思，字面理解它的作用是处理并发情况的 HashMap。

通过前面的学习，我们知道多线程并发下 HashMap 是不安全的(如死循环)，更普遍 的是多线程并发下，由于堆内存对于各个线程是共享的，而 HashMap 的 put 方法 不是原子操作，假设Thread1先 put 值，然后 sleep 2秒(也可以是系统时间片切换失 去执行权)，在这2秒内值被Thread2改了，Thread1“醒来”再 get 的时候发现已经不 是原来的值了，这就容易出问题。

那么如何避免这种多线程出错的情况呢？

常规思路就是给 HashMap 的 put 方法加锁(synchronized)，保证同一个时刻只允 许一个线程拥有对 hashmap 有写的操作权限即可。然而假如线程1中操作耗时，其 他需要操作该 hashmap 的线程就需要在门口排队半天，严重影响用户体验， HashTable 就是这样子做的。

举个生活中的例子，很多银行除了存取钱，还支持存取贵重物品，贵重物品都放在 保险箱里，把 HashMap 和 HashTable 比作银行，结构：

把线程比作人，对应的情况如下：

多线程下用 HashMap 不确定性太高，有破产的风险，不能选；用 HashTable 不会 破产，但是用户体验不太好，那么怎样才能做到多人存取既不影响他人存值，又不 用排队呢？

有人提议搞个「银行者联盟」，多开几个像HashTable 这种「带锁」的银行就好 了，有多少人办理业务，就开多少个银行，一对一服务，这个区都是大老板，开银 行的成本都是小钱，于是「银行者联盟」成立了。 接下来的情况是这样的：比如用户A和用户B一起去银行存各自的项链，这个「银行 者联盟」操作后，然后对用户A说，1号银行现在没人你可以去那存，不用排队，然 后用户A就去1号银行存项链，1号银行把用户A接进门，马上拉闸，然后把用户A的 项链放在第x行第x个保险箱，等用户A办妥离开后，再开闸；对于用户B同理。此时 不管用户A和用户B在各自银行里面待多久都不会影响到彼此，不用担心自己的项链 被人偷换了。这就是ConcurrentHashMap的设计思路，用一个图来理解

从上图可以看出，此时锁的是对应的单个银行，而不是整个「银行者联盟」。分析 下这种设计的特点：

多个银行组成的「银行者联盟」 当有人来办理业务时，「银行者联盟」需要确定这个人去哪个银行 当此人去到指定银行办理业务后，该银行上锁，其他人不能同时执行修改操作，直 到此人离开后解锁.

ConcurrentHashMap源码解析

ConcurrentHashMap 同样也分为 1.7 、1.8 版，两者在实现上略有不同。 先来看看 1.7 的实现，下面是结构图：

如图所示，是由 Segment 数组、HashEntry 组成，和 HashMap 一样，仍然是数组 加链表。主要是通过分段锁实现的。

关于分段锁

段Segment继承了重入锁ReentrantLock，有了锁的功能，每个锁控制的是一段， 当每个Segment越来越大时，锁的粒度就变得有些大了。

• 分段锁的优势在于保证在操作不同段 map 的时候可以并发执行，操作同段 map 的时候，进行锁的竞争和等待。这相对于直接对整个map同步 synchronized是有优势的。

• 缺点在于分成很多段时会比较浪费内存空间(不连续，碎片化); 操作map时竞争 同一个分段锁的概率非常小时，分段锁反而会造成更新等操作的长时间等待; 当 某个段很大时，分段锁的性能会下降。

1.7 已经解决了并发问题，并且能支持 N 个 Segment 这么多次数的并发，但依然存 在 HashMap 在 1.7 版本中的问题。

那就是查询遍历链表效率太低。

因此 1.8 做了一些数据结构上的调整。 首先来看下底层的组成结构：

其实和 1.8 HashMap 结构类似，当链表节点数超过指定阈值的话，也是会转换成红 黑树的，大体结构也是一样的。 那么 JDK 1.8 ConcurrentHashMap 到底是如何实现线程安全的？ 答案:其中抛弃了原有的Segment 分段锁，而采用了 CAS + synchronized 来保证 并发安全性。（cas：比较并替换）

**① 基本组成 **

• 抛弃了 JDK 1.7 中原有的 Segment 分段锁，而采用了 CAS + synchronized 来 保证并发安全性。

• 将JDK 1.7 中存放数据的 HashEntry 改为 Node，但作用是相同的。、 我们来看看 ConcurrentHashMap 的几个重要属性.

重要组成元素

Node：链表中的元素为 Node 对象。他是链表上的一个节点，内部存储了 key、 value 值，以及他的下一 个节点的引用。这样一系列的 Node 就串成一串，组成一 个链表。

ForwardingNode：当进行扩容时，要把链表迁移到新的哈希表，在做这个操作 时，会在把数组中的头节点替换为 ForwardingNode 对象。ForwardingNode 中不 保存 key 和 value，只保存了扩容后哈希表 （nextTable）的引用。此时查找相应 node 时，需要去 nextTable 中查找。

TreeBin：当链表转为红黑树后，数组中保存的引用为 TreeBin，TreeBin 内部不保 存 key/value，他保存了 TreeNode 的 list 以及红黑树 root。

TreeNode：红黑树的节点。

**② put 方法过程 **

存储结构定义了容器的 “形状”，那容器内的东西按照什么规则来放呢？换句话讲， 某个 key 是按 照什么逻辑放入容器的对应位置呢？

我们假设要存入的 key 为对象 x，这个过程如下 ：

1、通过对象 x 的 hashCode () 方法获取其 hashCode；

2、将 hashCode 映射到数组的某个位置上；

3、把该元素存储到该位置的链表中。

put 方法用来把一个键值对存储到 map 中。代码如下： 实际调用的是 putVal 方 法，第三个参数传入 false，控制 key 存在时覆盖原来的值。

请先看完代码注释，有个大致的了解，然后我们更加详细的学习一下：

1. 判断存储的 key、value 是否为空，若为空，则抛出异常，否则，进入步骤 2。

2. 计算 key 的 hash 值，随后进入自旋，该自旋可以确保成功插入数据，若 table 表为空或者长度为 0，则初始化 table 表，否则，进入步骤 3。

3. 根据 key 的 hash 值取出 table 表中的结点元素，若取出的结点为空（该桶为 空），则使用 CAS 将 key、value、hash 值生成的结点放入桶中。否则，进入 步骤 4。

4. 若该结点的的 hash 值为 MOVED（-1），则对该桶中的结点进行转移，否则， 进入步骤 5。 5 . 对桶中的第一个结点（即 table 表中的结点）进行加锁，对该桶进行遍历，桶中 的结点的 hash 值与 key 值与给定的 hash 值和 key 值相等，则根据标识选择是 否进行更新操作（用给定的 value 值替换该结点的 value 值），若遍历完桶仍 没有找到 hash 值与 key 值和指定的 hash 值与 key 值相等的结点，则直接新生 一个结点并赋值为之前后一个结点的下一个结点。进入步骤 6。

5. 若 binCount 值达到红黑树转化的阈值，则将桶中的结构转化为红黑树存储， 后，增加 binCount 的值。

6. 如果桶中的第一个元素的 hash 值大于 0，说明是链表结构，则对链表插入或者 更新。

7. 如果桶中的第一个元素是 TreeBin，说明是红黑树结构，则按照红黑树的方式进 行插入或者更新。

8. 在锁的保护下，插入或者更新完毕后，如果是链表结构，需要判断链表中元素 的数量是否超过 8（默认），一旦超过，就需要考虑进行数组扩容，或者是链表 转红黑树。

扩容

什么时候会扩容？

1. 使用put()添加元素时会调用addCount()，内部检查sizeCtl看是否需要扩容。

2. tryPresize()被调用，此方法被调用有两个调用点：

链表转红黑树(put()时检查)时如果table容量小于64(MIN_TREEIFY_CAPACITY)，则会 触发扩容。 调用putAll()之类一次性加入大量元素，会触发扩容。 addCount() addCount()与tryPresize()实现很相似，我们先以addCount()分析下扩容逻辑：

**1.链表转红黑树 **

首先我们要理解为什么 Map 需要扩容，这是因为我们采用哈希表存储数据，当固定 大小的哈希表存 储数据越来越多时，链表长度会越来越长，这会造成 put 和 get 的 性能下降。此时我们希望哈希表中多一些桶位，预防链表继续堆积的更长。

ConcurrentHashMap 有链表转红黑树的操作，以提高查找的速度，红黑树时间复 杂度为 O (logn)，而链表是 O (n/2)，因此只在 O (logn)<O (n/2) 时才会进行转换， 也就是以 8 作为分界点。

接下来我们分析 treeifyBin 方法代码，这个代码中会选择是把此时保存数据所在的 链表转为红黑树，还是对整个哈希表扩容。 treeifyBin 不一定就会进行红黑树转换，也可能是仅仅做数组扩容。

构造完TreeBin这个空节点之后，就开始构造红黑树，首先是第一个节点，左右 子节点设置为空，作为红黑树的root节点，设置为黑色，父节点为空。

然后在每次添加完一个节点之后，都会调用balanceInsertion方法来维持这是一 个红黑树的属性和平衡性。红黑树所有操作的复杂度都是O(logn)，所以当元素量比 较大的时候，效率也很高。

**数组扩容 **

我们大致了解了 ConcurrentHashMap 的存储结构，那么我们思考一个问题，当数 组中保存的链表越来越多，那么再存储进来的元素大概率会插入到现有的链表中， 而不是使用数组中剩下的空位。 这样会造成数组中保存的链表越来越长，由此导致 哈希表查找速度下降，从 O (1) 慢慢趋近于链表 的时间复杂度 O (n/2)，这显然违背 了哈希表的初衷。 所以 ConcurrentHashMap 会做一个操作， 称为扩容。也就是把数组长度变大，增 加更多的空位出来，终目的就是预防链表过长，这样查找的时间复杂度才会趋向于 O (1)。扩容的操作并不会在数组没有空位时才进行，因为在桶位快满时， 新保存元 素更大的概率会命中已经使用的位置，那么可能后几个桶位很难被使用，而链表却 越来 越长了。ConcurrentHashMap 会在更合适的时机进行扩容，通常是在数组中 75% 的位置被使用 时。 其实以上内容和 HashMap 类似，ConcurrentHashMap 此外提供了线程安全的保 证，它主要是通 过 CAS 和 Synchronized 关键字来实现，我们在源码分析中再详细 来看。

我们做一下总结：

1、ConcurrentHashMap 采用数组 + 链表 + 红黑树的存储结构；

2、存入的 Key 值通过自己的 hashCode 映射到数组的相应位置；

3、ConcurrentHashMap 为保障查询效率，在特定的时候会对数据增加长度，这个 操作叫做扩容；

4、当链表长度增加到 8 时，可能会触发链表转为红黑树（数组长度如果小于 64， 优先扩容，具体 看后面源码分析）。

接下来，我们的源码分析就从 ConcurrentHashMap 的构成、保存元素、哈希算 法、扩容、查找数 据这几个方面来进行 扩容后数组容量为原来的 2 倍。

**数据迁移（ 扩容时的线程安全） **

ConcurrentHashMap 的扩容时机和 HashMap 相同，都是在 put 方法的后一步 检查是否需要扩容，如果需要则进行扩容，但两者扩容的过程完全不同， ConcurrentHashMap 扩容的方法叫做 transfer，从 put 方法的 addCount 方法进 去，就能找到 transfer 方法，transfer 方法的主要思路是：

1. 首先需要把老数组的值全部拷贝到扩容之后的新数组上，先从数组的队尾开始 拷贝；

2. 拷贝数组的槽点时，先把原数组槽点锁住，保证原数组槽点不能操作，成功拷 贝到新数组时，把 原数组槽点赋值为转移节点；

3. 这时如果有新数据正好需要 put 到此槽点时，发现槽点为转移节点，就会一直 等待，所以在扩容完成之前，该槽点对应的数据是不会发生变化的；

4. 从数组的尾部拷贝到头部，每拷贝成功一次，就把原数组中的节点设置成转移 节点；

5. 直到所有数组数据都拷贝到新数组时，直接把新数组整个赋值给数组容器，拷 贝完成

putTreeVal()与此方法遍历方式类似不再介绍。

 ④ get 方法过程 ConcurrentHashMap 读的话，就比较简单，先获取数组的下标，然后通过判断数 组下标的 key 是 否和我们的 key 相等，相等的话直接返回，如果下标的槽点是链表 或红黑树的话，分别调用相应的 查找数据的方法，整体思路和 HashMap 很像，源 码如下：

1. 计算 hash 值。

2. 根据 hash 值找到数组对应位置: (n – 1) & h。

3. 根据该位置处结点性质进行相应查找。

4. 如果该位置为 null，那么直接返回 null。 如果该位置处的结点刚好就是需要的，返回该结点的值即可。

5. 如果该位置结点的 hash 值小于 0，说明正在扩容，或者是红黑树。

6. 如果以上 3 条都不满足，那就是链表，进行遍历比对即可。

** 初始化数组 **

数组初始化时，首先通过自旋来保证一定可以初始化成功，然后通过 CAS 设置 SIZECTL 变量的值，来保证同一时刻只能有一个线程对数组进行初始化，CAS 成功 之后，还会再次判断当前数组是否已经初始化完成，如果已经初始化完成，就不会 再次初始化，通过自旋 + CAS + 双重 check 等 手段保证了数组初始化时的线程安 全，源码如下：

里面有个关键的值 sizeCtl，这个值有多个含义。 1、-1 代表有线程正在创建 table； 2、-N 代表有 N-1 个线程正在复制 table； 3、在 table 被初始化前，代表 根据构造函数传入的值计算出的应被初始化的大小； 4、在 table 被初始化后，则被 设置为 table 大小 的 75%，代表 table 的容量（数组容量）。 initTable 中使用到 1 和 4，2 和 3 在其它方法中会有使用。下面我们可以先看下 ConcurrentHashMap 的构造方法，里面会使用上面的 3

最后来回顾总结下HashMap和ConcurrentHashMap对比 ConcurrentHashMap 和 HashMap 两者的相同之处：

1.数组、链表结构几乎相同，所以底层对数据结构的操作思路是相同的（只是思路 相同，底层实现 不同）；

2.都实现了 Map 接口，继承了 AbstractMap 抽象类，所以大多数的方法也都是相 同的， HashMap 有的方法，ConcurrentHashMap 几乎都有，所以当我们需要从 HashMap 切换到 ConcurrentHashMap 时，无需关心两者之间的兼容问题

不同点：

1.红黑树结构略有不同，HashMap 的红黑树中的节点叫做 TreeNode，TreeNode 不仅仅有属 性，还维护着红黑树的结构，比如说查找，新增等等； ConcurrentHashMap 中红黑树被拆分成 两块，TreeNode 仅仅维护的属性和查找 功能，新增了 TreeBin，来维护红黑树结构，并负责根 节点的加锁和解锁；

2.新增 ForwardingNode （转移）节点，扩容的时候会使用到，通过使用该节点， 来保证扩容时的线程安全。