ConcurrentHashMap 在 Java7 和 8 有何不同？

文章目录

ConcurrentHashMap 在 Java7 和 8 有何不同？前言1.Java 72.Java 83.重要的方法回顾3.1 Node 数组3.2 put 方法3.3 get 方法 4.对比Java7 和Java8 的异同和优缺点4.1 数据结构不同4.2 并发度4.3 保证并发安全的原理4.4 遇到 Hash 碰撞4.5 查询时间复杂度 5.参考

前言

本章的部分内容在之前的文章 Java并发编程|第十篇：ConcurrentHashMap源码分析 也有提到，但是之前的文章更偏重于源码的分析，相对比较复杂和枯燥。而本章主要是针对面试的重点进行讨论，以及之前内容的总结与回顾。

1.Java 7

从图中我们可以看出，在 ConcurrentHashMap 内部进行了 Segment 分段，Segment 继承了 ReentrantLock，可以理解为一把锁，各个 Segment 之间都是相互独立上锁的，互不影响。相比于之前的 Hashtable 每次操作都需要把整个对象锁住而言，大大提高了并发效率。因为它的锁与锁之间是独立的，而不是整个对象只有一把锁。

每个 Segment 的底层数据结构与 HashMap 类似，仍然是数组和链表组成的拉链法结构。默认有 0~15 共 16 个 Segment，所以最多可以同时支持 16 个线程并发操作（操作分别分布在不同的 Segment 上）。16 这个默认值可以在初始化的时候设置为其他值，但是一旦确认初始化以后，是不可以扩容的。

2.Java 8

图中的节点有三种类型

第一种是最简单的，空着的位置代表当前还没有元素来填充。第二种就是和 HashMap 非常类似的拉链法结构，在每一个槽中会首先填入第一个节点，但是后续如果计算出相同的 Hash 值，就用链表的形式往后进行延伸。第三种结构就是红黑树结构，这是 Java 7 的 ConcurrentHashMap 中所没有的结构，在此之前我们可能也很少接触这样的数据结构。

当第二种情况的链表长度大于某一个阈值（默认为 8），且同时满足一定的容量要求的时候，ConcurrentHashMap 便会把这个链表从链表的形式转化为红黑树的形式，目的是进一步提高它的查找性能。所以，Java 8 的一个重要变化就是引入了红黑树的设计，由于红黑树并不是一种常见的数据结构，所以我们在此简要介绍一下红黑树。

红黑树的特点：

根节点是黑色的

每个叶子节点都是黑色的空节点（NIL），也就是说，叶子节点不存储数据

任何相邻的节点都不能同时为红色，也就是说，红色节点是被黑色节点隔开的

每个节点，从该节点到达其可达叶子节点的所有路径，都包含相同数目的黑色节点

红黑树是一种特殊平衡二叉查找树(AVL树)，查找效率高，会自动平衡，防止极端不平衡从而影响查找效率的情况发生。

由于自平衡的特点，即左右子树高度几乎一致，所以其查找性能近似于二分查找，时间复杂度是 O(logn) ；反观链表，它的时间复杂度就不一样了，如果发生了最坏的情况，可能需要遍历整个链表才能找到目标元素，时间复杂度为 O(n)，远远大于红黑树的 O(logn)，尤其是在节点越来越多的情况下，O(logn) 体现出的优势会更加明显。

关于 O(logn) 的查询效率，可以参考博主之前的一篇文章：

《二分查找-上》 也是一种时间复杂度为 O(logn) 的查找方法，第三小节 3.O(logn) 惊人的查找速度。

3.重要的方法回顾

3.1 Node 数组

ConcurrentHashMap 内部是一个 Node 的数组

transient volatile Node<K,V>[] table;

Node

static class Node<K,V> implements Map.Entry<K,V> { final int hash; final K key; volatile V val; volatile Node<K,V> next; ...

每个 Node 里面是 key-value 的形式，并且把 value 用 volatile 修饰，以便保证可见性，同时内部还有一个指向下一个节点的 next 指针，方便产生链表结构。

initTable() 方法中默认初始化一个长度为 16 的 Node 数组，关键代码如下：

Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n]; table = tab = nt;//将值赋值给table

3.2 put 方法

final V putVal(K key, V value, boolean onlyIfAbsent) { if (key == null || value == null) throw new NullPointerException(); // 计算 hash 值 int hash = spread(key.hashCode()); int binCount = 0;// 记录链表的长度 for (Node<K,V>[] tab = table;;) { Node<K,V> f; int n, i, fh; if (tab == null || (n = tab.length) == 0) //如果node数组为空 tab = initTable();// 初始化 // 找该 hash 值对应的数组下标 else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) { //如果该位置是空的，就用 CAS 的方式放入新值 if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value, null))) break; // no lock when adding to empty bin } //hash值等于 MOVED 代表在扩容 else if ((fh = f.hash) == MOVED) tab = helpTransfer(tab, f);//协助扩容，逻辑和transfer类似 else { V oldVal = null; synchronized (f) {//对头节点加锁 if (tabAt(tab, i) == f) {//判断table数组当前位置是否为头节点 if (fh >= 0) {// 表示链表形式 binCount = 1;//记录链表的长度 for (Node<K,V> e = f;; ++binCount) {// 遍历链表 K ek; //如果发现该 key 已存在，就判断是否需要进行覆盖，然后返回 if (e.hash == hash && ((ek = e.key) == key || (ek != null && key.equals(ek)))) { oldVal = e.val; if (!onlyIfAbsent) e.val = value; break; } Node<K,V> pred = e; //到了链表的尾部也没有发现该 key，说明之前不存在，就把新值添加到链表的最后 if ((e = e.next) == null) { pred.next = new Node<K,V>(hash, key, value, null); break; } } } else if (f instanceof TreeBin) {//如果是红黑树 Node<K,V> p; binCount = 2; //调用红黑树的方法插入新值 if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key, value)) != null) { oldVal = p.val; if (!onlyIfAbsent) p.val = value; } } } } if (binCount != 0) { if (binCount >= TREEIFY_THRESHOLD) treeifyBin(tab, i);//如果链表的长度>=8 链表转化为红黑树 if (oldVal != null) //putVal 的返回是添加前的旧值，所以返回 oldVal return oldVal; break; } } } addCount(1L, binCount);// 集合的大小+1 return null; }

put方法大致分为四个阶段

第一个阶段可以称为初始化阶段，在第一次调用 put 方法时，table 数组为空，调用 initTable 方法进行 table 数组的初始化

第二个阶段，判断 table 数组对应位置节点是否为空，如果该位置是空的，就用 CAS 的方式放入新值

第三个阶段，产生 hash 碰撞，对头节点上锁，采用拉链法将冲突的元素转为链表

最后一个阶段，如果链表的长度>=8（且同时满足一定的容量要求的时候） 链表转化为红黑树

当然还有并发扩容，集合大小并发计算等等，可以从之前的源码分析文章进行了解。

3.3 get 方法

大致分为 5 步：

计算 Hash 值，通过 e = tabAt(tab, (n - 1) & h)) 获取到对应的槽点（节点）如果 table 数组是空的或者该位置为 null，那么直接返回 null如果该节点刚好就是我们需要的节点，直接返回该节点的值如果这个节点位置正在扩容（eh=-1）或者是红黑树的 Root 节点（eh=-2），那么调用节点的 find 方法继续查找否则就遍历链表进行查找

源码如下：

public V get(Object key) { Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek; int h = spread(key.hashCode());//计算hash值 // 如果 table 为空或者当前节点为空，直接返回null if ((tab = table) != null && (n = tab.length) > 0 && (e = tabAt(tab, (n - 1) & h)) != null) { //获取当前tab[i]的node if ((eh = e.hash) == h) {//如果该节点的hash值和h相等 if ((ek = e.key) == key || (ek != null && key.equals(ek))) return e.val;//如果key值相同，返回当前节点的val值 } // eh = -1，该节点为fwd节点 数组正在扩容 // eh = -2，该节点为红黑树的Root节点 else if (eh < 0)//调用该节点的find方法查找 return (p = e.find(h, key)) != null ? p.val : null; while ((e = e.next) != null) {//遍历链表 //在当节点一直向下查找下一个节点，判断是否有key值相等 if (e.hash == h && ((ek = e.key) == key || (ek != null && key.equals(ek)))) return e.val; } } return null; }

4.对比Java7 和Java8 的异同和优缺点

4.1 数据结构不同

Java 7 采用 Segment 分段锁来实现，而 Java 8 中的 ConcurrentHashMap 使用数组 + 链表 + 红黑树

4.2 并发度

Java 7 中，每个 Segment 独立加锁，最大并发个数就是 Segment 的个数，默认是 16。

Java 8 中，锁粒度更细，理想情况下 table 数组元素的个数（也就是数组长度）就是其支持并发的最大个数，并发度比之前有提高。

4.3 保证并发安全的原理

Java 7 采用 Segment 分段锁来保证安全，而 Segment 是继承自 ReentrantLock。

Java 8 中放弃了 Segment 的设计，采用 Node + CAS + synchronized 保证线程安全。

4.4 遇到 Hash 碰撞

Java 7 在 Hash 冲突时，会使用拉链法，也就是链表的形式。

Java 8 先使用拉链法，在链表长度超过一定阈值时，将链表转换为红黑树，来提高查找效率。

4.5 查询时间复杂度

Java 7 遍历链表的时间复杂度是 O(n)，n 为链表长度。

Java 8 如果变成遍历红黑树，那么时间复杂度降低为 O(logn)，n 为树的节点个数。

5.参考

《Java 并发编程 78 讲》- 徐隆曦