当前位置：首页 > news >正文

【八股文】基于源码聊聊ConcurrentHashmap的设计

news 来源：原创 2025/8/20 5:03:21

版本演进

jdk 1.7中是分段锁的设计，将哈希表划分为多个segment，每个段独立加锁，锁粒度为段级别。

操作需两次哈希，第一次定位段，第二次定位桶内链表。这种实现方式的缺点就是段数量固定，扩容复杂，且哈希计算成本高。

jdk1.8中进行了优化，改用CAS+synchronized。取消了segment的设计，将锁粒度进一步细化，改用synchronized仅对单个桶加锁。提升并发度。同时，通过CAS实现无锁读，无锁扩容及计数器更新等，减少锁竞争。

基于JDK8源码分析

基本结构

整体结构类似hashmap，数组+链表+红黑树

public class ConcurrentHashMap<K,V> extends AbstractMap<K,V>implements ConcurrentMap<K,V>, Serializable {// 哈希表数组transient volatile Node<K,V>[] table;// 扩容时使用的下一哈希表private transient volatile Node<K,V>[] nextTable;// 基础计数器，主要用于无竞争时private transient volatile long baseCount;// 表初始化和扩容控制private transient volatile int sizeCtl;// 扩容时的分割索引private transient volatile int transferIndex;// CAS 操作相关private static final sun.misc.Unsafe U;
}

关键内部类

static class Node<K,V> implements Map.Entry<K,V> {final int hash;final K key;volatile V val;volatile Node<K,V> next;// 构造方法和基本方法...
}

static final class TreeNode<K,V> extends Node<K,V> {TreeNode<K,V> parent;  // 父节点TreeNode<K,V> left;    // 左子节点TreeNode<K,V> right;   // 右子节点TreeNode<K,V> prev;    // 前驱节点boolean red;          // 颜色// 构造方法和树操作方法...
}

链表长度超过阈值(8)时转换为红黑树，提高查找效率

核心方法

PUT方法

public V put(K key, V value) {return putVal(key, value, false);
}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;if (tab == null || (n = tab.length) == 0)tab = initTable();  // 初始化表else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {// 使用CAS尝试无锁插入if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value)))break;  // 插入成功则退出循环}else if ((fh = f.hash) == MOVED)tab = helpTransfer(tab, f);  // 协助扩容else {V oldVal = null;synchronized (f) {  // 锁住链表头节点if (tabAt(tab, i) == f) {if (fh >= 0) {  // 链表// 遍历链表...}else if (f instanceof TreeBin) {  // 红黑树// 树操作...}}}if (binCount != 0) {if (binCount >= TREEIFY_THRESHOLD)treeifyBin(tab, i);  // 转换为红黑树break;}}}addCount(1L, binCount);  // 更新计数return null;
}

哈希计算 - spread 方法

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

使用高低位异或来减少哈希冲突

原子获取桶 - tabAt 方法

static final <K,V> Node<K,V> tabAt(Node<K,V>[] tab, int i) {return (Node<K,V>)U.getObjectVolatile(tab, ((long)i << ASHIFT) + ABASE);
}

使用 Unsafe 的 volatile 读保证可见性，使用 Unsafe 的 volatile 读保证可见性

CAS 插入 - casTabAt 方法

static final <K,V> boolean casTabAt(Node<K,V>[] tab, int i,Node<K,V> c, Node<K,V> v) {return U.compareAndSwapObject(tab, ((long)i << ASHIFT) + ABASE, c, v);
}

典型的 CAS 操作，仅在预期当前值为 c 时才更新为 v

初始化表 - initTable

private final Node<K,V>[] initTable() {while ((tab = table) == null || tab.length == 0) {if ((sc = sizeCtl) < 0) // 其他线程正在初始化Thread.yield(); // 让出CPUelse if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) { // CAS抢锁try {// 双重检查if ((tab = table) == null || tab.length == 0) {int n = (sc > 0) ? sc : DEFAULT_CAPACITY;table = tab = new Node[n];sc = n - (n >>> 2); // 0.75负载因子}} finally {sizeCtl = sc; // 释放锁}break;}}return tab;
}

协助扩容 - helpTransfer

final Node<K,V>[] helpTransfer(Node<K,V>[] tab, Node<K,V> f) {Node<K,V>[] nextTab; int sc;if (tab != null && (f instanceof ForwardingNode) &&(nextTab = ((ForwardingNode<K,V>)f).nextTable) != null) {// 计算扩容戳int rs = resizeStamp(tab.length);while (nextTab == nextTable && table == tab &&(sc = sizeCtl) < 0) {// 检查是否可以参与扩容if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||sc == rs + MAX_RESIZERS || transferIndex <= 0)break;if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1)) {transfer(tab, nextTab); // 实际扩容转移break;}}return nextTab;}return table;
}

树化 - treeifyBin

private final void treeifyBin(Node<K,V>[] tab, int index) {Node<K,V> b; int n, sc;if (tab != null) {// 如果表太小（<64），优先扩容而非树化if ((n = tab.length) < MIN_TREEIFY_CAPACITY)tryPresize(n << 1);else if ((b = tabAt(tab, index)) != null && b.hash >= 0) {synchronized (b) {if (tabAt(tab, index) == b) {TreeNode<K,V> hd = null, tl = null;// 将链表转换为TreeNode链表for (Node<K,V> e = b; e != null; e = e.next) {TreeNode<K,V> p =new TreeNode<K,V>(e.hash, e.key, e.val,null, null);if ((p.prev = tl) == null)hd = p;elsetl.next = p;tl = p;}// 创建TreeBin并替换链表setTabAt(tab, index, new TreeBin<K,V>(hd));}}}}
}

GET方法

public V get(Object key) {Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;int h = spread(key.hashCode());  // 计算哈希if ((tab = table) != null && (n = tab.length) > 0 &&(e = tabAt(tab, (n - 1) & h)) != null) {if ((eh = e.hash) == h) {if ((ek = e.key) == key || (ek != null && key.equals(ek)))return e.val;  // 直接命中}else if (eh < 0)  // 红黑树或ForwardingNodereturn (p = e.find(h, key)) != null ? p.val : null;while ((e = e.next) != null) {  // 遍历链表if (e.hash == h &&((ek = e.key) == key || (ek != null && key.equals(ek))))return e.val;}}return null;
}

讲讲这里eh<0这块特殊节点处理的部分

不同的节点类型对应不同的find实现：

-1，表示转发节点，在扩容时出现，find会去新表中查找
-2，表示红黑树根节点，在红黑树中查找
-3，表示保留节点，返回null

扩容时候的读操作，是先访问旧表，遇到转发节点，转向新表查询，返回结果。

这样的好处是可以实现无锁迁移，读操作不用等待扩容完成，也不会看到中间状态。

总结

JDK8中对ConcurrentHashmap还是做了比较多的优化的，设计上充分体现了“读无锁，写最小化锁”的并发优化思想。

【八股文】基于源码聊聊ConcurrentHashmap的设计

版本演进 jdk 1.7中是分段锁的设计，将哈希表划分为多个segment，每个段独立加锁，锁粒度为段级别。操作需两次哈希，第一次定位段，第二次定位桶内链表。这种实现方式的缺点就是段数量固定，扩容复杂&#xf…...

编程日记 2025/8/20 5:03:21

Mysql--基础知识点--93--两阶段提交

1 两阶段提交以update语句的具体执行过程为例： 具体更新一条记录 UPDATE t_user SET name ‘xiaolin’ WHERE id 1;的流程如下： 1.执行器负责具体执行，会调用存储引擎的接口，通过主键索引树搜索获取 id 1 这一行记录&#…...

编程日记 2025/8/20 19:25:51

数字化招标采购系统怎么让招采协同更高效？

招标采购领域的数智化转型正在引发行业革命性变革。从传统线下模式到全流程电子化，再到当前数智化阶段的超时空协同，行业的演进路径清晰展现了技术与管理的深度融合。郑州信源信息数智化招采系统作为行业标杆，其创新实践为未来协同工作方式的…...

编程日记 2025/8/20 19:25:22

池塘计数（BFS）

题目描述由于最近的降雨，光头强的田地里的各个地方都积水了，用 NM(1≤N≤100；1≤M≤100)NM(1≤N≤100；1≤M≤100) 的正方形的矩形表示。每个广场都有水 W 或旱地 .。光头强想知道他的田地里形成了多少池塘。池塘是指一组相邻的有…...

编程日记 2025/8/20 10:55:06

《Science》观点解读：AI无法创造真正的智能体（AI Agent）

无论是想要学习人工智能当做主业营收，还是像我一样作为开发工程师但依然要运用这个颠覆开发的时代宠儿，都有必要了解、学习一下人工智能。近期发现了一个巨牛的人工智能学习网站，通俗易懂，风趣幽默，入行门槛低&#x…...

编程日记 2025/8/20 19:27:26

从零开始学A2A四：A2A 协议的安全性与多模态支持

文章目录 A2A 协议的安全性与多模态支持一、A2A 协议安全机制1. 认证机制2. 授权机制3. 数据加密二、多模态交互支持1. 文本交互2. 音频支持3. 视频与图像处理4. 复合数据格式三、安全与多模态最佳实践1. 安全性实践2. 多模态实践四、与 MCP 的对比1. 安全机制对比2. 多模态…...

编程日记 2025/8/19 23:53:48

一种大位宽加减法器的时序优化

平台：vivado2018.3 芯片：xc7a100tfgg484-2 (active) 在FPGA中实现超高位宽加减法器（如256）时，时序收敛常成为瓶颈。由于进位链（Carry Chain）跨越多级逻辑单元，关键路径延迟会随位宽…...

编程日记 2025/8/20 19:25:51

【专业解读：Semantic Kernel（SK）】大语言模型与传统编程的桥梁

目录 Start:什么是Semantic Kernel？ 一、Semantic Kernel的本质：AI时代的操作系统内核 1.1 重新定义LLM的应用边界 1.2 技术定位对比二、SK框架的六大核心组件与技术实现 2.1 内核（Kernel）：智能任务调度中心 2…...

编程日记 2025/8/20 2:21:24

InfiniBand与RoCEv2负载均衡机制的技术梳理与优化实践

AI技术的高速迭代正驱动全球算力格局进入全新纪元。据IDC预测，未来五年中国智能算力规模将以超50%的年复合增长率爆发式扩张，数据中心全面迈入“智能算力时代”。然而，海量AI训练、实时推理等高并发场景对底层网络提出了更严苛的挑战——超大…...

编程日记 2025/8/20 7:36:31

Vue与React组件化设计对比

组件化是现代前端开发的核心思想之一，而Vue和React作为两大主流框架，在组件化设计上既有相似之处，也存在显著差异。本文将从语法设计、数据管理、组件通信、性能优化、生态系统等多个方向，结合实例详细对比两者的特点。一、模板…...

编程日记 2025/8/20 19:33:39

UE中通过AAIController::MoveTo函数巡逻至目标点后没法正常更新巡逻目标点

敌人巡逻的逻辑如下： 敌人在游戏一开始的时候就通过moveto函数先前往首先设定的patroltarget目标，在距离patroltarget距离为patroradius（200unit)之内时就可以通过checkpatroltarget函数更新新的patroltarget目标，随后前往新的pat…...

编程日记 2025/8/20 19:29:15

Python-细节知识点range函数的详解

在 Python 中，range 是一个内置函数，用于生成一个不可变的整数序列，通常用于控制循环次数或生成数值范围。以下是详细说明： 基本语法 range(stop) # 生成 [0, stop) 的整数，步长为1 range(start, stop) …...

编程日记 2025/8/20 19:25:23

git rebase的使用

我的使用 git checkout feature # 本地分支 git pull origin main --rebase # 目标分支 git pull origin feature --rebase git push origin featuregit rebase 是 Git 中用于重写提交历史的强大工具，可将分支的提交移动到新的基点上，使历史更线性。以…...

编程日记 2025/8/20 18:37:02

CMake Error at build/_deps/glog-src/CMakeLists.txt:1 (cmake_minimum_required):

这个错误提示意思是你当前系统上安装的 CMake 版本过低，不满足项目的要求。根据错误信息： CMake Error at build/_deps/glog-src/CMakeLists.txt:1 (cmake_minimum_required): CMake 3.22 or higher is required. You are running version 3.16.3 项目…...

编程日记 2025/8/20 19:31:16

MATLAB 控制系统设计与仿真 - 34

多变量系统知识回顾 - MIMO system 这一章对深入理解多变量系统以及鲁棒分析至关重要首先，对于如下系统： 当G(s)为单输入，单输出系统时： 如果： 则： 所以当G(s)为MIMO时，例如2X2时&#xff…...

编程日记 2025/8/20 19:32:16

【Unity】JSON数据的存取

这段代码的结构是为了实现数据的封装和管理，特别是在 Unity 中保存和加载玩家数据时。以下是对代码设计的逐步解释： 1. PlayerCoin 类 PlayerCoin 是一个简单的数据类，用于表示单个玩家的硬币信息。它包含以下字段： count&…...

编程日记 2025/8/20 19:32:14

利用 Java 爬虫按关键字搜索淘宝商品

在电商领域，通过关键字搜索商品是常见的需求。淘宝作为国内知名的电商平台，提供了丰富的商品搜索功能。本文将详细介绍如何使用 Java 爬虫技术按关键字搜索淘宝商品，并获取搜索结果的详细信息。一、准备工作 1. 注册淘宝开放平台账号要使…...

编程日记 2025/8/20 11:49:23

【C】初阶数据结构11 -- 选择排序

本篇文章主要讲解经典排序算法 -- 选择排序目录 1 算法思想 2 代码 3 时间复杂度与空间复杂度分析 1） 时间复杂度 2） 空间复杂度 1 算法思想选择排序是一种在一段区间里面选择最小的元素和最大的元素的一种排序算法。假设这里排升序&#…...

编程日记 2025/8/20 7:18:13

【Semantic Kernel核心组件】Plugin：连接AI与业务逻辑的桥梁

目录一、Plugin是什么？为什么它是SK的核心？ 一、Plugin的核心机制与Python实现 1. 插件类型：语义函数与本地函数语义函数（Semantic Function） 本地函数（Native Function） 2. Plugin的注…...

编程日记 2025/8/20 8:33:50

《基于神经网络实现手写数字分类》

《基于神经网络实现手写数字分类》一、主要内容： 1、通过B站陈云霁老师的网课，配合书本资料，了解神经网络的基本组成和数学原理。 2、申请云平台搭建实验环境 3、基于5个不同的实验模块逐步理解实验操作步骤，并实现不同模块代码…...

编程日记 2025/8/20 19:27:23

车载诊断架构 --- 车载诊断概念的深度解读

我是穿拖鞋的汉子，魔都中坚持长期主义的汽车电子工程师。老规矩，分享一段喜欢的文字，避免自己成为高知识低文化的工程师：周末洗了一个澡，换了一身衣服，出了门却不知道去哪儿，不知道去找谁，漫无目的走着，大概这就是成年人最深的孤独吧! 旧人不知我近况，新人不知我过…...

编程日记 2025/8/20 19:33:39

四、探索LangChain：连接语言模型与外部世界的桥梁

一、什么是 LangChain LangChain 是一个开源的软件框架，旨在帮助开发者高效构建和部署基于**大型语言模型（LLM）**的应用程序。它通过提供一系列工具、组件和接口，简化了从模型调用、提示工程到复杂应用开发的全流程，使得开发者能够快速将 LLM 集成到实际场景中。 1. 核心…...

编程日记 2025/8/20 19:32:16

LangChain4j中的Chat与语言模型API详解：构建高效对话系统的利器

LangChain4j中的Chat与语言模型API详解：构建高效对话系统的利器引言：大模型时代的开发利器在人工智能快速发展的今天，大型语言模型（LLM）已成为构建智能应用的核心组件。LangChain4j作为Java生态中领先的LLM集成框架…...

编程日记 2025/8/20 19:32:51

C++中const与constexpr的区别

在C中，const和constexpr都用于定义常量，但它们的用途和行为有显著区别： ### 1. **初始化时机** - **const**：表示变量是只读的，但其值可以在**编译时或运行时**初始化。 cpp const int a 5; // 编译…...

编程日记 2025/8/20 19:29:14

长亭2月公开赛Web-ssrfme

环境部署拉取环境报错： 可以尝试拉取一下ubuntu:16.04，看是否能拉取成功将wersion："3"删掉我拉去成功之后，再去拉取环境，成功！ 访问环境测试ssrf 源码 <?php highlight_file(__file__…...

编程日记 2025/8/20 19:12:10

AI日报 - 2025年4月18日

🌟 今日概览(60秒速览) ▎🤖 AGI探讨 | 专家激辩AGI定义与实现时间点，Causal AI被视为关键一步，o3模型预测2027年实现引关注。 Causal AI强调因果关系而非模式；专家清单推荐不同模型适用场景；AGI定义及何时…...

编程日记 2025/8/20 19:31:16

Spring IoC 详解

在 Spring IoC& DI 详解中对 IoC已经有了介绍，下面对 IoC 进行详细介绍。 IoC，即控制反转，在之前我们编写程序的时候，我们都是自己 new 出来一个对象，然后自己去管理这个对象，但是这有时候有些麻烦&a…...

编程日记 2025/8/20 19:24:02

oracle查询当前用户所有字段和表

在 Oracle 数据库中，可以通过查询数据字典视图来获取某个表的字段（列）信息。以下是常用的查询方法： 查询当前用户下的表字段如果您想查看当前用户下某个表的字段信息，可以查询 USER_TAB_COLUMNS 视图： SE…...

编程日记 2025/8/20 19:24:00

ACL(访问控制列表）

ACL(访问控制列表） 1、基础内容访问控制列表ACL(Access ControlList)是由一条或多条规则组成的集合。所谓规则，是指描述报文匹配条件的判断语句，这些条件可以是报文的源地址、目的地址、端口号等。通过一系列规则来匹配报文，如…...

编程日记 2025/8/20 19:24:01

1.建堆（向上调整） 1.1大堆 #include<stdio.h> void swap(int *p1,int *p2) {int temp *p1;*p1 *p2;*p2 temp; } void Ajustup(int *a,int child)//向上调整 {int parent (child - 1) / 2;while (child > 0){if (a[child] > a[parent]…...

编程日记 2025/8/20 19:24:03

在Linux下安装Gitlab

在Cenos7下安装GitLab 在ssh下安装官方安装文档:https://gitlab.cn/install/?versionce 1. 使用阿里YUM 镜像云下载 https://mirrors.aliyun.com/repo/Centos-7.repo替换 /etc/yum.repos.d/CentOS-Base.repo在目录/etc/yum.repos.d/下执行如下命令： curl …...

编程日记 2025/8/20 19:32:49

【算法】快速排序、归并排序（非递归版）

目录一、快速排序（非递归） 1.原理 2.实现 2.1 stack 2.2 partition(array,left,right) 2.3 pivot - 1 > left 二、归并排序（非递归） 1.原理 2.实现 2.1 gap 2.1.1 i 2*gap 2.1.2 gap * 2 2.1.3 gap < array.…...

编程日记 2025/8/20 19:25:49

如何自学机器学习？零基础到实战的完整路径

机器学习作为人工智能的核心领域，已成为技术人必备的硬实力。本文为自学者梳理出一条从零基础到项目落地的系统学习路线，涵盖知识框架、工具链与实战技巧。一、构建三大基础模块（1-2个月） 数学基石：线性代数重点掌握…...

编程日记 2025/8/20 19:30:41

PHP开发环境搭建(Hbuider+phpstudy)

目录 1.Hbuider下载 Hbuider的网址 2.Hbuilder的安装 1-首先找到刚刚下载的安装包 2-然后进行解压 3-进入解压后的文件夹HBuilderX，找到HBuilderX这一项，双击打开 4-选择你喜欢的风格,任意选择一个就可以了 5-选择你选快捷键的方案 6-点击开始体验就可了…...

编程日记 2025/8/20 19:26:22

【4.1.-4.20学习周报】

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档文章目录摘要Abstract一、方法介绍1.1HippoRAG 1.2HippoRAG2二、实验2.1实验概况2.2实验代码2.3实验结果总结摘要本博客介绍了论文《From RAG to Memory: Non-Parametri…...

编程日记 2025/8/20 19:29:14

vim笔记

vim三种模式切换命令常用复制粘贴...

编程日记 2025/8/20 19:28:19

【JAVA】基础知识“抽象类”详解，从入门到理解~

目录 1. 抽象类 1.1 什么是抽象类❓ 1.2 为什么需要抽象类❓ 1.3 抽象类语法 1.4 抽象类特征 ① 抽象类是被abstract修饰的 ② 被abstract修饰的方法称为抽象方法，这个方法可以没有具体的实现 ③ 当一个类中含有抽象方法的时候，该类必须使用abst…...

编程日记 2025/8/20 19:27:51

docker 启动mysql9认证失败

docker compose 启动mysql9认证失败随着mysql更新到了9版本，在docker中相较于8减少了一些体积，很吸引人尝试， 但是在使用原本的配置文件拉起mysql，连接时却提示权限认证失败 1045 - Access denied for user root172.18.0.1 (…...

编程日记 2025/8/20 19:30:06

【Axure绘制原型】图片切割、交互动效、热区、动态面板、元件显示隐藏、表单元件、表格、内联框架

切割功能：将图片切成多部分。通过移动鼠标可以调整两条虚线的位置，点击。虚线相当于切割刀，被虚线分离的部分将变成单独的图切割后的图片： 交互交互动效的构成： 目标：谁触发交互（元…...

编程日记 2025/8/20 19:27:24

DeepSeek智能时空数据分析（一）：筛选特定空间范围内的POI数据

时空数据分析很有用，但是GIS/时空数据库技术门槛太高时空数据分析在优化业务运营中至关重要，尤其在数据驱动决策的当下，其价值正随大模型时代的到来进一步凸显。然而，三大挑战仍制约其发展：技术门槛高，需…...

编程日记 2025/8/20 19:30:41

使用mybatisPlus自带的分页方法+xml实现数据分页

：因为需要实现多表关联分页，原本想的是直接使用selectpagehelper，但是pagehelper只对xml文件生效；后面发现可以直接使用mybatisplus自带的分页，不依靠pagehelper实现多表关联分页； 实现类：关键…...

编程日记 2025/8/20 15:27:52

第六节：React Hooks进阶篇-自定义Hook设计

实战题：实现一个useWindowSize或useFetch 自定义 Hook 设计实战：useWindowSize 与 useFetch 实现详解一、useWindowSize：实时监听窗口尺寸 1. 基础实现（TypeScript 版） import { useState, useEffect } from react…...

编程日记 2025/8/20 19:32:48