Java ThreadLocalMap的线性探测法解决哈希冲突

ThreadLocalMap 是 Java ThreadLocal 的核心存储结构，用于维护线程特有的变量副本。不同于 Java 集合框架中常见的 HashMap 使用链表法或红黑树来处理哈希冲突，ThreadLocalMap 选择了线性探测法。理解这一机制对于排查内存泄漏和优化多线程程序至关重要。

1. 理解基础数据结构

打开 ThreadLocalMap 的源码，你会发现它内部维护了一个 Entry 类型的数组 table。观察 Entry 的定义，它的 Key 是 ThreadLocal 对象，并且继承自 WeakReference（弱引用），而 Value 则是强引用。这意味着 Key 可能被 GC 回收，导致 Key 为 null 的“脏 Entry”。注意，这是一个纯数组结构，没有链表。

2. 定位哈希冲突的产生

计算 一个 ThreadLocal 对象在数组中的下标时，使用公式 key.threadLocalHashCode & (len - 1)。遇到 两个不同的 ThreadLocal 对象计算出相同下标的情况时，就发生了哈希冲突。对比 HashMap 的做法：HashMap 会在该位置挂一个链表或树，把新元素挂在后面。而 ThreadLocalMap 采用 不同的策略。

3. 掌握线性探测法的执行流程

当哈希冲突发生时，线性探测法不会寻找额外的数据结构存储冲突元素，而是直接在当前数组中寻找下一个空位。

尝试 在计算出的下标 i 处插入数据。检查 位置 i：

• 如果该位置为空（null），直接放入数据，结束。
• 如果该位置不为空，判断该位置现有的 Entry 的 Key 是否与当前 Key 相同（通过引用地址 == 或 equals 方法）。
  • 如果 Key 相同，更新该位置的 Value。
  • 如果 Key 不同（发生了冲突），执行线性探测。

执行线性探测：移动到下一个下标 i + 1。循环判断位置 i + 1，直到找到一个空位，或者找到一个 Key 相同的位置进行更新。如果到了数组末尾，会从数组下标 0 继续，形成一个环形探测。

为了更直观地展示这一循环查找的过程，请参考以下流程：

4. 分析 set 方法的源码逻辑

阅读 ThreadLocalMap.set() 方法的关键代码片段，理解线性探测在代码层面的实现。

private void set(ThreadLocal<?> key, Object value) {
    Entry[] tab = table;
    int len = tab.length;
    int i = key.threadLocalHashCode & (len - 1);

    for (Entry e = tab[i]; e != null; e = tab[i = nextIndex(i, len)]) {
        ThreadLocal<?> k = e.get();
        if (k == key) {
            e.value = value;
            return;
        }
        if (k == null) {
            replaceStaleEntry(key, value, i);
            return;
        }
    }

    tab[i] = new Entry(key, value);
    int sz = ++size;
    if (!cleanSomeSlots(i, sz) && sz >= threshold)
        rehash();
}

关注 for (Entry e = tab[i]; e != null; e = tab[i = nextIndex(i, len)]) 这一行循环代码。理解 nextIndex(i, len) 方法的本质：它就是 i + 1，如果越界则归零。执行 循环体内逻辑：

1. 获取 当前槽位的 Entry e。
2. 比对 e.get()（即 Key）与当前 Key。
3. 命中 则替换 Value 并返回。
4. 未命中 且遇到 Key 为 null 的槽位（脏 Entry），触发 replaceStaleEntry 进行清理并插入新数据。

结束 循环若仍未找到位置，创建 新 Entry 放入 找到的空槽位。

5. 理解 get 操作的回溯探测

调用 get() 方法获取数据时，同样面临哈希冲突的查找问题。

计算 初始下标 i。遍历 数组：从 i 开始向后线性扫描。匹配 Key：如果找到 Key 相同的 Entry，返回 其 Value。终止 条件：如果在扫描过程中遇到了某个槽位为 null（空槽位），说明后面不可能再有目标数据了（因为 set 时是连续存放的），停止 查找并返回 null。

6. 对比线性探测法与链表法

建立 如下对比表格，理解两者差异：