问题

ThreadLocalMap使用链表法来处理冲突吗？

答案

核心结论

不是。ThreadLocalMap使用的是开放地址法中的线性探测法（Linear Probing），而非链表法。

冲突解决：线性探测法

原理：当哈希冲突时，向后查找下一个空位置，直到找到空位或找到相同的key。

核心代码：

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();

        // 情况1: 找到相同的key，更新value
        if (k == key) {
            e.value = value;
            return;
        }

        // 情况2: key为null（已被GC），替换过期Entry
        if (k == null) {
            replaceStaleEntry(key, value, i);
            return;
        }

        // 情况3: 不同的key，继续向后查找
    }

    // 找到空位，插入新Entry
    tab[i] = new Entry(key, value);
    int sz = ++size;

    if (!cleanSomeSlots(i, sz) && sz >= threshold)
        rehash();
}

// 计算下一个索引（循环递增）
private static int nextIndex(int i, int len) {
    return ((i + 1 < len) ? i + 1 : 0);
}

线性探测示例

场景：初始容量16，依次插入3个ThreadLocal

ThreadLocal<String> tl1 = new ThreadLocal<>();  // hash后索引 = 5
ThreadLocal<String> tl2 = new ThreadLocal<>();  // hash后索引 = 5（冲突！）
ThreadLocal<String> tl3 = new ThreadLocal<>();  // hash后索引 = 6（冲突！）

插入过程：

初始状态:
┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┐
│ 0 │ 1 │ 2 │ 3 │ 4 │ 5 │ 6 │ 7 │ 8 │ 9 │10 │11 │12 │13 │14 │15 │
├───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┤
│   │   │   │   │   │   │   │   │   │   │   │   │   │   │   │   │
└───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┘

插入tl1（索引5）:
┌───┬───┬───┬───┬───┬─────┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┐
│ 0 │ 1 │ 2 │ 3 │ 4 │ tl1 │ 6 │ 7 │ 8 │ 9 │10 │11 │12 │13 │14 │15 │
└───┴───┴───┴───┴───┴─────┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┘

插入tl2（索引5，冲突）:
1. 检查table[5]，已被tl1占用
2. i = nextIndex(5, 16) = 6
3. 检查table[6]，为null，插入tl2

┌───┬───┬───┬───┬───┬─────┬─────┬───┬───┬───┬───┬───┬───┬───┬───┬───┐
│ 0 │ 1 │ 2 │ 3 │ 4 │ tl1 │ tl2 │ 7 │ 8 │ 9 │10 │11 │12 │13 │14 │15 │
└───┴───┴───┴───┴───┴─────┴─────┴───┴───┴───┴───┴───┴───┴───┴───┴───┘

插入tl3（索引6，冲突）:
1. 检查table[6]，已被tl2占用
2. i = nextIndex(6, 16) = 7
3. 检查table[7]，为null，插入tl3

┌───┬───┬───┬───┬───┬─────┬─────┬─────┬───┬───┬───┬───┬───┬───┬───┬───┐
│ 0 │ 1 │ 2 │ 3 │ 4 │ tl1 │ tl2 │ tl3 │ 8 │ 9 │10 │11 │12 │13 │14 │15 │
└───┴───┴───┴───┴───┴─────┴─────┴─────┴───┴───┴───┴───┴───┴───┴───┴───┘

get()操作的线性探测

private Entry getEntry(ThreadLocal<?> key) {
    int i = key.threadLocalHashCode & (table.length - 1);
    Entry e = table[i];

    if (e != null && e.get() == key) {
        return e;  // 直接命中
    } else {
        return getEntryAfterMiss(key, i, e);  // 未命中，线性探测
    }
}

private Entry getEntryAfterMiss(ThreadLocal<?> key, int i, Entry e) {
    Entry[] tab = table;
    int len = tab.length;

    while (e != null) {
        ThreadLocal<?> k = e.get();
        if (k == key)
            return e;  // 找到
        if (k == null)
            expungeStaleEntry(i);  // 顺便清理过期Entry
        else
            i = nextIndex(i, len);  // 继续向后查找
        e = tab[i];
    }
    return null;  // 遇到null停止
}

查找示例：

查找tl3（初始索引6）:
1. table[6] = tl2，不匹配
2. i = nextIndex(6, 16) = 7
3. table[7] = tl3，匹配成功 ✓

与HashMap链表法对比

维度	ThreadLocalMap（线性探测）	HashMap（链表法/红黑树）
冲突解决	开放地址法（线性探测）	链表法（JDK8+红黑树）
存储结构	Entry数组	Node数组 + 链表/树
查找过程	向后探测直到找到或遇到null	遍历链表/树
最坏时间复杂度	O(n)	O(log n)（红黑树）
空间占用	只需数组	数组 + Node对象
缓存友好	✅ 连续内存访问	❌ Node对象分散
适用场景	元素少、冲突低	元素多、冲突高

HashMap的链表法示意：

HashMap table数组:
┌─────┬─────┬─────┬─────┐
│  0  │  1  │  2  │  3  │
├─────┼─────┼─────┼─────┤
│null │ ●───┼─●   │null │
└─────┴──│──┴─│───┴─────┘
         │    │
         ↓    ↓
       Node  Node
         │    │
         ↓    ↓
       Node  null
         │
         ↓
       null

为什么ThreadLocalMap使用线性探测？

1. ThreadLocal数量少

• 一般一个线程只有几个ThreadLocal（< 10个）
• 冲突概率低，线性探测足够高效

2. 魔数保证均匀分布

private static final int HASH_INCREMENT = 0x61c88647;  // 斐波那契散列

// 即使连续创建ThreadLocal，分布也很均匀
ThreadLocal tl1 = new ThreadLocal();  // hash: 0x61c88647
ThreadLocal tl2 = new ThreadLocal();  // hash: 0xc3910c8e
ThreadLocal tl3 = new ThreadLocal();  // hash: 0x2559f0d5

3. 缓存友好

• 数组连续存储，CPU缓存命中率高
• 链表Node对象分散在堆中，缓存效率低

4. 避免额外对象

• 线性探测只需Entry数组
• 链表法需要额外的Node对象，增加GC压力

线性探测的性能问题

问题1：聚集现象（Clustering）

当发生冲突时，多个Entry会堆积在一起，形成”簇”，导致查找效率下降。

聚集示例:
┌───┬───┬───┬─────┬─────┬─────┬─────┬───┬───┐
│ 0 │ 1 │ 2 │ tl1 │ tl2 │ tl3 │ tl4 │ 7 │ 8 │
└───┴───┴───┴─────┴─────┴─────┴─────┴───┴───┘
             ← 聚集区域 →

// 如果新插入的ThreadLocal hash到3-6，需要多次探测

解决方案：

• 使用魔数0x61c88647减少聚集
• 低负载因子（2/3），保持稀疏

问题2：查找效率下降

最坏情况下，查找需要遍历整个数组（O(n)）。

解决方案：

• 扩容阈值设为capacity * 2/3（比HashMap的0.75更低）
• 及时清理过期Entry，减少有效元素数量

扩容时的rehash

private void rehash() {
    expungeStaleEntries();  // 先清理所有过期Entry

    // 清理后如果仍超过3/4阈值，则扩容
    if (size >= threshold - threshold / 4)
        resize();
}

private void resize() {
    Entry[] oldTab = table;
    int oldLen = oldTab.length;
    int newLen = oldLen * 2;  // 扩容2倍
    Entry[] newTab = new Entry[newLen];

    int count = 0;

    for (int j = 0; j < oldLen; ++j) {
        Entry e = oldTab[j];
        if (e != null) {
            ThreadLocal<?> k = e.get();
            if (k == null) {
                e.value = null;  // 清理过期Entry
            } else {
                // 重新计算索引
                int h = k.threadLocalHashCode & (newLen - 1);
                while (newTab[h] != null)
                    h = nextIndex(h, newLen);  // 线性探测找空位
                newTab[h] = e;
                count++;
            }
        }
    }

    setThreshold(newLen);
    size = count;
    table = newTab;
}

rehash过程：

扩容前（容量16）:
┌───┬───┬───┬─────┬─────┬─────┬───┬───┐
│ 0 │ 1 │ 2 │ tl1 │ tl2 │null │ 6 │ 7 │
└───┴───┴───┴─────┴─────┴─────┴───┴───┘

扩容后（容量32）:
- 重新计算每个Entry的索引
- tl1: 旧索引3，新索引可能是3或19（取决于hash值）
- tl2: 旧索引4，重新计算
- 元素分布更均匀

实际性能测试

public class LinearProbingPerformance {
    public static void main(String[] args) {
        int count = 100;

        // 测试线性探测性能
        long start = System.nanoTime();
        for (int i = 0; i < count; i++) {
            ThreadLocal<String> tl = new ThreadLocal<>();
            tl.set("value" + i);
            tl.get();
        }
        long time = System.nanoTime() - start;

        System.out.println("100个ThreadLocal操作耗时: " + time / 1000 + "μs");
        // 输出: 约100-200μs（非常快）
    }
}

线性探测的优缺点

优点：

• ✅ 实现简单，代码量少
• ✅ 缓存友好，连续内存访问
• ✅ 无需额外Node对象，节省内存
• ✅ 配合魔数，冲突率低

缺点：

• ❌ 容易产生聚集现象
• ❌ 删除操作复杂（需要重新rehash）
• ❌ 负载因子过高时性能下降
• ❌ 最坏情况O(n)查找

面试答题要点

1. 核心答案：ThreadLocalMap使用线性探测法（开放地址法），而非链表法
2. 工作原理：哈希冲突时向后查找下一个空位，直到找到空位或相同key
3. 与HashMap对比：HashMap用链表/红黑树，ThreadLocalMap用数组+线性探测
4. 设计原因：ThreadLocal数量少、魔数保证均匀分布、缓存友好、节省内存
5. 性能优化：低负载因子（2/3）、魔数0x61c88647、及时清理过期Entry