讲师中心 微信公众号
AI工具推荐 视频效率加速

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

星瑶小哥_3306

星瑶小哥_3306

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

|

1008人浏览过

|

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

更重要的是:线性探测让清理逻辑可嵌入到日常读写路径中,而二次哈希会让 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 Hot

一款AI音频处理工具,主要用于音述AI是一个以“用声音述说故事”为核心的 AI 音乐创作与声音分享社区,适合需要提升相关任务效率的用户。

WorkBuddy

一款AI办公效率工具,主要用于腾讯云推出的AI原生桌面智能体工作台,适合需要提升相关任务效率的用户。

Atoms
Atoms Hot

Atoms是一款AI智能体工具,第一支自动构建真实业务的 AI 团队。

二狗PPT
二狗PPT Hot

一款AI演示文稿工具,主要用于专为中式职场打造的AI PPT生成工具,适合需要提升相关任务效率的用户。

立刻MV
立刻MV Hot

立刻MV是一款AI文本写作工具,AI 音乐视频(MV)创作工具。

码上飞
码上飞 Hot

一款基于自然语言的AI应用开发平台,可根据用户描述自动生成应用程序,帮助个人和团队快速完成应用原型与开发。

Lovart
Lovart Hot

一款面向视觉设计创作的AI设计平台,可通过智能体和画布工作流辅助制作海报、Logo、网页、PPT及其他视觉内容。

豆包大模型

豆包大模型是一款由字节跳动推出的企业级大语言模型服务平台。

相关专题

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

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

549

2023.09.22

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

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

1698

2024.03.01

string转int
string转int

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

7139

2023.08.02

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

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

3405

2024.08.29

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

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

4448

2025.08.29

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

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

3005

2025.08.29

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

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

6607

2023.07.18

堆和栈区别
堆和栈区别

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

2748

2023.08.10

DBeaver怎么导入数据
DBeaver怎么导入数据

DBeaver数据导入专题,整理Excel、CSV、SQL、TXT等常见文件的数据导入方法,涵盖目标数据库选择、数据表创建、字段映射、数据类型设置及导入参数配置等操作,帮助用户将本地文件中的数据写入数据库,并了解批量导入、重复数据处理和导入失败等常见问题的解决方法。

0

2026.11.05

热门下载

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

精品课程

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

Copyright 2014-2026 https://www.php.cn/ All Rights Reserved | php.cn