HashMap 与 ConcurrentHashMap 原理总结

一、HashMap原理总结：

1、什么是HashMap：

（1）HashMap 是基于 Map 接口的非同步实现，线程不安全，是为了快速存取而设计的；它采用 key-value 键值对的形式存放元素（并封装成 Node 对象），允许使用 null 键和 null 值，但只允许存在一个键为 null，并且存放在 Node[0] 的位置，不过允许存在多个 value 为 null 的情况。

（2）在 JDK7 及之前的版本，HashMap 的数据结构可以看成“数组+链表”，在 JDK8 及之后的版本，数据结构可以看成”数组+链表+红黑树”，也就是说 HashMap  底层采用数组实现，数组的每个位置都存储一个单向链表，当链表的长度超过一定的阈值时，就会转换成红黑树。转换的目的是当链表中元素较多时，也能保证HashMap的存取效率（备注：链表转为红黑树只有在数组的长度大于等于64才会触发）

（3）HashMap 有两个影响性能的关键参数：“初始容量”和“加载因子”：

• 容量 capacity：就是哈希表中数组的数量，默认初始容量是16，容量必须是2的N次幂，这是为了提高计算机的执行效率。
• 加载因子 loadfactor：在 HashMap 扩容之前，容量可以达到多满的程度，默认值为 0.75
• 扩容阈值 threshold = capacity * loadfactor

（4）采用 Fail-Fast 机制，底层通过一个 modCount 值记录修改的次数，对 HashMap 的修改操作都会增加这个值。迭代器在初始过程中会将这个值赋给 exceptedModCount ，在迭代的过程中，如果发现 modCount 和 exceptedModCount 的值不一致，代表有其他线程修改了Map，就立刻抛出异常。

2、HashMap 的 put() 方法添加元素的过程：

（1）重新计算 hash 值：

拿到 key 的 hashcode 值之后，调用 hash() 方法重新计算 hash 值，防止质量低下的 hashCode() 函数出现，从而使 hash 值的分布尽量均匀。

JDK8 及之后的版本，对 hash() 方法进行了优化，重新计算 hash 值时，让 hashCode 的高16位参与异或运算，目的是即使 table 数组的长度较小，在计算元素存储位置时，也能让高位也参与运算。

（key == null）? 0 : ( h = key.hashcode()) ^ (h >>> 16)

（2）计算元素存放在数组中的哪个位置：

将重新计算出来的 hash 值与 (tablel.length-1) 进行位与&运算，得出元素应该放入数组的哪个位置。

为什么 HashMap 的底层数组长度总是2的n次方幂？因为当 length 为2的n次方时，h & (length – 1) 就相当于对 length 取模，而且速度比直接取模要快得多，二者等价不等效，这是HashMap在性能上的一个优化

（3）将 key-value 添加到数组中：

① 如果计算出的数组位置上为空，那么直接将这个元素插入放到该位置中。

② 如果数组该位置上已经存在链表，则使用 equals() 比较链表上是否存在 key 相同的节点，如果为true，则替换原元素；如果不存在，则在链表的尾部插入新节点（Jdk1.7及以前的版本使用的头插法）

③ 如果插入元素后，如果链表的节点数是否超过8个，则调用 treeifyBin() 将链表节点转为红黑树节点。

④ 最后判断 HashMap 总容量是否超过阈值 threshold，则调用 resize() 方法进行扩容，扩容后数组的长度变成原来的2倍。

 在 HashMap 中，当发生hash冲突时，解决方式是采用拉链法，也就是将所有哈希值相同的记录都放在同一个链表中，除此之外，解决hash冲突的方式有：

• 开放地址法（线性探测再散列、二次探测再散列、伪随机探测再散列）：当冲突发生时，在散列表中形成一个探测序列，沿此序列逐个单元地查找，直到找到给定的关键字，或者碰到一个开放的地址为止（即该地址单元为空）。如果是插入的情况，在探查到开放的地址，则可将待插入的新结点存入该地址单元，如果是查找的情况，探查到开放的地址则表明表中无待查的关键字，即查找失败。
• 再哈希法：产生冲突时，使用另外的哈希函数计算出一个新的哈希地址、直到冲突不再发生
• 建立一个公共溢出区：把冲突的记录都放在另一个存储空间，不放在表里面。

3、HashMap扩容的过程：

（1）重新建立一个新的数组，长度为原数组的两倍；

（2）遍历旧数组的每个数据，重新计算每个元素在新数组中的存储位置。使用节点的hash值与旧数组长度进行位与运算，如果运算结果为0，表示元素在新数组中的位置不变；否则，则在新数组中的位置下标=原位置+原数组长度。

（3）将旧数组上的每个数据使用尾插法逐个转移到新数组中，并重新设置扩容阈值。

问题：为什么扩容时节点重 hash 只可能分布在原索引位置或者 原索引长度+oldCap 位置呢？换句话说，扩容时使用节点的hash值跟oldCap进行位与运算，以此决定将节点分布到原索引位置或者原索引+oldCap位置上的原理是什么呢？

假设老表的容量为16，则新表容量为16*2=32，假设节点1的hash值为 0000 0000 0000 0000 0000 1111 0000 1010，节点2的hash值为 0000 0000 0000 0000 0000 1111 0001 1010。

那么节点1和节点2在老表的索引位置计算如下图计算1，由于老表的长度限制，节点1和节点2的索引位置只取决于节点hash值的最后4位。再看计算2，计算2为元素在新表中的索引计算，可以看出如果两个节点在老表的索引位置相同，则新表的索引位置只取决于节点hash值倒数第5位的值，而此位置的值刚好为老表的容量值16，此时节点在新表的索引位置只有两种情况：原索引位置和 原索引+oldCap位置（在此例中即为10和10+16=26）。由于结果只取决于节点hash值的倒数第5位，而此位置的值刚好为老表的容量值16，因此此时新表的索引位置的计算可以替换为计算3，直接使用节点的hash值与老表的容量16进行位于运算，如果结果为0则该节点在新表的索引位置为原索引位置，否则该节点在新表的索引位置为 原索引+ oldCap 位置。

4、HashMap 链表转换成红黑树：

当数组中某个位置的节点达到8个时，会触发 treeifyBin() 方法将链表节点（Node）转红黑树节点（TreeNode，间接继承Node），转成红黑树节点后，其实链表的结构还存在，通过next属性维持，红黑树节点在进行操作时都会维护链表的结构，并不是转为红黑树节点后，链表结构就不存在了。当数组中某个位置的节点在移除后达到6个时，并且该索引位置的节点为红黑树节点，会触发 untreeify() 将红黑树节点转化成链表节点。

HashMap 在进行插入和删除时有可能会触发红黑树的插入平衡调整（balanceInsertion方法）或删除平衡调整（balanceDeletion ）方法，调整的方式主要有以下手段：左旋转（rotateLeft方法）、右旋转（rotateRight方法）、改变节点颜色（x.red = false、x.red = true），进行调整的原因是为了维持红黑树的数据结构。

当链表长过长时会转换成红黑树，那能不能使用AVL树替代呢？

AVL树是完全平衡二叉树，要求每个结点的左右子树的高度之差的绝对值最多为1，而红黑树通过适当的放低该条件（红黑树限制从根到叶子的最长的可能路径不多于最短的可能路径的两倍长，结果是这个树大致上是平衡的），以此来减少插入/删除时的平衡调整耗时，从而获取更好的性能，虽然会导致红黑树的查询会比AVL稍慢，但相比插入/删除时获取的时间，这个付出在大多数情况下显然是值得的。

5、HashMap 在 JDK7 和 JDK8 有哪些区别?

① 数据结构：在 JDK7 及之前的版本，HashMap 的数据结构可以看成“数组+链表”，在 JDK8 及之后的版本，数据结构可以看成”数组+链表+红黑树”，当链表的长度超过8时，链表就会转换成红黑树

② 对数据重哈希：JDK8 及之后的版本，对 hash() 方法进行了优化，重新计算 hash 值时，让 hashCode 的高16位参与异或运算，目的是在 table 的 length较小的时候，在进行计算元素存储位置时，也让高位也参与运算。

③ 在 JDK7 及之前的版本，在添加元素的时候，采用头插法，所以在扩容的时候，会导致之前元素相对位置倒置了，在多线程环境下扩容可能造成环形链表而导致死循环的问题。DK1.8之后使用的是尾插法，扩容是不会改变元素的相对位置

④ 扩容时重新计算元素的存储位置的方式：JDK7 及之前的版本重新计算存储位置是直接使用 hash & (table.length-1)；JDK8 使用节点的hash值与旧数组长度进行位与运算，如果运算结果为0，表示元素在新数组中的位置不变；否则，则在新数组中的位置下标=原位置+原数组长度。

6、线程不安全的体现？如何变成线程安全：

无论在 JDK7 还是 JDK8 的版本中，HashMap 都是线程不安全的，HashMap 的线程不安全主要体现在以下两个方面：

• 在JDK7及以前的版本，表现为在多线程环境下进行扩容，由于采用头插法，位于同一索引位置的节点顺序会反掉，导致可能出现死循环的情况
• 在JDK8及以后的版本，表现为在多线程环境下添加元素，可能会出现数据丢失的情况

如果想使用线程安全的 Map 容器，可以使用以下几种方式：

（1）使用线程安全的 Hashtable，它底层的每个方法都使用了 synchronized 保证线程同步，所以每次都锁住整张表，在性能方面会相对比较低。

除了线程安全性方面，Hashtable 和 HashMap 的不同之处还有：

• 继承的父类：两者都实现了 Map 接口，但 HashMap 继承自 AbstractMap 类，而 Hashtable 继承自 Dictionary 类
• 遍历方式：HashMap 仅支持 Iterator 的遍历方式，但 Hashtable 实现了 Enumeration 接口，所以支持Iterator和Enumeration两种遍历方式
• 使用方式：HashMap 允许 null 键和 null 值，Hashtable 不允许 null  键和 null 值
• 数据结构：HashMap 底层使用“数组+链表+红黑树”，Hashtable 底层使用“数组+链表”
• 初始容量及扩容方式：HashMap 的默认初始容量为16，每次扩容为原来的2倍；Hashtable 默认初始容量为11，每次扩容为原来的2倍+1。
• 元素的hash值：HashMap的hash值是重新计算过的，Hashtable直接使用Object的hashCode；

之所以会出现初始容量以及元素hash值计算方式的不同，是因为 HashMap 和 Hashtable 设计时的侧重点不同。Hashtable 的侧重点是哈希结果更加均匀，使得哈希冲突减少，当哈希表的大小为素数时，简单的取模哈希的结果会更加均匀。而 HashMap 则更加关注哈希的计算效率问题，在取模计算时，如果模数是2的幂，那么我们可以直接使用位运算来得到结果，效率要大大高于做除法。

有关 Hashtable 的内容，可以详细阅读：Hashtable原理详解（JDK1.8）

（2）使用Collections.synchronizedMap()方法来获取一个线程安全的集合，底层原理是使用synchronized来保证线程同步。

（3）使用 ConcurrentHashMap 集合。

JDK7 版本的 HahsMap 源码解析：https://blog.csdn.net/a745233700/article/details/83108880

JDK8 版本的 HahsMap 源码解析：https://blog.csdn.net/a745233700/article/details/85126716

二、ConcurrentHashMap 原理（JDK8）：

1、ConcurrentHashMap 的实现原理：

在 JDK8 及以上的版本中，ConcurrentHashMap 的底层数据结构依然采用“数组+链表+红黑树”，但是在实现线程安全性方面，抛弃了 JDK7 版本的 Segment分段锁的概念，而是采用了 synchronized + CAS 算法来保证线程安全。在ConcurrentHashMap中，大量使用 Unsafe.compareAndSwapXXX 的方法，这类方法是利用一个CAS算法实现无锁化的修改值操作，可以大大减少使用加锁造成的性能消耗。这个算法的基本思想就是不断比较当前内存中的变量值和你预期变量值是否相等，如果相等，则接受修改的值，否则拒绝你的而操作。因为当前线程中的值已经不是最新的值，你的修改很可能会覆盖掉其他线程修改的结果。

2、扩容方法 transfer()：

ConcurrentHashMap 为了减少扩容带来的时间影响，在扩容过程中没有进行加锁，并且支持多线程进行扩容操作。在扩容过程中主要使用 sizeCtl 和 transferIndex 这两个属性来协调多线程之间的并发操作，并且在扩容过程中大部分数据可以做到访问不阻塞，整个扩容操作分为以下几个步骤：

2.1、根据 CPU 核数和数组长度，计算每个线程应该处理的桶数量，如果CPU为单核，则使用一个线程处理所有桶

2.2、根据当前数组长度n，新建一个两倍长度的数组 nextTable（该这个步骤是单线程执行的）

2.3、将原来 table 中的元素复制到 nextTable 中，这里允许多线程进行操作，具体操作步骤如下：

（1）初始化 ForwardingNode 对象，充当占位节点，hash 值为 -1，该占位对象存在时表示集合正在扩容状态。

ForwardingNode 的 key、value、next 属性均为 null ，nextTable 属性指向扩容后的数组，它的作用主要有以下两个：

• 占位作用，用于标识数组该位置的桶已经迁移完毕
• 作为一个转发的作用，扩容期间如果遇到查询操作，遇到转发节点，会把该查询操作转发到新的数组上去，不会阻塞查询操作。

（2）通过 for 循环从右往左依次迁移当前线程所负责数组：

① 如果当前桶没有元素，则直接通过 CAS 放置一个 ForwardingNode 占位对象，以便查询操作的转发和标识当前位置已经被处理过。

② 如果线程遍历到节点的 hash 值为 MOVE，也就是 -1（即 ForwardingNode 节点），则直接跳过，继续处理下一个桶中的节点

③ 如果不满足上面两种情况，则直接给当前桶节点加上 synchronized 锁，然后重新计算该桶的元素在新数组中的应该存放的位置，并进行数据迁移。重计算节点的存放位置时，通过 CAS 把低位节点 lowNode 设置到新数组的 i 位置，高位节点 highNode 设置到 i+n 的位置（i 表示在原数组的位置，n表示原数组的长度）

• 如果数组中的节点是链表结构，则顺序遍历链表并使用头插法进行构造新链表
• 如果数组中的节点是红黑树结构，则for循环以链表方式遍历整棵红黑树，使用尾插法拼接

④ 当前桶位置的数据迁移完成后，将 ForwardingNode 占位符对象设置到当前桶位置上，表示该位置已经被处理了

2.4、每当一条线程扩容结束就会更新一次 sizeCtl 的值，进行减 1 操作，当最后一条线程扩容结束后，需要重新检查一遍数组，防止有遗漏未成功迁移的桶。扩容结束后，将 nextTable 设置为 null，表示扩容已结束，将 table 指向新数组，sizeCtl 设置为扩容阈值。

sizeCtl：是一个控制标识符，在不同的地方有不同用途，它不同的取值不同也代表不同的含义。在扩容时，它代表的是当前并发扩容的线程数量

• 负数代表正在进行初始化或扩容操作：-1代表正在初始化，-N 表示有N-1个线程正在进行扩容操作
• 正数或0代表hash表还没有被初始化或下一次进行扩容的大小，这一点类似于扩容阈值的概念。

3、put() 方法的 helpTransfer() 协助扩容：

put() 在多线程情况下可能有以下两种情况：

• 如果检测到 ConcurrentHashMap 正在进行扩容操作，也就是当前桶位置上被插入了 ForwardingNode 节点，那么当前线程也要协助进行扩容，协助扩容时会调用 helpTransfer() 方法，当方法被调用的时候，当前 ConcurrentHashMap 一定已经有了 nextTable 对象，首先拿到这个 nextTable 对象，调用transfer方法。
• 如果检测到要插入的节点是非空且不是 ForwardingNode  节点，就对这个节点加锁，这样就保证了线程安全。尽管这个有一些影响效率，但是还是会比hashTable 的 synchronized 要好得多。

有关扩容的源码解析可以阅读该文章：https://blog.csdn.net/ZOKEKAI/article/details/90051567

三、ConcurrentHashMap 原理（JDK7）：

在第二部分我们提到 JDK8 和 JDK7 中 ConcurrentHashMap 的设计是不一样的，那么下面我们就简单介绍一下 JDK7 中 ConcurrentHashMap 的实现：

1、ConcurrentHashMap实现的原理：

在 JDK7 中，ConcurrentHashMap 使用“分段锁”机制实现线程安全，数据结构可以看成是”Segment数组+HashEntry数组+链表”，一个 ConcurrentHashMap 实例中包含若干个 Segment 实例组成的数组，每个 Segment 实例又包含由若干个桶，每个桶中都是由若干个 HashEntry 对象链接起来的链表。

因为Segment 类继承 ReentrantLock 类，所以能充当锁的角色，通过 segment 段将 ConcurrentHashMap 划分为不同的部分，就可以使用不同的锁来控制对哈希表不同部分的修改，从而允许多个写操作并发进行，默认支持 16 个线程执行并发写操作，及任意数量线程的读操作。

 2、ConcurrentHashMap 的 put() 方法添加元素的过程：

（1）对 key 值进行重哈希，并使用重哈希的结果与 segmentFor() 方法， 计算出元素具体分到哪个 segment 中。插入元素前，先使用 lock() 对该 segment 加锁，之后再使用头插法插入元素。如果其他线程经过计算也是放在这个 segment 下，则需要先获取锁，如果计算得出放在其他的 segment，则正常执行，不会影响效率，以此实现线程安全，这样就能够保证只要多个修改操作不发生在同一个 segment  时，它们就可以并发进行。

（2）在将元素插入到 segment 前，会检查本次插入会不会导致 segment 中元素的数量超过阈值，如果会，那么就先对 segment 进行扩容和重哈希操作，然后再进行插入。而重哈希操作，实际上是对 ConcurrentHashMap 的某个 segment 的重哈希，因此 ConcurrentHashMap 的每个 segment 段所包含的桶位也就不尽相同。

如果元素的 hash 值与原数组长度进行位与运算，得到的结果为0，那么元素在新桶的序号就是和原桶的序号是相等的；否则元素在新桶的序号就是原桶的序号加上原数组的长度

3、ConcurrentHashMap 读操作为什么不需要加锁？

（1）在 HashEntry 类中，key，hash 和 next 域都被声明为 final 的，value 域被 volatile 所修饰，因此 HashEntry 对象几乎是不可变的，通过 HashEntry 对象的不变性来降低读操作对加锁的需求

next 域被声明为 final，意味着不能从hash链的中间或尾部添加或删除节点，因为这需要修改 next 引用值，因此所有的节点的修改只能从头部开始。但是对于 remove 操作，需要将要删除节点的前面所有节点整个复制一遍，最后一个节点指向要删除结点的下一个结点。

（2）用 volatile 变量协调读写线程间的内存可见性；

（3）若读时发生指令重排序现象（也就是读到 value 域的值为 null 的时候），则加锁重读；

4、ConcurrentHashMap 的跨端操作：

ConcurrentHashMap 的跨段操作：比如 size() 计算集合中元素的总个数。首先为了并发性的考虑，ConcurrentHashMap 并没有使用全局计数器，而是分别在每个 segment 中使用一个 volatile 修饰的计数器count，这样当需要更新计数器时，不用锁定整个 ConcurrentHashMap。而 size() 在统计时，是先尝试 RETRIES_BEFORE_LOCK 次（默认是两次）通过不锁住 Segment 的方式来统计各个 Segment 大小，如果统计的过程中，容器的count发生了变化，则再采用对所有 segment 段加锁的方式来统计所有Segment的大小。

JDK7 版本的 ConcurrentHashMap 源码解析：https://blog.csdn.net/a745233700/article/details/83120464

JDK8 版本的 ConcurrentHashMap 源码解析：https://blog.csdn.net/a745233700/article/details/83123359