0

0

详解ThreadLocalMap的Hash冲突解决方式_线性探测法与快速清理逻辑

P粉602998670

P粉602998670

发布时间:2026-02-11 14:20:56

|

968人浏览过

|

来源于php中文网

原创

ThreadLocalMap采用线性探测而非链地址法,冲突时向后顺序查找空槽或匹配key,不扩容、不拉链;get/set过程中顺路清理stale entry,但仅限探测路径且不绕回数组开头,依赖主动remove防止内存泄漏。

详解threadlocalmap的hash冲突解决方式_线性探测法与快速清理逻辑

ThreadLocalMap 用的是线性探测,不是链地址法

很多人看到 ThreadLocalMap 内部是数组 + Entry 数组,下意识以为它像 HashMap 那样用链表或红黑树处理哈希冲突。其实不是——ThreadLocalMap 采用纯线性探测(linear probing),冲突时直接往后找空槽,不拉链、不扩容、不建树。

这意味着:一旦发生冲突,后续 get / set 都要顺序扫描,直到遇到 null 或命中 key。性能退化明显,尤其在大量 ThreadLocal 被泄漏或未及时 remove() 的场景下。

  • set() 时若目标 slot 已被占用,从该位置开始向后遍历,跳过已失效的 Entry(key == null),直到找到空位或 key 相等的 slot
  • get() 时同样线性查找,但只在 key 相等或遇到 null 时停止;中间遇到的 stale entry(key == null)会被顺手清理
  • 没有负载因子控制,也不自动 rehash,全靠调用方主动 remove() 或触发探测过程中的“快速清理”逻辑

stale entry 的快速清理不是“额外功能”,而是探测路径上的副作用

所谓“快速清理”,本质是在 get()set()remove() 过程中,只要线性探测路过 Entry 且其 key == null,就立即执行 expungeStaleEntry(int staleSlot) 清理该槽,并把后面连续的有效 entry 往前挪——避免探测链断裂或无效占位。

这个逻辑不保证全覆盖,只清理探测路径上碰到的 stale entry。如果某个 stale entry 始终没被路过(比如它卡在长探测链中间,而后续操作都从别处开始),就不会被清掉。

  • 清理动作只发生在当前探测路径上,不会全表扫描
  • expungeStaleEntry() 会把从 staleSlot 开始向后所有非 null key 的 Entry 重新 hash 定位,填回更靠近原始位置的地方,压缩探测距离
  • 如果清理过程中又发现新的 stale entry,也会一并处理,形成有限深度的“清理链”,但不会递归到底

为什么不用开放寻址里的二次哈希或双重散列?

因为 ThreadLocalMap 的 key 是 ThreadLocal 实例,本身已具备良好散列分布(ThreadLocalthreadLocalHashCode 是每次 new 时原子递增生成的),冲突概率低;加上实际使用中单个线程的 ThreadLocal 数量通常不多(几十以内),线性探测足够高效,也省去了维护多套 hash 函数的复杂度。

Flowith
Flowith

一款GPT4驱动的节点式 AI 创作工具

下载

更重要的是:线性探测让清理逻辑可嵌入到日常读写路径中,而二次哈希会让 stale entry 散布更随机,无法在一次探测中连带清理。

  • ThreadLocal 自带的 nextHashCode 是静态原子变量,每次构造递增,天然避免同线程内 key 的哈希聚集
  • 数组长度固定为 2 的幂,hash & (len - 1) 快速定位,配合线性探测,整体实现极轻量
  • 不支持并发修改,所以无需考虑多线程下探测路径不一致的问题,简化了清理前提条件

容易被忽略的清理边界:probe 超出数组长度后不 wrap-around

ThreadLocalMap 的线性探测 **不会绕回数组开头**。它的探测范围是从初始 hash 位置开始,一路向后,直到遇到 null 槽为止。也就是说,数组末尾的冲突只能往末尾堆,前面空着也没用。

这导致两个后果:一是尾部容易形成“拥堵区”,二是清理 stale entry 时,expungeStaleEntry() 也只向后扫描,不会跨到开头去搬移元素。

  • 探测循环终止条件是 entry == null,不是 index == table.length
  • 如果一个 stale entry 后面全是有效 entry,它可能永远卡在那里,除非后续写操作正好从它前面某个位置出发并一路探到它
  • 这也是为什么长期运行的线程(如线程池中的 worker)必须显式调用 ThreadLocal.remove(),不能只依赖自动清理

事情说清了就结束。

本站声明:本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn

热门AI工具

更多
DeepSeek
DeepSeek

幻方量化公司旗下的开源大模型平台

豆包大模型
豆包大模型

字节跳动自主研发的一系列大型语言模型

通义千问
通义千问

阿里巴巴推出的全能AI助手

腾讯元宝
腾讯元宝

腾讯混元平台推出的AI助手

文心一言
文心一言

文心一言是百度开发的AI聊天机器人,通过对话可以生成各种形式的内容。

讯飞写作
讯飞写作

基于讯飞星火大模型的AI写作工具,可以快速生成新闻稿件、品宣文案、工作总结、心得体会等各种文文稿

即梦AI
即梦AI

一站式AI创作平台,免费AI图片和视频生成。

ChatGPT
ChatGPT

最最强大的AI聊天机器人程序,ChatGPT不单是聊天机器人,还能进行撰写邮件、视频脚本、文案、翻译、代码等任务。

相关专题

更多
c语言中null和NULL的区别
c语言中null和NULL的区别

c语言中null和NULL的区别是:null是C语言中的一个宏定义,通常用来表示一个空指针,可以用于初始化指针变量,或者在条件语句中判断指针是否为空;NULL是C语言中的一个预定义常量,通常用来表示一个空值,用于表示一个空的指针、空的指针数组或者空的结构体指针。

243

2023.09.22

java中null的用法
java中null的用法

在Java中,null表示一个引用类型的变量不指向任何对象。可以将null赋值给任何引用类型的变量,包括类、接口、数组、字符串等。想了解更多null的相关内容,可以阅读本专题下面的文章。

665

2024.03.01

string转int
string转int

在编程中,我们经常会遇到需要将字符串(str)转换为整数(int)的情况。这可能是因为我们需要对字符串进行数值计算,或者需要将用户输入的字符串转换为整数进行处理。php中文网给大家带来了相关的教程以及文章,欢迎大家前来学习阅读。

688

2023.08.02

int占多少字节
int占多少字节

int占4个字节,意味着一个int变量可以存储范围在-2,147,483,648到2,147,483,647之间的整数值,在某些情况下也可能是2个字节或8个字节,int是一种常用的数据类型,用于表示整数,需要根据具体情况选择合适的数据类型,以确保程序的正确性和性能。本专题为大家提供相关的文章、下载、课程内容,供大家免费下载体验。

557

2024.08.29

c++怎么把double转成int
c++怎么把double转成int

本专题整合了 c++ double相关教程,阅读专题下面的文章了解更多详细内容。

193

2025.08.29

C++中int的含义
C++中int的含义

本专题整合了C++中int相关内容,阅读专题下面的文章了解更多详细内容。

206

2025.08.29

堆和栈的区别
堆和栈的区别

堆和栈的区别:1、内存分配方式不同;2、大小不同;3、数据访问方式不同;4、数据的生命周期。本专题为大家提供堆和栈的区别的相关的文章、下载、课程内容,供大家免费下载体验。

409

2023.07.18

堆和栈区别
堆和栈区别

堆(Heap)和栈(Stack)是计算机中两种常见的内存分配机制。它们在内存管理的方式、分配方式以及使用场景上有很大的区别。本文将详细介绍堆和栈的特点、区别以及各自的使用场景。php中文网给大家带来了相关的教程以及文章欢迎大家前来学习阅读。

586

2023.08.10

Rust异步编程与Tokio运行时实战
Rust异步编程与Tokio运行时实战

本专题聚焦 Rust 语言的异步编程模型,深入讲解 async/await 机制与 Tokio 运行时的核心原理。内容包括异步任务调度、Future 执行模型、并发安全、网络 IO 编程以及高并发场景下的性能优化。通过实战示例,帮助开发者使用 Rust 构建高性能、低延迟的后端服务与网络应用。

1

2026.02.11

热门下载

更多
网站特效
/
网站源码
/
网站素材
/
前端模板

精品课程

更多
相关推荐
/
热门推荐
/
最新课程
关于我们 免责申明 举报中心 意见反馈 讲师合作 广告合作 最新更新
php中文网:公益在线php培训,帮助PHP学习者快速成长!
关注服务号 技术交流群
PHP中文网订阅号
每天精选资源文章推送

Copyright 2014-2026 https://www.php.cn/ All Rights Reserved | php.cn | 湘ICP备2023035733号