Java & Android 集合框架 #10 全网最全的 ThreadLocal 原理详细解析 —— 源码篇
⭐️ 本文已收录到 AndroidFamily，技术和职场问题，请关注公众号 [彭旭锐] 和 [BaguTree Pro] 知识星球提问。
学习数据结构与算法的关键在于掌握问题背后的算法思维框架，你的思考越抽象，它能覆盖的问题域就越广，理解难度也更复杂。在实际的业务开发中，往往不需要我们手写数据结构，而是直接使用标准库的数据结构 / 容器类。
本文是 Java & Android 集合框架系列的第 10 篇文章，完整文章目录请移步到文章末尾~
前言
大家好，我是小彭。
本文源码基于 Java 8 ThreadLocal。
思维导图：
4. ThreadLocalMap 源码分析
ThreadLocalMap 是 ThreadLocal 内部使用的散列表，也是 ThreadLocal 的静态内部类。这一节，我们就来分析 ThreadLocalMap 散列表中主要流程的源码。
4.1 ThreadLocalMap 的属性
先用一个表格整理 ThreadLocalMap 的属性：
| 属性 | 描述 |
|---|---|
| Entry[] table | 底层数组 |
| int size | 有效键值对数量 |
| int threshold | 扩容阈值（数组容量的 2/3） |
| int INITIAL_CAPACITY | 默认数组容量（16） |
可以看到，散列表必备底层数组 table、键值对数量 size、扩容阈值 threshold 等属性都有，并且也要求数组的长度是 2 的整数倍。主要区别在于 Entry 节点上：
- 1、ThreadLocal 本身就是散列表的键 Key；
- 2、扩容阈值为数组容量的 2/3；
- 3、ThreadLocalMap#Entry 节点没有
next指针，因为 ThreadLocalMap 采用线性探测解决散列冲突，所以不存在链表指针； - 4、ThreadLocalMap#Entry 在键值对的 Key 上使用弱引用，这与 WeakHashMap 相似。
ThreadLocal.java
static class ThreadLocalMap {
// 默认数组容量（容量必须是 2 的整数倍）
private static final int INITIAL_CAPACITY = 16;
// 底层数组
private Entry[] table;
// 有效键值对数量
private int size = 0;
// 扩容阈值
private int threshold; // Default to 0
private void setThreshold(int len) {
threshold = len * 2 / 3;
}
// 键值对节点
static class Entry extends WeakReference<ThreadLocal<?>> {
// next：开放寻址法没有 next 指针
// Key：与 WeakHashMap 相同，少了 key 的强引用
// Hash：位于 ThreadLocal#threadLocalHashCode
// Value：当前线程的副本
Object value;
Entry(ThreadLocal<?> k, Object v) {
super(k/*注意：只有 Key 是弱引用*/);
value = v;
}
}
}
不出意外的话又有小朋友出来举手提问了🙋🏻♀️：
-
🙋🏻♀️疑问 3：为什么 ThreadLocalMap 要求数组的容量是 2 的整数幂？（回答过多少次了，把手给我放下）
-
🙋🏻♀️疑问 4：为什么 Key 是弱引用，而不是 Entry 或 Value 是弱引用？
首先，Entry 一定要持有强引用，而不能持有弱引用。这是因为 Entry 是 ThreadLocalMap 内部维护数据结构的实现细节，并不会暴露到 ThreadLocalMap 外部，即除了 ThreadLocalMap 本身之外没有其它地方持有 Entry 的强引用。所以，如果持有 Entry 的弱引用，即使 ThreadLocalMap 外部依然在使用 Key 对象，ThreadLocalMap 内部依然会回收键值对，这与预期不符。
其次，不管是 Key 还是 Value 使用弱引用都可以实现自动清理，至于使用哪一种方法各有优缺点，适用场景也不同。Key 弱引用的优点是外部不需要持有 Value 的强引用，缺点是存在 “重建 Key 不等价” 问题。
由于 ThreadLocal 的应用场景是线程局部存储，我们没有重建多个 ThreadLocal 对象指向同一个键值对的需求，也没有重写 Object#equals() 方法，所以不存在重建 Key 的问题，使用 Key 弱引用更方便。
| 类型 | 优点 | 缺点 | 场景 |
|---|---|---|---|
| Key 弱引用 | 外部不需要持有 Value 的强引用，使用更简单 | 重建 Key 不等价 | 未重写 equals |
| Value 弱引用 | 重建 Key 等价 | 外部需要持有 Value 的强引用 | 重写 equals |
4.2 ThreadLocalMap 的构造方法
ThreadLocalMap 有 2 个构造方法：
-
1、带首个键值对的构造方法： 在首次添加元素或首次查询数据生成缺省值时，才会调用此构造方法创建 ThreadLocalMap 对象，并添加首个键值对；
-
2、带 Map 的构造方法： 在创建子线程时，父线程会调用此构造方法创建 ThreadLocalMap 对象，并添加批量父线程 ThreadLocalMap 中的有效键值对。
ThreadLocal.java
// 带首个键值对的构造方法
void createMap(Thread t, T firstValue) {
t.threadLocals = new ThreadLocalMap(this, firstValue);
}
// 带 Map 的构造方法
static ThreadLocalMap createInheritedMap(ThreadLocalMap parentMap) {
return new ThreadLocalMap(parentMap);
}
static class ThreadLocalMap {
// -> 带首个键值对的构造方法
ThreadLocalMap(ThreadLocal<?> firstKey, Object firstValue) {
// 创建底层数组（默认长度为 16）
table = new Entry[INITIAL_CAPACITY];
// 散列值转数组下标
int i = firstKey.threadLocalHashCode & (INITIAL_CAPACITY - 1);
// 添加首个元素（首个元素一定不会冲突）
table[i] = new Entry(firstKey, firstValue);
// 键值对数量
size = 1;
// 设置扩容阈值
setThreshold(INITIAL_CAPACITY);
}
// -> 带 Map 的构造方法
private ThreadLocalMap(ThreadLocalMap parentMap) {
Entry[] parentTable = parentMap.table;
int len = parentTable.length;
// 设置扩容阈值
setThreshold(len);
// 创建底层数组（使用 parent 的长度）
table = new Entry[len];
// 逐个添加键值对
for (int j = 0; j < len; j++) {
Entry e = parentTable[j];
if (e != null) {
// 如果键值对的 Key 被回收，则跳过
ThreadLocal<Object> key = (ThreadLocal<Object>) e.get();
if (key != null) {
// 构造新的键值对
Object value = key.childValue(e.value);
Entry c = new Entry(key, value);
// 散列值转数组下标
int h = key.threadLocalHashCode & (len - 1);
// 处理散列冲突
while (table[h] != null)
// 线性探测
h = nextIndex(h, len);
table[h] = c;
// 键值对数量
size++;
}
}
}
}
}
4.3 回顾线性探测的工作原理
ThreadLocalMap 后续的源码有难度，为了帮助理解，我将文章 “第一节 · 回顾散列表的工作原理” 中有关线性探测方法的部分移在这里。
-
添加键值对： 先将散列值取余映射到数组下标，然后从数组下标位置开始探测与目标 Key 相等的节点。如果找到，则将旧 Value 替换为新 Value，否则沿着数组顺序线性探测。直到线性探测遇到空闲位置，则说明节点不存在，需要添加新节点。如果在添加键值对后数组没有空闲位置，就触发扩容；
-
查找键值对： 查找类似。也是先将散列值映射到数组下标，然后从数组下标位置开始线性探测。直到线性探测遇到空闲位置，则说明节点不存在；
-
删除键值对： 删除类似。由于查找操作在遇到空闲位置时，会认为键值对不存在于散列表中，如果删除操作时 “真删除”，就会使得一组连续段产生断层，导致查找操作失效。因此，删除操作要做 “假删除”，删除操作只是将节点标记为 “Deleted”，查找操作在遇到 “Deleted” 标记的节点时会继续向下探测。
开放寻址法示意图
可以看到，在线性探测中的 “连续段” 非常重要： 线性探测在判断节点是否存在于散列表时，并不是线性遍历整个数组，而只会线性遍历从散列值映射的数组下标后的连续段。
4.4 ThreadLocalMap 的获取方法
ThreadLocalMap 的获取方法相对简单，所以我们先分析，区分 2 种情况：
- 1、数组下标直接命中目标 Key，则直接返回，也不清理无效数据（这就是前文提到访问 ThreadLocal 不一定会触发清理的源码体现）；
- 2、数组下标未命中目标 Key，则开始线性探测。探测过程中如果遇到 Key == null 的无效节点，则会调用
expungeStaleEntry()清理连续段（说明即使触发清理，也不一定会扫描整个散列表）。
expungeStaleEntry() 是 ThreadLocalMap 核心的连续段清理方法，下文提到的 replaceStaleEntry() 和 cleanSomeSlots() 等清理方法都会直接或间接调用到 expungeStaleEntry()。 它的逻辑很简单：就是线性遍历从 staleSlot 位置开始的连续段：
- 1、k == null 的无效节点： 清理；
- 2、k ≠ null 的有效节点，再散列到新的位置上。
ThreadLocalMap#getEntry 方法示意图
不出意外的话又有小朋友出来举手提问了🙋🏻♀️：
- 🙋🏻♀️疑问 5：清理无效节点我理解，为什么要对有效节点再散列呢？
线性探测只会遍历连续段，而清理无效节点会导致连续段产生断层。如果没有对有效节点做再散列，那么有效节点在下次查询时就有可能探测不到了。
ThreadLocal.java
static class ThreadLocalMap {
// 获取 Key 匹配的键值对
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)
// Key 对象被回收，触发连续段清理
// 连续段清理在一个 while 循环中只会触发一次，因为这个段中 k == null 的节点都被清理出去了
// 如果连续段清理后，i 位置为 null，那么目标节点一定不存在
expungeStaleEntry(i);
else
// 未命中，探测下一个位置
i = nextIndex(i, len);
e = tab[i];
}
return null;
}
// -> 清理连续段中无效数据
// staleSlot：起点
private int expungeStaleEntry(int staleSlot) {
Entry[] tab = table;
int len = tab.length;
// 清理无效节点（起点一定是无效节点）
tab[staleSlot].value = null;
tab[staleSlot] = null;
size--;
// 线性探测直到遇到空闲位置
Entry e;
int i;
for (i = nextIndex(staleSlot, len); (e = tab[i]) != null; i = nextIndex(i, len)) {
ThreadLocal<?> k = e.get();
if (k == null) {
// 清理无效节点
e.value = null;
tab[i] = null;
size--;
} else {
// 疑问 5：清理无效节点我理解，为什么要对有效节点再散列呢？
// 再散列有效节点
int h = k.threadLocalHashCode & (len - 1);
if (h != i) {
tab[i] = null;
while (tab[h] != null)
h = nextIndex(h, len);
tab[h] = e;
}
}
}
return i;
}
// -> 线性探测下一个数组位置
private static int nextIndex(int i, int len) {
return ((i + 1 < len) ? i + 1 : 0);
}
}
4.5 ThreadLocalMap 的添加方法
ThreadLocalMap#set 的流程非常复杂，我将主要步骤概括为 6 步：
- 1、先将散列值映射到数组下标，并且开始线性探测；
- 2、如果探测中遇到目标节点，则将旧 Value 更新为新 Value；
- 3、如果探测中遇到无效节点，则会调用
replaceStaleEntry()清理连续段并添加键值对； - 4、如果未探测到目标节点或无效节点，则创建并添加新节点；
- 5、添加新节点后调用
cleanSomeSlots()方法清理部分数据； - 6、如果没有发生清理并且达到扩容阈值，则触发
rehash()扩容。
replaceStaleEntry()： 清理连续段中的无效节点的同时，如果目标节点存在则更新 Value 后替换到 staleSlot 无效节点位置，如果不存在则创建新节点替换到 staleSlot 无效节点位置。
cleanSomeSlots()： 对数式清理，清理复杂度比全数组清理低，在大多数情况只会扫描 log(len) 个元素。如果扫描过程中遇到无效节点，则从该位置执行一次连续段清理，再从连续段的下一个位置重新扫描 log(len) 个元素，直接结束对数扫描。
ThreadLocalMap#set 示意图
ThreadLocal.java
static class ThreadLocalMap {
private void set(ThreadLocal<?> key, Object value) {
Entry[] tab = table;
int len = tab.length;
// 1、散列值转数组下标
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) {
// 2、命中，将旧 Value 替换为新 Value
e.value = value;
return;
}
if (k == null) {
// 3、清理无效节点，并插入键值对
replaceStaleEntry(key, value, i);
return;
}
}
// 4、如果未探测到目标节点或无效节点，则创建并添加新节点
tab[i] = new Entry(key, value);
int sz = ++size;
// cleanSomeSlots：清理部分数据
// 5、添加新节点后调用 cleanSomeSlots() 方法清理部分数据
if (!cleanSomeSlots(i, sz /*有效数据个数*/) && sz >= threshold)
// 6、如果没有发生清理并且达到扩容阈值，则触发 rehash() 扩容
rehash();
}
// -> 3、清理无效节点，并插入键值对
// key-value：插入的键值对
private void replaceStaleEntry(ThreadLocal<?> key, Object value, int staleSlot) {
Entry[] tab = table;
int len = tab.length;
Entry e;
// slotToExpunge：记录清理的起点
int slotToExpunge = staleSlot;
// 3.1 向前探测找到连续段中的第一个无效节点
for (int i = prevIndex(staleSlot, len); (e = tab[i]) != null; i = prevIndex(i, len))
if (e.get() == null)
slotToExpunge = i;
// 3.2 向后探测目标节点
for (int i = nextIndex(staleSlot, len); (e = tab[i]) != null; i = nextIndex(i, len)) {
ThreadLocal<?> k = e.get();
if (k == key) {
// 3.2.1 命中，将目标节点替换到 staleSlot 位置
e.value = value;
tab[i] = tab[staleSlot];
tab[staleSlot] = e;
// 3.2.2 如果连续段在 staleSlot 之前没有无效节点，则从 staleSlot 的下一个无效节点开始清理
if (slotToExpunge == staleSlot)
slotToExpunge = i;
// 3.2.3 如果连续段中还有其他无效节点，则清理
// expungeStaleEntry：连续段清理
// cleanSomeSlots：对数式清理
cleanSomeSlots(expungeStaleEntry(slotToExpunge), len);
return;
}
// 如果连续段在 staleSlot 之前没有无效节点，则从 staleSlot 的下一个无效节点开始清理
if (k == null && slotToExpunge == staleSlot)
slotToExpunge = i;
}
// 3.3 创建新节点并插入 staleSlot 位置
tab[staleSlot].value = null;
tab[staleSlot] = new Entry(key, value);
// 3.4 如果连续段中还有其他无效节点，则清理
if (slotToExpunge != staleSlot)
cleanSomeSlots(expungeStaleEntry(slotToExpunge), len /*数组长度*/);
}
// 5、对数式清理
// i：起点
// n：数组长度或有效数据个数
private boolean cleanSomeSlots(int i, int n) {
boolean removed = false;
Entry[] tab = table;
int len = tab.length;
do {
i = nextIndex(i, len);
Entry e = tab[i];
if (e != null && e.get() == null) {
// 发现无效节点，重新探测 log2(len)
n = len;
removed = true;
// 连续段清理
i = expungeStaleEntry(i);
}
} while ( (n >>>= 1) != 0); // 探测 log2(len)
return removed;
}
}
4.6 ThreadLocalMap 的扩容方法
ThreadLocalMap 的扩容方法相对于添加方法比较好理解。在添加方法中，如果添加键值对后散列值的长度超过扩容阈值，就会调用 rehash() 方法扩容，主体流程分为 3步：
- 1、先完整扫描散列表清理无效数据，清理后用较低的阈值判断是否需要扩容；
- 2、创建新数组；
- 3、将旧数组上无效的节点忽略，将有效的节点再散列到新数组上。
ThreadLocaoMap#rehash 示意图
ThreadLocal.java
static class ThreadLocalMap {
// 扩容（在容量到达 threshold 扩容阈值时调用）
private void rehash() {
// 1、全数组清理
expungeStaleEntries();
// 2、用较低的阈值判断是否需要扩容
if (size >= threshold - threshold / 4)
// 3、真正执行扩容
resize();
}
// -> 1、完整散列表清理
private void expungeStaleEntries() {
Entry[] tab = table;
int len = tab.length;
for (int j = 0; j < len; j++) {
Entry e = tab[j];
if (e != null && e.get() == null)
// 很奇怪为什么不修改 j 指针
expungeStaleEntry(j);
}
}
// -> 3、真正执行扩容
private void resize() {
Entry[] oldTab = table;
// 扩容为 2 倍
int oldLen = oldTab.length;
int newLen = oldLen * 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) {
// 清除无效键值的 Value
e.value = null; // Help the GC
} 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;
}
}
4.7 ThreadLocalMap 的移除方法
ThreadLocalMap 的移除方法是添加方法的逆运算，ThreadLocalMap 也没有做动态缩容。
与常规的移除操作不同的是，ThreadLocalMap 在删除时会执行 expungeStaleEntry() 清除无效节点，并对连续段中的有效节点做再散列，所以 ThreadLocalMap 是 “真删除”。
ThreadLocal.java
static class ThreadLocalMap {
// 移除
private void remove(ThreadLocal<?> key) {
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)]) {
if (e.get() == key) {
// 清除弱引用关系
e.clear();
// 清理连续段
expungeStaleEntry(i);
return;
}
}
}
}
4.8 ThreadLocalMap 复杂度分析
总结下 ThreadLocalMap 的时间复杂度，以下 K 为连续段的长度，N 是数组长度。
- 获取方法： 平均时间复杂度为 O(K)；
- 添加方法： 平均时间复杂度为 O(K)，在触发扩容的添加操作中时间复杂度为 O(N)，基于摊还分析后时间复杂度依然是 O(K)；
- 移除方法： 移除是 “真删除”，平均时间复杂度为 O(K)。
4.9 访问 ThreadLocal 一定会清理无效数据吗？
不一定。只有扩容会触发完整散列表清理，其他情况都不能保证清理，甚至不会触发。
5. 总结
- 1、ThreadLocal 是一种特殊的无锁线程安全方式，通过为每个线程分配独立的资源副本，从根本上避免发生资源冲突；
- 2、ThreadLocal 在所有线程间隔离，InheritableThreadLocal 在创建子线程时会拷贝父线程中 InheritableThreadLocal 的有效键值对；
- 3、虽然 ThreadLocal 提供了自动清理数据的能力，但是自动清理存在滞后性。为了避免内存泄漏，在业务开发中应该及时调用 remove 清理无效的局部存储；
- 4、ThreadLocal 是采用线性探测解决散列冲突的散列表。
ThreadLocal 思维导图
版权声明
参考资料
⭐️ 永远相信美好的事情即将发生，欢迎加入小彭的 Android 交流社群~
