当前位置：文江博客文章教程详情

Java HashMap 详细介绍

发布于 2025-04-15 17:55:24 字数 20340 浏览 10 评论 0

HashMap

什么是 HashMap？

基于哈希表的 Map 接口的实现。
HashMap 是一个散列表，它存储的内容是键值对(key-value) 映射。
HashMap 继承于 AbstractMap，实现了 Map、Cloneable、java.io.Serializable 接口。
HashMap 的实现不是同步的，这意味着它不是线程安全的。它的 key、value 都可以为 null。此外，HashMap 中的映射不是有序的。

HashMap 的工作原理？

HashMap 是基于 hashing 的原理，我们使用 put(key, value) 存储对象到 HashMap 中，使用 get(key) 从 HashMap 中获取对象。
- Put: 当我们往 hashmap 中 put 元素的时候，先根据 key 的 hash 值得到这个元素在数组中的位置（即下标），如果下标对应的链表为空，则直接把键值对作为链表头节点，如果不为空，发生哈希冲突，则 equals 方法在对应位置的链表中找到需要的元素，有就把 value 替换，没有那么在同一个位子上的元素将以链表的形式存放，新加入的放在链头，最先加入的放在链尾。（JDK1.7 之所以放在头节点，是因为 HashMap 的发明者认为后插入的 Entry 被查找的可能性更大。）
- Get: 从 hashmap 中 get 元素时，首先计算 key 的 hashcode，找到数组中对应位置的某一元素，然后通过 key 的 equals 方法在对应位置的链表中找到需要的元素。

怎样计算 key 在数组中的位置 (hash 算法)？根据 HashCode 计算数组下标？

我们当然希望这个 hashmap 里面的元素位置尽量的分布均匀些，尽量使得每个位置上的元素数量只有一个，那么当我们用 hash 算法求得这个位置的时候，马上就可以知道对应位置的元素就是我们要的，而不用再去遍历链表
JDK1.7
- h&(length-1) 就相当于对 length 取模，而且在速度、效率上比直接取模要快得多
JDK1.8 优化
- 高 16 位异或低 16 位，然后再 h&(length-1)，目的：混合原始哈希码的高位和低位，以此来加大低位的随机性。而且混合后的低位掺杂了高位的部分特征，这样高位的信息也被变相保留下来。

碰撞，hash 冲突

哈希表为解决 Hash 冲突，可以采用开放地址法和链地址法来解决问题。HashMap 采用了链地址法。链地址法，简单来说，就是数组加链表的结合。在每个数组元素上都一个链表结构，当数据被 Hash 后，得到数组下标，把数据放在对应下标元素的链表上。
JDK1.7 链表头插。JDK1.8 链表尾插。

HashMap 的扩容 resize()？

JDK 1.7 先扩容后插入
- hashmap 使用一个容量更大的数组来代替旧的数组，transfer（）方法将原有 Entry 数组里的元素拷贝到新的 Entry 数组里，扩容之后，原数组中的数据必须重新计算其在新数组中的位置，并放进去，这就是 resize。
- 新容量=旧容量2；默认旧容量=160.75=12
- 在扩容后插入的过程中，存储在 LinkedList 中的元素的次序会反过来，因为移动到新的 bucket 位置的时候，HashMap 并不会将元素放在 LinkedList 的尾部，而是放在头部，这是为了避免尾部遍历(tail traversing)。
JDK 1.8 先插入后扩容
- 在 JDK1.8 的时候直接用了 JDK1.7 的时候计算的规律，也就是扩容前的原始位置+扩容的大小值=JDK1.8 的计算方式，而不再是 JDK1.7 的那种与计算的方法。但是这种方式就相当于只需要判断 Hash 值的新增参与运算的位是 0 还是 1 就直接迅速计算出了扩容后的储存方式。

JDK 1.7/1.8 扩容区别

HashMap 长度为什么等于 2 的幂？？

hashmap 中默认的数组大小为 16，加载因子 0.75。并且每次自动扩展或手动初始化时，长度必须是 2 的幂。
举例：
- 看下图，左边两组是数组长度为 16（2 的 4 次方），右边两组是数组长度为 15。两组的 hashcode 均为 8 和 9，但是很明显，当它们和 1110“与”的时候，产生了相同的结果，也就是说它们会定位到数组中的同一个位置上去，这就产生了碰撞，8 和 9 会被放到同一个链表上，那么查询的时候就需要遍历这个链表，得到 8 或者 9，这样就降低了查询的效率。
- 同时，我们也可以发现，当数组长度为 15 的时候，hashcode 的值会与 14（1110）进行“与”，那么最后一位永远是 0，而 0001，0011，0101，1001，1011，0111，1101 这几个位置永远都不能存放元素了，显然不符合 Hash 算法均匀分布的原则，空间浪费相当大，更糟的是这种情况中，数组可以使用的位置比数组长度小了很多，这意味着进一步增加了碰撞的几率，减慢了查询的效率！

所以，长度 16 或者其他 2 的幂，Length-1 的值是所有二进制位全为 1，这种情况下，index 的结果等同于 HashCode 后几位的值。只要输入的 HashCode 本身分布均匀，Hash 算法的结果就是均匀的。

JDK1.8 的 HashMap 的优化？

数据结构变化：
- 数组+链表+红黑树，当链表的深度达到 8 的时候，也就是默认阈值，就会自动扩容把链表转成红黑树的数据结构来把时间复杂度从 O（N）变成 O（logN）提高了效率
Hash 算法计算方式改变：
- 高 16 位异或低 16 位，后&(length-1)
扩容后不是重新计算所有元素在数组的位置：
- 新的位置=旧的位置 OR 旧的位置+旧容量
JDK1.7 用的是头插法，而 JDK1.8 及之后使用的都是尾插法，
- 因为 JDK1.7 是用单链表进行的纵向延伸，当采用头插法就是能够提高插入的效率，但是也会容易出现逆序且环形链表死循环问题。但是在 JDK1.8 之后是因为加入了红黑树，使用尾插法能够避免出现逆序且链表死循环的问题。
链表死循环问题 https://coolshell.cn/articles/9606.html/comment-page-1#comments

为什么 JDK1.8 中 HashMap 链表长度超过 8 会转成树结构？？

1.若桶中链表元素个数大于等于 8 时，链表转换成树结构；若桶中链表元素个数小于等于 6 时，树结构还原成链表。因为红黑树的平均查找长度是 log(n)，长度为 8 的时候，平均查找长度为 3，如果继续使用链表，平均查找长度为 8/2=4，这才有转换为树的必要。链表长度如果是小于等于 6，6/2=3，虽然速度也很快的，但是转化为树结构和生成树的时间并不会太短。
2.还有选择 6 和 8，中间有个差值 7 可以有效防止链表和树频繁转换。假设一下，如果设计成链表个数超过 8 则链表转换成树结构，链表个数小于 8 则树结构转换成链表，如果一个 HashMap 不停的插入、删除元素，链表个数在 8 左右徘徊，就会频繁的发生树转链表、链表转树，效率会很低。
1. 在这里简单解释一下，理想情况下，在随机哈希代码下，桶中的节点频率遵循泊松分布，文中给出了桶长度 k 的频率表。由频率表可以看出，桶的长度超过 8 的概率非常非常小。所以作者应该是根据概率统计而选择了 8 作为阀值，由此可见，这个选择是非常严谨和科学的。

HashMap 为什么是线程不安全的？

HashMap resize 而引起死循环.（条件竞争）。扩容的的时候可能会形成环形链表，造成死循环。 https://coolshell.cn/articles/9606.html/comment-page-1#comments
put 的时候导致的多线程数据不一致
- 在多线程下 put 操作时，产生哈希碰撞，最后的写入操作会覆盖先前的写入操作----写入不一致。最后的修改操作会覆盖先前的修改---修改不一致。
注意：要想实现线程安全，那么需要调用 collections 类的静态方法

为什么 String, Interger 这样的 wrapper 类适合作为键？？

1.不可变性： String 是不可变的，也是 final 的
- 计算 hashCode()，就要防止键值改变，如果键值在放入时和获取时返回不同的 hashcode 的话，那么就不能从 HashMap 中找到你想要的对象。
- 不可变性还有其他的优点如线程安全。
2.已经重写了 equals() 和 hashCode() 方法
- 为什么要重写 equals() 方法？
  - 1．Object 类中 equals 方法比较的是两个对象的引用地址，只有对象的引用地址指向同一个地址时，才认为这两个地址是相等的，否则这两个对象就不相等。
  - 2.如果有两个对象，他们的属性是相同的，但是地址不同，这样使用 equals() 比较得出的结果是不相等的，而我们需要的是这两个对象相等，因此默认的 equals() 方法是不符合我们的要求的，这个时候我们就需要对 equals() 方法进行重写以满足我们的预期结果。
  - 3.在 java 的集合框架中需要用到 equals() 方法进行查找对象，如果集合中存放的是自定义类型，并且没有重写 equals() 方法，则会调用 Object 父类中的 equals() 方法按照地址比较，往往会出现错误的结果，此时我们应该根据业务需求重写 equals() 方法。
  - 如果不重写 equals，那么比较的将是对象的引用是否指向同一块内存地址，重写之后目的是为了比较两个对象的 value 值是否相等。
- 为什么 java 中在重写 equals() 方法后必须对 hashCode() 方法进行重写？
  - 1.为了维护 hashCode() 方法的 equals 协定，该协定指出：相等的对象必须具有相等的散列码（hashCode）；而两个 hashCode() 返回的结果相等，两个对象的 equals() 方法不一定相等。
  - 2.如果不重写 hashCode()，就会造成相等对象，不同的 hashCode();在 hashMap 中就会存储两个值一样的对象。导致混淆。

我们可以使用自定义的对象作为键吗？？

当然你可能使用任何对象作为键，只要它遵守了 equals() 和 hashCode() 方法的定义规则，并且当对象插入到 Map 中之后将不会再改变了。如果这个自定义对象时不可变的，那么它已经满足了作为键的条件，因为当它创建之后就已经不能改变了。

HashTable

什么是 HashTable

Hashtable 也是一个散列表，它存储的内容是键值对(key-value) 映射。
Hashtable 继承于 Dictionary，实现了 Map、Cloneable、java.io.Serializable 接口。
Hashtable 的函数都是同步的，这意味着它是线程安全的。它的 key、value 都不可以为 null。此外，Hashtable 中的映射不是有序的。

HashTable 的参数？

（1） table 是一个 Entry[]数组类型，而 Entry 实际上就是一个单向链表。哈希表的"key-value 键值对"都是存储在 Entry 数组中的。
（2） count 是 Hashtable 的大小，它是 Hashtable 保存的键值对的数量。
（3） threshold 是 Hashtable 的阈值，用于判断是否需要调整 Hashtable 的容量。 threshold 的值="容量*加载因子"。
（4） loadFactor 就是加载因子。
（5） modCount 是用来实现 fail-fast 机制的

HashTable 的扩容

默认初始容量为 11
线程安全，但是速度慢，不允许 key/value 为 null
加载因子为 0.75：即当元素个数超过容量长度的 0.75 倍时，进行扩容
- 扩容增量： 2*原数组长度+1
  - 如 HashTable 的容量为 11，一次扩容后是容量为 23

HashTable 和 HashMap 的区别

1.继承的父类不同
- Hashtable 继承自 Dictionary 类，而 HashMap 继承自 AbstractMap 类。但二者都实现了 Map 接口。
2.线程安全性不同
- Hashtable 同步-线程安全。HashMap 非同步-不是线程安全的。
3.是否提供 contains 方法
- HashMap 把 Hashtable 的 contains 方法去掉了，改成 containsValue 和 containsKey
- Hashtable 则保留了 contains，containsValue 和 containsKey 三个方法，其中 contains 和 containsValue 功能相同。
4.key 和 value 是否允许 null 值
- Hashtable 不允许，HashMap 允许
5.两个遍历方式的内部实现上不同
- Hashtable、HashMap 都使用了 Iterator。而由于历史原因，Hashtable 还使用了 Enumeration 的方式。
6.哈希值的使用不同
- Hashtable 直接使用对象的 hashCode、HashMap 重新计算 hash 值，而且用于代替求模
7.内部实现使用的数组初始化和扩容方式不同，
- Hashtable 默认容量为 11，不要求底层数组的容量一定要为 2 的整数次幂，扩容时将容量变为原来的 2 倍加 1，
- HashMap 默认容量为 16，要求底层数组的容量一定要为 2 的整数次幂，扩容时将容量变为原来的 2 倍

ConcurrHashMap

什么是 ConcurrentHashMap?

ConcurrentHashMap 就是多线程编程中可以使用的一种高性能的线程安全 HashMap 方案。

为什么用 ConcurrentHashMap?

HashMap 是线程不安全的，在并发环境下，可能会形成环状链表（扩容时可能造成，具体原因自行百度 google 或查看源码分析），导致 get 操作时，cpu 空转
HashTable 线程安全的策略实现代价却太大了，简单粗暴，get/put 所有相关操作都是 synchronized 的，这相当于给整个哈希表加了一把大锁，多线程访问时候，只要有一个线程访问或操作该对象，那其他线程只能阻塞，相当于将所有的操作串行化，在竞争激烈的并发场景中性能就会非常差。

JDK1.7 ConcurrentHashMap?

1.7 结构

Segment

Segment 的结构和 HashMap 类似，是一种数组和链表结构。
同 HashMap 一样，Segment 包含一个 HashEntry 数组，数组中的每一个 HashEntry 既是一个键值对，也是一个链表的头节点。
每个 Segment 守护着一个 HashEntry 数组里的元素，当对 HashEntry 数组的数据进行修改时，必须首先获得它对应的 Segment 锁。
Segment 是一种可重入锁 ReentrantLock

什么是分段锁技术？

容器里有多把锁，每一把锁用于锁容器其中一部分数据，那么当多线程访问容器里不同数据段的数据时，线程间就不会存在锁竞争，从而可以有效的提高并发访问效率

ConcurrentHashMap 的工作原理？

ConcurrentHashMap 所使用的锁分段技术，首先将数据分成一段一段的存储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一个段数据的时候，其他段的数据也能被其他线程访问。能够实现真正的并发访问。
有一些方法需要跨段，比如 size() 和 containsValue()，它们可能需要锁定整个表而不仅仅是某个段，这需要按顺序锁定所有段，操作完毕后，又按顺序释放所有段的锁。这里“按顺序”是很重要的，否则极有可能出现死锁

初始化

三个参数

initialCapacity
- initialCapacity 表示新创建的这个 ConcurrentHashMap 的初始容量，也就是上面的结构图中的 Entry 数量。默认值为 static final int DEFAULT_INITIAL_CAPACITY = 16;
loadFactor
- loadFactor 表示负载因子，就是当 ConcurrentHashMap 中的元素个数大于 loadFactor * 最大容量时就需要 rehash，扩容。默认值为 static final float DEFAULT_LOAD_FACTOR = 0.75f;
concurrencyLevel
- concurrencyLevel 表示并发级别，这个值用来确定 Segment 的个数，Segment 的个数是大于等于 concurrencyLevel 的第一个 2 的 n 次方的数。比如，如果 concurrencyLevel 为 12，13，14，15，16 这些数，则 Segment 的数目为 16(2 的 4 次方)。默认值为 static final int DEFAULT_CONCURRENCY_LEVEL = 16;。理想情况下 ConcurrentHashMap 的真正的并发访问量能够达到 concurrencyLevel，因为有 concurrencyLevel 个 Segment，假如有 concurrencyLevel 个线程需要访问 Map，并且需要访问的数据都恰好分别落在不同的 Segment 中，则这些线程能够无竞争地自由访问（因为他们不需要竞争同一把锁），达到同时访问的效果。这也是为什么这个参数起名为“并发级别”的原因。
concurrencyLevel 主要用来初始化 segments、segmentShift 和 segmentMask 等；而 initialCapacity 和 loadFactor 则主要用来初始化每个 Segment 分段。

初始化 ConcurrentHashMap

ssize(segments 数组的长度) sshift(计算 ssize 时进行移位操作的次数)
segmentShift 段偏移量
segmentMask 段掩码
例子：

初始化 Segment 分段

ssize 2 的 N 次方大于等于 ConcurrentHashMapLevel
sshift (计算 ssize 时进行移位操作的次数)log(ssize)
segmentShift = 32 - sshift; //之所以用 32 是因为 ConcurrentHashMap 里的 hash() 方法输出的最大数是 32 位的
segmentMask = ssize - 1;
例如 LconcurrencyLevel 等于 16，则 ssize=16,sshift=4，则 segmentShift 为 28,。segmentMask=15;hash 值是一个 32 位的整数，将其向右移动 28 位就变成这个样子：0000 0000 0000 0000 0000 0000 0000 xxxx，然后再用这个值与 segmentMask 做&运算，也就是取最后四位的值。这个值确定 Segment 的索引。

三次 hash

Segment 下面包含很多个 HashEntry 列表数组。对于一个 key，需要经过三次（为什么要 hash 三次下文会详细讲解）hash 操作，才能最终定位这个元素的位置，这三次 hash 分别为：
- 对于一个 key，先进行一次 hash 操作，得到 hash 值 h1，也即 h1 = hash1(key)；
- 将得到的 h1 的高几位进行第二次 hash，得到 hash 值 h2，也即 h2 = hash2(h1 高几位)，通过 h2 能够确定该元素的放在哪个 Segment；
- 将得到的 h1 进行第三次 hash，得到 hash 值 h3，也即 h3 = hash3(h1)，通过 h3 能够确定该元素放置在哪个 HashEntry。

Put 操作？

put 操作是要加锁的。

判断 value 是否为 null，如果为 null，直接抛出异常。
key 通过一次 hash 运算得到一个 hash 值。(这个 hash 运算下文详说)
将得到 hash 值向右按位移动 segmentShift 位，然后再与 segmentMask 做&运算得到 segment 的索引 j。
在初始化的时候我们说过 segmentShift 的值等于 32-sshift，例如 concurrencyLevel 等于 16，则 sshift 等于 4，则 segmentShift 为 28。hash 值是一个 32 位的整数，将其向右移动 28 位就变成这个样子： 0000 0000 0000 0000 0000 0000 0000 xxxx，然后再用这个值与 segmentMask 做&运算，也就是取最后四位的值。这个值确定 Segment 的索引。
使用 Unsafe 的方式从 Segment 数组中获取该索引对应的 Segment 对象。
向这个 Segment 对象中 put 值，这个 put 操作也基本是一样的步骤（通过&运算获取 HashEntry 的索引，然后 set）。

Get 操作？

JDK1.7 的 ConcurrentHashMap 的 get 操作是不加锁的，因为在每个 Segment 中定义的 HashEntry 数组和在每个 HashEntry 中定义的 value 和 next HashEntry 节点都是 volatile 类型的，volatile 类型的变量可以保证其在多线程之间的可见性，因此可以被多个线程同时读，从而不用加锁。
而其 get 操作步骤也比较简单，定位 Segment –> 定位 HashEntry –> 通过 getObjectVolatile() 方法获取指定偏移量上的 HashEntry –> 通过循环遍历链表获取对应值。
- 定位 Segment：(((h >>> segmentShift) & segmentMask) << SSHIFT) + SBASE
- 定位 HashEntry：(((tab.length - 1) & h)) << TSHIFT) + TBASE

Remove 操作？

size 操作？

计算 ConcurrentHashMap 的元素大小是一个有趣的问题，因为他是并发操作的，就是在你计算 size 的时候，他还在并发的插入数据，可能会导致你计算出来的 size 和你实际的 size 有相差（在你 return size 的时候，插入了多个数据），要解决这个问题，JDK1.7 版本用两种方案
第一种方案他会使用不加锁的模式去尝试多次计算 ConcurrentHashMap 的 size，最多三次，比较前后两次计算的结果，结果一致就认为当前没有元素加入，计算的结果是准确的
第二种方案是如果第一种方案不符合，他就会给每个 Segment 加上锁，然后计算 ConcurrentHashMap 的 size 返回
举例：
- 一个 Map 有 4 个 Segment，标记为 S1，S2，S3，S4，现在我们要获取 Map 的 size。
- 计算过程是这样的：
  - 第一次计算，不对 S1，S2，S3，S4 加锁，遍历所有的 Segment，假设每个 Segment 的大小分别为 1，2，3，4，更新操作次数分别为：2，2，3，1，则这次计算可以得到 Map 的总大小为 1+2+3+4=10，总共更新操作次数为 2+2+3+1=8；
  - 第二次计算，不对 S1,S2,S3,S4 加锁，遍历所有 Segment，假设这次每个 Segment 的大小变成了 2，2，3，4，更新次数分别为 3，2，3，1，因为两次计算得到的 Map 更新次数不一致（第一次是 8，第二次是 9) 则可以断定这段时间 Map 数据被更新，则此时应该再试一次；
  - 第三次计算，不对 S1，S2，S3，S4 加锁，遍历所有 Segment，假设每个 Segment 的更新操作次数还是为 3，2，3，1，则因为第二次计算和第三次计算得到的 Map 的更新操作的次数是一致的，就能说明第二次计算和第三次计算这段时间内 Map 数据没有被更新，此时可以直接返回第三次计算得到的 Map 的大小。
  - 最坏的情况：第三次计算得到的数据更新次数和第二次也不一样，则只能先对所有 Segment 加锁再计算最后解锁。

JDK1.8 ConcurrentHashMap?

1.8 结构

ConcurrentHashMap 在 1.8 版本摒弃了 Segment（锁段）的概念，而是启用了一种全新的 CAS 算法的方式实现，Node + CAS + Synchronized。数据结构沿用了与它同时期的 HashMap 版本的思想，底层依然由数组+链表+红黑树的方式思想。

CAS 思想和实现原理？

乐观锁：认为数据一般情况下不会造成冲突，所以在数据进行提交更新的时候，才会正式对数据的冲突与否进行检测，如果发现冲突了，则让用户返回错误的信息。让用户决定如何去做。
悲观锁:就是对数据的冲突采取一种悲观的态度，也就是说假设数据肯定会冲突，所以在数据开始读取的时候就把数据锁定住。【数据锁定：数据将暂时不会得到修改】
思想：
- CAS（Compare And Swap，比较交换）：CAS 有三个操作数，内存值 V、预期值 A、要修改的新值 B，当且仅当 A 和 V 相等时才会将 V 修改为 B，否则什么都不做。
- 实现 CAS 最重要的一点，就是比较和交换操作的一致性，否则就会产生歧义。
  - 比如当前线程比较成功后，准备更新共享变量值的时候，这个共享变量值被其他线程更改了，那么 CAS 函数必须返回 false。
实现原理
- CAS 通过调用 JNI 的代码实现的。JNI:Java Native Interface-JAVA 本地接口，允许 java 与其他语言交互。
- 要实现这个需求，java 中提供了 Unsafe 类，它提供了三个函数，分别用来操作基本类型 int 和 long，以及引用类型 Object。方法的实现位于 unsafe.cpp 中
```
public final native boolean compareAndSwapObject
    (Object obj, long valueOffset, Object expect, Object update);

    public final native boolean compareAndSwapInt
    (Object obj, long valueOffset, int expect, int update);

    public final native boolean compareAndSwapLong
    (Object obj, long valueOffset, long expect, long update);
```
- Java 中 CAS 操作通过 JNI 本地方法实现，在 JVM 中程序会根据当前处理器的类型来决定是否为 cmpxchg 指令添加 lock 前缀。如果程序是在多处理器上运行，就为 cmpxchg 指令加上 lock 前缀（Lock Cmpxchg）；反之，如果程序是在单处理器上运行，就省略 lock 前缀。
- lock 前缀有两个特性 1，禁止该指令与前面和后面的读写指令重排序 2，把写缓冲区的所有数据刷新到内存中
- 这两点保证了内存屏障效果，保证了 CAS 同时具有 volatile 读和 volatile 写的内存语义。
缺点
- 不过 CAS 操作也存在一些缺点：1. 存在 ABA 问题，其解决思路是使用版本号；2. 循环时间长，开销大；3. 只能保证一个共享变量的原子操作。

ConcurrentHashMap1.8 的工作原理？

在 JDK1.7 之前，ConcurrentHashMap 是通过分段锁机制来实现的，所以其最大并发度受 Segment 的个数限制。因此，在 JDK1.8 中，ConcurrentHashMap 的实现原理摒弃了这种设计，而是选择了与 HashMap 类似的数组+链表+红黑树的方式实现，而加锁则采用 CAS 和 synchronized 实现。
首先，在 table 中添加一个元素时，如果添加元素的链表节点个数超过 8，则会触发链表向红黑树结构转换。
- 首先会检查 hash 表的大小是否大于等于 MIN_TREEIFY_CAPACITY，默认值为 64，如果小于该值，则表示不需要转化为红黑树结构，直接将 hash 表扩容即可。
- 如果当前 table 的长度大于 64，则使用 CAS 获取指定的 Node 节点，然后对该节点通过 synchronized 加锁，由于只对一个 Node 节点加锁，因此该操作并不影响其他 Node 节点的操作，因此极大的提高了 ConcurrentHashMap 的并发效率。
- 加锁之后，便是将这个 Node 节点所在的链表转换为 TreeBin 结构的红黑树。
- 然后，在 table 中删除元素时，如果元素所在的红黑树节点个数小于 6，则会触发红黑树向链表结构转换。

数据结构

ConcurrentHashMap 中包含一个 table 数组，其类型是一个 Node 数组；而 Node 是一个继承自 Map.Entry<K, V>的链表，而当这个链表结构中的数据大于 8，则将数据结构升级为 TreeBin 类型的红黑树结构。
JDK1.8 中的 ConcurrentHashMap 中还包含一个重要属性 sizeCtl，其是一个控制标识符，不同的值代表不同的意思：
- 其为 0 时，表示 hash 表还未初始化
- 而为正数时这个数值表示初始化或下一次扩容的大小，相当于一个阈值；即如果 hash 表的实际大小>=sizeCtl，则进行扩容，默认情况下其是当前 ConcurrentHashMap 容量的 0.75 倍；
- 而如果 sizeCtl 为-1，表示正在进行初始化操作；
- 而为-N 时，则表示有 N-1 个线程正在进行扩容。

1.8 初始化 ConcurrentHashMap

首先会判断 sizeCtl 的值，如果其小于 0，则说明其正在进行初始化或扩容操作，则不执行任何操作，调用 yield() 方法使当前线程返回等待状态；
而如果 sizeCtl 大于等于 0，则使用 CAS 操作比较 sizeCtl 的值是否是-1，如果是-1 则进行初始化。
- 初始化时，如果 sizeCtl 的值为 0，则创建默认容量的 table；否则创建大小为 sizeCtl 的 table；
- 然后重置 sizeCtl 的值为 0.75n，即当前 table 容量的 0.75 倍，并返回创建的 table，此时初始化 hash 表完成。

Put 操作

计算 key 的 hash 值，即调用 speed() 方法计算 hash 值；
获取 hash 值对应的 Node 节点位置，此时通过一个循环实现。有以下几种情况：
- 如果 table 表为空，则首先进行初始化操作，初始化之后再次进入循环获取 Node 节点的位置；
- 如果 table 不为空，但没有找到 key 对应的 Node 节点，则直接调用 casTabAt() 方法插入一个新节点，此时不用加锁；
- 如果 table 不为空，且 key 对应的 Node 节点也不为空，但 Node 头结点的 hash 值为 MOVED(-1)，则表示需要扩容，此时调用 helpTransfer() 方法进行扩容；
- 其他情况下，则直接向 Node 中插入一个新 Node 节点，此时需要对这个 Node 链表或红黑树通过 synchronized 加锁。
插入元素后，判断对应的 Node 结构是否需要改变结构，如果需要则调用 treeifyBin() 方法将 Node 链表升级为红黑树结构；
最后，调用 addCount() 方法记录 table 中元素的数量。

Get 操作

通过 get 获取 hash 表中的值时，首先需要获取 key 值的 hash 值。而在 JDK1.8 的 ConcurrentHashMap 中通过 spread() 方法获取。
speed() 方法将 key 的 hash 值进行再 hash，让 hash 值的高位也参与 hash 运算，从而减少哈希冲突。然后再查询对应的 value 值。
查询时，首先通过 tabAt() 方法找到 key 对应的 Node 链表或红黑树，然后遍历该结构便可以获取 key 对应的 value 值。其中，tabAt() 方法主要通过 Unsafe 类的 getObjectVolatile() 方法获取 value 值，通过 volatile 读获取 value 值，可以保证 value 值的可见性，从而保证其是当前最新的值。

size 操作

JDK1.8 的 ConcurrentHashMap 中保存元素的个数的记录方法也有不同，首先在添加和删除元素时，会通过 CAS 操作更新 ConcurrentHashMap 的 baseCount 属性值来统计元素个数。但是 CAS 操作可能会失败，因此，ConcurrentHashMap 又定义了一个 CounterCell 数组来记录 CAS 操作失败时的元素个数。
因此，ConcurrentHashMap 中元素的个数则通过如下方式获得：元素总数 = baseCount + sum(CounterCell)
size 只能获取 int 范围内的 ConcurrentHashMap 元素个数；而如果 hash 表中的数据过多，超过了 int 类型的最大值，则推荐使用 mappingCount() 方法获取其元素个数。

ConcurrentHashMap JDK1.7 1.8 区别?

JDK 1.7 ReentrantLock+Segment+HashEntry JDK1.8 synchronized+CAS+HashEntry+红黑树

1.JDK1.8 的实现降低锁的粒度，JDK1.7 版本锁的粒度是基于 Segment 的，包含多个 HashEntry，而 JDK1.8 锁的粒度就是 HashEntry（首节点）
2.JDK1.8 版本的数据结构变得更加简单，使得操作也更加清晰流畅，因为已经使用 synchronized 来进行同步，所以不需要分段锁的概念，也就不需要 Segment 这种数据结构了，由于粒度的降低，实现的复杂度也增加了
3.JDK1.8 使用红黑树来优化链表，基于长度很长的链表的遍历是一个很漫长的过程，而红黑树的遍历效率是很快的，代替一定阈值的链表，这样形成一个最佳拍档

JDK1.8 为什么使用内置锁 synchronized 来代替重入锁 ReentrantLock?

1.因为粒度降低了，在相对而言的低粒度加锁方式，synchronized 并不比 ReentrantLock 差，在粗粒度加锁中 ReentrantLock 可能通过 Condition 来控制各个低粒度的边界，更加的灵活，而在低粒度中，Condition 的优势就没有了
2.JVM 的开发团队从来都没有放弃 synchronized，而且基于 JVM 的 synchronized 优化空间更大，使用内嵌的关键字比使用 API 更加自然
3.在大量的数据操作下，对于 JVM 的内存压力，基于 API 的 ReentrantLock 会开销更多的内存，虽然不是瓶颈，但是也是一个选择依据

ConcurrentHashMap 和 HashMap 区别

1.HashMap 非线程安全 ConcurrentHashMap 线程安全
2.ConcurrentHashMap 将整个 Hash 桶进行了分段 segment，每个 segment 上都有锁
3.ConcurrentHashMap 让锁的粒度更精细，并发性能更好。

ConcurrentHashMap 和 HashTable 区别

1.底层数据结构
- ConcurrentHashMap1.7 分段数组+链表
- ConcurrentHashMap1.8 数组+链表/红黑二叉树
- HashTable 数组+链表
2.实现线程安全的方式
- Hashtable 的所有操作都会锁住整个对象，虽然能够保证线程安全，但是性能较差；
- ConcurrentHashMap 内部使用 Segment 数组，每个 Segment 类似于 Hashtable，在“写”线程或者部分特殊的“读”线程中锁住的是某个 Segment 对象，其它的线程能够并发执行其它的 Segment 对象。

分享到QQ

分享到微博