ConcurrentHashMap 源码分析(一)

news/2024/9/23 18:29:12/

一、简述

本文对 ConcurrentHashMap#put() 源码进行分析。

二、源码概览

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

上面是 ConcurrentHashMap#put() 的源码,我们可以看出其核心逻辑在 putVal() 方法中。

java">final V putVal(K key, V value, boolean onlyIfAbsent) {if (key == null || value == null) throw new NullPointerException();int hash = spread(key.hashCode());int binCount = 0;for (Node<K,V>[] tab = table;;) {Node<K,V> f; int n, i, fh; K fk; V fv;if (tab == null || (n = tab.length) == 0)tab = initTable();else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value)))break;                   // no lock when adding to empty bin}else if ((fh = f.hash) == MOVED)tab = helpTransfer(tab, f);else if (onlyIfAbsent // check first node without acquiring lock&& fh == hash&& ((fk = f.key) == key || (fk != null && key.equals(fk)))&& (fv = f.val) != null)return fv;else {V oldVal = null;synchronized (f) {if (tabAt(tab, i) == f) {if (fh >= 0) {binCount = 1;for (Node<K,V> e = f;; ++binCount) {K ek;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;if ((e = e.next) == null) {pred.next = new Node<K,V>(hash, key, value);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;}}else if (f instanceof ReservationNode)throw new IllegalStateException("Recursive update");}}if (binCount != 0) {if (binCount >= TREEIFY_THRESHOLD)treeifyBin(tab, i);if (oldVal != null)return oldVal;break;}}}addCount(1L, binCount);return null;
}

上面是 ConcurrentHashMap#putVal() 的源码,有兴趣的小伙伴可以先试着读一下。

三、核心流程分析

java">final V putVal(K key, V value, boolean onlyIfAbsent) {// 检查 key 和 value 是否为 null,如果是则抛出 NullPointerException 异常if (key == null || value == null) throw new NullPointerException();// 调用 spread 方法将 key 的哈希码进行扩散,得到一个散列值 hashint hash = spread(key.hashCode());int binCount = 0;// 开启循环for (Node<K,V>[] tab = table;;) {// 定义一些变量Node<K,V> f; int n, i, fh; K fk; V fv;// 检查当前的哈希表(tab)是否为空或长度为 0if (tab == null || (n = tab.length) == 0)// 调用 initTable() 方法初始化哈希表tab = initTable();// 如果当前槽位(f = tabAt(tab, i = (n - 1) & hash))为空else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {// 使用 CAS 操作尝试在该槽位上添加新的节点if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value)))// 成功则跳出循环break;                   // no lock when adding to empty bin}// 如果当前槽位的哈希值为 MOVEDelse if ((fh = f.hash) == MOVED)// 帮助其进行哈希表的转移操作tab = helpTransfer(tab, f);// 如果 onlyIfAbsent 为 true,并且当前槽位的键与要添加的键相同else if (onlyIfAbsent // check first node without acquiring lock&& fh == hash&& ((fk = f.key) == key || (fk != null && key.equals(fk)))&& (fv = f.val) != null)// 直接返回当前槽位的值return fv;else {V oldVal = null;// 对当前槽位的节点进行加锁synchronized (f) {// 暂时省略 synchronized 中的内容}// 检查 binCount 是否不为 0if (binCount != 0) {// 如果 binCount 的值大于或等于 TREEIFY_THRESHOLD(默认值为8)if (binCount >= TREEIFY_THRESHOLD)// 将当前的链表结构转化为红黑树结构 treeifyBin(tab, i);// 如果 oldVal 不为 nullif (oldVal != null)// 直接返回 oldValreturn oldVal;// 跳出循环break;}}}// 调用 addCount 方法增加元素的数量addCount(1L, binCount);return null;
}

从上面的源码中可以分析出,ConcurrentHashMap#putVal() 的核心逻辑为:

在这里插入图片描述

  1. 首先进行空值检查,如果键或值为 null,那么抛出 NullPointerException
  2. 使用 spread() 方法,计算 Hash 值
  3. 开启循环,首先检测 Hash 表的状态是否已完成初始化
  4. 未完成初始化,使用 initTable() 方法完成初始化
  5. 若 Hash 表已完成初始化,则检查需要插入的槽位是否为空
  6. 若槽位为空,则采用 CAS 插入新节点,新节点插入成功退出循环
  7. 若槽位不为空,判断插入槽位是否需要移动
  8. 若需要移动,使用 helpTransfer() 方法实现槽位转移(扩容)
  9. 若不需要移动,则检查当前槽位的键是否与插入的键相同
  10. 若键相同,直接返回当前槽位的值,退出循环
  11. 若键不同,发生 Hash 冲突,进入 synchronized 代码块执行解决 Hash 冲突的逻辑

四、Hash 冲突流程分析

java">// 之前 synchronized 省略的内容
// 对哈希桶的节点加锁
synchronized (f) {// 检查当前的槽位是否改变if (tabAt(tab, i) == f) {// 如果当前节点是链表节点if (fh >= 0) {binCount = 1;// 遍历链表for (Node<K,V> e = f;; ++binCount) {K ek;// 如果找到了与添加的键相同的节点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;// 如果找到链表末尾依旧没有找到if ((e = e.next) == null) {// 添加一个新的节点pred.next = new Node<K,V>(hash, key, value);break;}}}// 如果当前节点是红黑树节点else if (f instanceof TreeBin) {Node<K,V> p;binCount = 2;// 调用 putTreeVal() 方法if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,value)) != null) {oldVal = p.val;if (!onlyIfAbsent)// 如果键已存在则更新旧值p.val = value;}}// 如果当前节点是 ReservationNodeelse if (f instanceof ReservationNode)// 抛出 IllegalStateException 异常throw new IllegalStateException("Recursive update");}
}

上面是 ConcurrentHashMap#putVal() 方法中发生 Hash 冲突时的源码。

在这里插入图片描述

  1. 首先,将 Hash 桶中的节点加 synchronized
  2. 判断槽位是否改变
  3. 槽位未改变,检查是否为链表节点
  4. 若是链表节点,则遍历链表,键已存在则更新值,键不存在则新增节点
  5. 若是红黑树节点,则调用红黑树的 putTreeVal() 方法,键已存在则更新值,键不存在则新增节点
  6. 若是 ReservationNode 则抛出 IllegalStateException 异常

五、FAQ

5.1 helpTransfer() 方法是什么

helpTransfer() 方法的主要工作是检查是否满足扩容条件,如果满足,则协助进行扩容操作。具体来说,它会检查当前的哈希表是否正在进行扩容操作,如果是,则帮助完成扩容;如果不是,则直接返回当前的哈希表。

5.2 Hash 冲突源码中为什么需要判断槽位是否改变

if (tabAt(tab, i) == f) 的目的是为了检查在进入同步块之后,当前槽位的节点是否发生了变化。

在多线程环境下,当一个线程获取到锁并进入同步块时,其他线程可能已经修改了哈希表的状态。因此,在进行节点操作之前,需要再次检查当前槽位的节点是否与预期的节点相同。

如果当前槽位的节点与预期的节点不同,那么说明在这个线程获取锁的过程中,其他线程已经修改了哈希表的状态。在这种情况下,当前线程应该跳过后续的操作,因为它们可能基于错误的状态。
这是一种常见的并发编程技巧,被称为"双重检查锁"(Double-Checked Locking)。它可以确保在多线程环境下的正确性和效率。

5.3 ReservationNode 是什么

在 ConcurrentHashMap 中,ReservationNode 是一个特殊类型的节点,是一个临时的占位符,不应该出现在正常的操作中。如果出现了,那么可能是发生了递归更新

往期推荐

  1. IoC 思想简单而深邃
  2. ThreadLocal
  3. 终端的颜值担当-WindTerm
  4. Spring 三级缓存
  5. RBAC 权限设计(二)

http://www.ppmy.cn/news/1429221.html

相关文章

Jupyter的下载与安装

1.下载&#xff1a; 在anaconda的指定环境中 conda install nb_conda_kernels 2.打开 在anaconda指定环境中使用命令&#xff1a; jupyter notebook 3.输入指令后&#xff0c;会显示如下&#xff0c;根据显示地址打开 3. 在右边的new按钮处&#xff0c;选择相应环境&…

Vitis HLS 学习笔记--HLS优化指令示例-目录

目录 1. 示例集合概述 2. 内容分析 2.1 array_partition 2.2 bind_op_storage 2.3 burst_rw 2.4 critical_path 2.5 custom_datatype 2.6 dataflow_stream 2.7 dataflow_stream_array 2.8 dependence_inter 2.9 gmem_2banks 2.10 kernel_chain 2.11 lmem_2rw 2.1…

PTA 6-13 表尾插入法构造链表

本题实现链表的构造&#xff0c;采用表尾插入法构造链表&#xff0c;输出表中所有元素。 函数接口定义&#xff1a; 函数接口&#xff1a; ptr creat( )&#xff1b;//构造链表 void output(ptr p);//输出链表元素其中p 是用户传入的参数。creat函数返回链表的头指针&#xf…

第65天:API攻防-接口安全WebPackRESTSOAPWSDLWebService

目录 思维导图 前置知识 案例一&#xff1a;WebService 类-Wsdl&ReadyAPI-SQL 注入 案例二&#xff1a;SOAP 类-Swagger&SoapUI&EXP-信息泄露 案例三&#xff1a;HTTP 类-WebPack&PackerFuzzer-信息泄露 思维导图 前置知识 RPC接口: 登录游戏时候登录账号…

在RISC-V64架构的CV1811C开发板上应用perf工具进行多线程程序性能分析及火焰图调试

CV1811C环境编译 SDK目录结构 . ├── build // 编译目录,存放编译脚本以及各board差异化配置 ├── buildroot-2021.05 // buildroot开源工具 ├── freertos // freertos系统 ├── fsbl // fsbl启动固件,prebuilt形式存在…

如何免费用 Llama 3 70B 帮你做数据分析与可视化?

快速、强悍且免费&#xff0c;你还等啥&#xff1f; Llama 3 的发布&#xff0c;真可谓一石激起千层浪。前两天&#xff0c;许多人还对「闭源模型能力普遍大于开源模型」的论断表示赞同。但是&#xff0c;最新的 LLM 排行榜&#xff08;https://chat.lmsys.org/?leaderboard&a…

Java离线视频提取音频+音频提取文案

需引入依赖javacv、vosk相关依赖&#xff0c; 至于javacv依赖&#xff0c;网上有很多缩减方案&#xff0c;注释部分是可行的缩减方案&#xff0c;至于视频提取视频这里无需安装ffmpeg&#xff0c;只需引入依赖。而vosk需要下载模型方可使用&#xff0c;并且下载比较慢&#xf…

【设计模式】单例模式|最常用的设计模式

写在前面 单例模式是最常用的设计模式之一&#xff0c;虽然简单&#xff0c;但是还是有一些小坑点需要注意。本文介绍单例模式并使用go语言实现一遍单例模式。 单例模式介绍 简介 单例模式保证一个类仅有一个实例&#xff0c;并提供一个访问它的全局访问点。 使用场景&#…