慕课君

V1

2022/09/20阅读:11主题:极简黑

一文讲清楚ConcurrentHashMap原理,值得收藏。

ConcurrentHashMap原理是面试的一个高频知识点,这属于第一阶段的过招。

如果你答上来了,之后面试官可能会顺势追问一下,如何提高 ConcurrentHashMap 的插入效率?于是一个接着一个,连环问就开始了,直到探到你的老底才罢休。

今天我们用一篇文章把ConcurrentHashMap讲清楚,帮你在面试时不慌不忙,从容应对。

1、ConcurrentHashMap 原理概述

ConcurrentHashMap 是一个存储 key/value 对的容器,并且是线程安全的。我们先看 ConcurrentHashMap 的存储结构,如下图:

这是经典的数组加链表的形式。并且在链表长度过长时转化为红黑树存储( Java 8 的优化),加快查找速度。

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

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

  1. 通过对象 x 的 hashCode () 方法获取其 hashCode;

  2. 将 hashCode 映射到数组的某个位置上;

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

从容器取数的逻辑如下:

  1. 通过对象 x 的 hashCode () 方法获取其 hashCode;

  2. 将 hashCode 映射到数组的某个位置上;

  3. 遍历该位置的链表或者从红黑树中找到匹配的对象返回。

这个数组 + 链表的存储结构其实是一个哈希表。

把对象 x 映射到数组的某个位置的函数,叫做 hash 函数。

这个函数的好坏决定元素在哈希表中分布是否均匀,如果元素都堆积在一个位置上,那么在取值时需要遍历很长的链表。

但元素如果是均匀的分布在数组中,那么链表就会较短,通过哈希函数定位位置后,能够快速找到对应的元素。

具体 ConcurrentHashMap 中的哈希函数如何实现我们后面会详细讲到。

扩容

我们大致了解了 ConcurrentHashMap 的存储结构。

那么我们思考一个问题,当数组中保存的链表越来越多,那么再存储进来的元素大概率会插入到现有的链表中,而不是使用数组中剩下的空位。

这样会造成数组中保存的链表越来越长,由此导致哈希表查找速度下降,从 O (1) 慢慢趋近于链表的时间复杂度 O (n/2),这显然违背了哈希表的初衷。

所以 ConcurrentHashMap 会做一个操作,称为扩容。

也就是把数组长度变大,增加更多的空位出来,最终目的就是预防链表过长,这样查找的时间复杂度才会趋向于 O (1)。

扩容的操作并不会在数组没有空位时才进行,因为在桶位快满时,新保存元素更大的概率会命中已经使用的位置,那么可能最后几个桶位很难被使用,而链表却越来越长了。ConcurrentHashMap 会在更合适的时机进行扩容,通常是在数组中 75% 的位置被使用时。

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

其实以上内容和 HashMap 类似,ConcurrentHashMap 此外提供了线程安全的保证,它主要是通过 CAS 和 Synchronized 关键字来实现,我们在源码分析中再详细来看。

我们做一下总结:

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

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

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

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

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

2、ConcurrentHashMap 的构成

2.1 重要属性

我们来看看 ConcurrentHashMap 的几个重要属性

1、transient volatile Node<K,V>[] table

这个 Node 数组就是 ConcurrentHashMap 用来存储数据的哈希表。

2、private static final int DEFAULT_CAPACITY = 16;

这是默认的初始化哈希表数组大小

3、static final int TREEIFY_THRESHOLD = 8

转化为红黑树的链表长度阈值

4、static final int MOVED = -1

这个标识位用于识别扩容时正在转移数据

5、static final int HASH_BITS = 0x7fffffff;

计算哈希值时用到的参数,用来去除符号位

6、private transient volatile Node<K,V>[] nextTable;

数据转移时,新的哈希表数组

可能有些属性看完解释你还摸不到头脑。没关系,我们在后面源码分析时,具体使用的地方还会做相应讲解。

2.2 重要组成元素

Node

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

ForwardingNode

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

TreeBin

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

TreeNode

红黑树的节点。

3、put 方法源码分析

put 方法用来把一个键值对存储到 map 中。代码如下:

public V put(K key, V value) {
return putVal(key, value, false);
}

实际调用的是 putVal 方法,第三个参数传入 false,控制 key 存在时覆盖原来的值。

我们接下来看 putVal 的代码,代码比较多,我把解释直接放到代码中:

final V putVal(K key, V value, boolean onlyIfAbsent) {
//key和value不能为空
if (key == null || value == null) throw new NullPointerException();
//计算key的hash值,后面我们会看spread方法的实现
int hash = spread(key.hashCode());
int binCount = 0;
//开始自旋,table属性采取懒加载,第一次put的时候进行初始化
for (Node<K,V>[] tab = table;;) {
        Node<K,V> f; int n, i, fh;
//如果table未被初始化,则初始化table
if (tab == null || (n = tab.length) == 0)
            tab = initTable();
//通过key的hash值映射table位置,如果该位置的值为空,那么生成新的node来存储该key、value,放入此位置
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
if (casTabAt(tab, i, null,
new Node<K,V>(hash, key, value, null)))
break;                   // no lock when adding to empty bin
        }
//如果该位置节点元素的hash值为MOVED,也就是-1,代表正在做扩容的复制。那么该线程参与复制工作。
else if ((fh = f.hash) == MOVED)
            tab = helpTransfer(tab, f);
//下面分支处理table映射的位置已经存在node的情况
else {
            V oldVal = null;
            synchronized (f) {
//再次确认该位置的值是否已经发生了变化
if (tabAt(tab, i) == f) {
//fh大于0,表示该位置存储的还是链表
if (fh >= 0) {
                        binCount = 1;
//遍历链表
for (Node<K,V> e = f;; ++binCount) {
                            K ek;
//如果存在一样hash值的node,那么根据onlyIfAbsent的值选择覆盖value或者不覆盖
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;
//如果找到最后一个元素,也没有找到相同hash的node,那么生成新的node存储key/value,作为尾节点放入链表。
if ((e = e.next) == null) {
                                pred.next = new Node<K,V>(hash, key,
value, null);
break;
                            }
                        }
                    }
//下面的逻辑处理链表已经转为红黑树时的key/value保存
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;
                        }
                    }
                }
            }
//node保存完成后,判断链表长度是否已经超出阈值,则进行哈希表扩容或者将链表转化为红黑树
if (binCount != 0) {
if (binCount >= TREEIFY_THRESHOLD)
                    treeifyBin(tab, i);
if (oldVal != null)
return oldVal;
break;
            }
        }
    }
//计数,并且判断哈希表中使用的桶位是否超出阈值,超出的话进行扩容
    addCount(1L, binCount);
return null;
}

主线流程梳理如下图:

其实 put 的核心思想都在这里了。接下来我们分别看一下关键节点的方法源码。

4、spread 方法源码分析

哈希算法的逻辑,决定 ConcurrentHashMap 保存和读取速度。hash 算法是 hashmap 的核心算法,JDK 的实现十分巧妙,值得我们学习。

spreed 方法源代码如下:

static final int spread(int h) {
return (h ^ (h >>> 16)) & HASH_BITS;
}

传入的参数 h 为 key 对象的 hashCode,spreed 方法对 hashCode 进行了加工。重新计算出 hash。我们先暂不分析这一行代码的逻辑,先继续往下看如何使用此 hash 值。

hash 值是用来映射该 key 值在哈希表中的位置。取出哈希表中该 hash 值对应位置的代码如下。

tabAt(tab, i = (n - 1) & hash)

我们先看这一行代码的逻辑,第一个参数为哈希表,第二个参数是哈希表中的数组下标。

通过 (n - 1) & hash 计算下标。

n 为数组长度,我们以默认大小 16 为例,那么 n-1 = 15,我们可以假设 hash 值为 100,那么 15 & 100 为多少呢?

& 把它左右数值转化为二进制,按位进行与操作,只有两个值都为 1 才为 1,有一个为 0 则为 0。

那么我们把 15 和 100 转化为二进制来计算,java 中 int 类型为 8 个字节,一共 32 个 bit 位。

n 的值 15 转为二进制:

0000 0000 0000 0000 0000 0000 0000 1111

hash 的值 100 转为二进制:

0000 0000 0000 0000 0000 0000 0110 0100。

计算结果:

0000 0000 0000 0000 0000 0000 0000 0100

对应的十进制值为 4

是不是已经看出点什么了?

15 的二进制高位都为 0,低位都是 1。

那么经过 & 计算后,hash 值 100 的高位全部被清零,低位则保持不变,并且一定是小于(n-1)的。

也就是说经过如此计算,通过 hash 值得到的数组下标绝对不会越界。

这里我提出两个问题:

1、数组大小可以为 17,或者 18 吗?

2、如果为了保证不越界为什么不直接用 % 计算取余数?

3、为什么不直接用 key 的 hashCode,而是使用经 spreed 方法加工后的 hash 值?

这几个问题是面试经常会问到的相关问题。我们一个个来解答。

4.1 数组大小必须为 2 的 n 次方

第一个问题的答案是数组大小必须为 2 的 n 次方,也就是 16、32、64…. 不能为其他值。

因为如果不是 2 的 n 次方,那么经过计算的数组下标会增大碰撞的几率,例如数组长度为 21,那么 n-1=20,对应的二进制为:

10100

那么 hash 值的二进制如果是 10000(十进制 16)、10010(十进制 18)、10001(十进制 17),和 10100 做 & 计算后,都是 10000,也就是都被映射到数组 16 这个下标上。这三个值会以链表的形式存储在数组 16 下标的位置。这显然不是我们想要的结果。

但如果数组长度 n 为 2 的 n 次方,2 进制的数值为 10,100,1000,10000……n-1 后对应二进制为 1,11,111,1111…… 这样和 hash 值低位 & 后,会保留原来 hash 值的低位数值,那么只要 hash 值的低位不一样,就不会发生碰撞。

其实如果数组长度为 2 的 n 次方,那么 (n - 1) & hash 等价于 hash% n。那么为什么不直接用 hash% n 呢?这是因为按位的操作效率会更高,经过我本地测试,& 计算速度大概是 % 操作的 50 倍左右。

所以 JDK 为了性能,而使用这种巧妙的算法,在确保元素均匀分布的同时,还保证了效率。

4.2 为什么不直接用 key 的 hashCode?

本来我们要分析 spreed 方法的代码,但是现在看起来这个方法好像并没有什么用处,直接用 key 的 hashCode 来定位哈希表的位置就可以了啊,为什么还要经过 spreed 方法的加工呢?

其实说到底还是为了减少碰撞的概率。我们先看看 spreed 方法中的代码做了什么事情:

1、h ^ (h >>> 16)

h >>> 16 的意思是把 h 的二进制数值向右移动 16 位。我们知道整形为 32 位,那么右移 16 位后,就是把高 16 位移到了低 16 位。而高 16 位清 0 了。

^ 为异或操作,二进制按位比较,如果相同则为 0,不同则为 1。这行代码的意思就是把高低 16 位做异或。如果两个 hashCode 值的低 16 位相同,但是高位不同,经过如此计算,低 16 位会变得不一样了。

为什么要把低位变得不一样呢?

这是由于哈希表数组长度 n 会是偏小的数值,那么进行 (n - 1) & hash 运算时,一直使用的是 hash 较低位的值。那么即使 hash 值不同,但如果低位相当,也会发生碰撞。而进行 h ^ (h >>> 16) 加工后的 hash 值,让 hashCode 高位的值也参与了哈希运算,因此减少了碰撞的概率。

2、(h ^ (h >>> 16)) & HASH_BITS

我们再看完整的代码,为何高位移到低位和原来低位做异或操作后,还需要和 HASH_BITS 这个常量做 & 计算呢?

HASH_BITS 这个常量的值为 0x7fffffff,转化为二进制为 0111 1111 1111 1111 1111 1111 1111 1111。

这个操作后会把最高位转为 0,其实就是消除了符号位,得到的都是正数。

这是因为负的 hashCode 在 ConcurrentHashMap 中有特殊的含义,因此我们需要得到一个正的 hashCode。

总结

通过以上分析我们已经清楚 ConcurrentHashMap 中是如何通过 Hash 值来映射数组位置的,这里面的算法设计确实十分的巧妙。可能平时我们编码用不到,但也要熟记于心,相信在面试中一定用得到。

本文作者|李一鸣

内容来源|慕课网,程序员的梦工厂

- END -

分类:

后端

标签:

Java

作者介绍

慕课君
V1