ThreadLocalMap哈希冲突解决与清理机制详解

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

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()，不能只依赖自动清理

事情说清了就结束。