本文已收录到 AndroidFamily，技术和职场问题，请关注公众号 [彭旭锐] 提问。
前言
大家好，我是小彭。
在前面的文章里，我们聊到了散列表的开放寻址法和分离链表法，也聊到了 HashMap、LinkedHashMap 和 WeakHashMap 等基于分离链表法实现的散列表。
今天，我们来讨论 Java 标准库中一个使用开放寻址法的散列表结构，也是 Java & Android “面试八股文” 的标准题库之一 —— ThreadLocal。
本文源码基于 Java 8 ThreadLocal。
思维导图：
1. 回顾散列表的工作原理
在开始分析 ThreadLocal 的实现原理之前，我们先回顾散列表的工作原理。
散列表是基于散列思想实现的 Map 数据结构，将散列思想应用到散列表数据结构时，就是通过 hash 函数提取键（Key）的特征值（散列值），再将键值对映射到固定的数组下标中，利用数组支持随机访问的特性，实现 O(1) 时间的存储和查询操作。
散列表示意图
在从键值对映射到数组下标的过程中，散列表会存在 2 次散列冲突：
- 第 1 次 - hash 函数的散列冲突： 这是一般意义上的散列冲突；
- 第 2 次 - 散列值取余转数组下标： 本质上，将散列值转数组下标也是一次 Hash 算法，也会存在散列冲突。
事实上，由于散列表是压缩映射，所以我们无法避免散列冲突，只能保证散列表不会因为散列冲突而失去正确性。常用的散列冲突解决方法有 2 类：
- 开放寻址法： 例如 ThreadLocalMap；
- 分离链表法： 例如 HashMap。
开放寻址（Open Addressing）的核心思想是： 在出现散列冲突时，在数组上重新探测出一个空闲位置。 经典的探测方法有线性探测、平方探测和双散列探测。线性探测是最基本的探测方法，我们今天要分析的 ThreadLocal 中的 ThreadLocalMap 散列表就是采用线性探测的开放寻址法。
2. 认识 ThreadLocal 线程局部存储
2.1 说一下 ThreadLocal 的特点？
ThreadLocal 提供了一种特殊的线程安全方式。
使用 ThreadLocal 时，每个线程可以通过 ThreadLocal#get 或 ThreadLocal#set 方法访问资源在当前线程的副本，而不会与其他线程产生资源竞争。这意味着 ThreadLocal 并不考虑如何解决资源竞争，而是为每个线程分配独立的资源副本，从根本上避免发生资源冲突，是一种无锁的线程安全方法。
用一个表格总结 ThreadLocal 的 API：
| public API | 描述 |
|---|---|
| set(T) | 设置当前线程的副本 |
| T get() | 获取当前线程的副本 |
| void remove() | 移除当前线程的副本 |
| ThreadLocal<S> withInitial(Supplier<S>) | 创建 ThreadLocal 并指定缺省值创建工厂 |
| protected API | 描述 |
| T initialValue() | 设置缺省值 |
2.2 ThreadLocal 如何实现线程隔离？（重点理解）
ThreadLocal 在每个线程的 Thread 对象实例数据中分配独立的内存区域，当我们访问 ThreadLocal 时，本质上是在访问当前线程的 Thread 对象上的实例数据，不同线程访问的是不同的实例数据，因此实现线程隔离。
Thread 对象中这块数据就是一个使用线性探测的 ThreadLocalMap 散列表，ThreadLocal 对象本身就作为散列表的 Key ，而 Value 是资源的副本。当我们访问 ThreadLocal 时，就是先获取当前线程实例数据中的 ThreadLocalMap 散列表，再通过当前 ThreadLocal 作为 Key 去匹配键值对。
ThreadLocal.java
// 获取当前线程的副本 public T get() { // 先获取当前线程实例数据中的 ThreadLocalMap 散列表 Thread t = Thread.currentThread(); ThreadLocalMap map = getMap(t); // 通过当前 ThreadLocal 作为 Key 去匹配键值对 ThreadLocalMap.Entry e = map.getEntry(this); // 详细源码分析见下文 ... } // 获取线程 t 的 threadLocals 字段，即 ThreadLocalMap 散列表 ThreadLocalMap getMap(Thread t) { return t.threadLocals; } // 静态内部类 static class ThreadLocalMap { // 详细源码分析见下文 ... } Thread.java
// Thread 对象的实例数据 ThreadLocal.ThreadLocalMap threadLocals = null; ThreadLocal.ThreadLocalMap inheritableThreadLocals = null; // 线程退出之前，会置空threadLocals变量，以便随后GC private void exit() { // ... threadLocals = null; inheritableThreadLocals = null; inheritedAccessControlContext = null; // ... } ThreadLocal 示意图
2.3 使用 InheritableThreadLocal 继承父线程的局部存储
在业务开发的过程中，我们可能希望子线程可以访问主线程中的 ThreadLocal 数据，然而 ThreadLocal 是线程隔离的，包括在父子线程之间也是线程隔离的。为此，ThreadLocal 提供了一个相似的子类 InheritableThreadLocal，ThreadLocal 和 InheritableThreadLocal 分别对应于线程对象上的两块内存区域：
-
1、ThreadLocal 字段： 在所有线程间隔离；
-
2、InheritableThreadLocal 字段： 子线程会继承父线程的 InheritableThreadLocal 数据。父线程在创建子线程时，会批量将父线程的有效键值对数据拷贝到子线程的 InheritableThreadLocal，因此子线程可以复用父线程的局部存储。
在 InheritableThreadLocal 中，可以重写 childValue() 方法修改拷贝到子线程的数据。
public class InheritableThreadLocal<T> extends ThreadLocal<T> { // 参数：父线程的数据 // 返回值：拷贝到子线程的数据，默认为直接传递 protected T childValue(T parentValue) { return parentValue; } } 需要特别注意：
-
注意 1 - InheritableThreadLocal 区域在拷贝后依然是线程隔离的： 在完成拷贝后，父子线程对 InheritableThreadLocal 的操作依然是相互独立的。子线程对 InheritableThreadLocal 的写不会影响父线程的 InheritableThreadLocal，反之亦然；
-
注意 2 - 拷贝过程在父线程执行： 这是容易混淆的点，虽然拷贝数据的代码写在子线程的构造方法中，但是依然是在父线程执行的。子线程是在调用 start() 后才开始执行的。
InheritableThreadLocal 示意图
2.4 ThreadLocal 的自动清理与内存泄漏问题
ThreadLocal 提供具有自动清理数据的能力，具体分为 2 个颗粒度：
-
1、自动清理散列表： ThreadLocal 数据是 Thread 对象的实例数据，当线程执行结束后，就会跟随 Thread 对象 GC 而被清理；
-
2、自动清理无效键值对： ThreadLocal 是使用弱键的动态散列表，当 Key 对象不再被持有强引用时，垃圾收集器会按照弱引用策略自动回收 Key 对象，并在下次访问 ThreadLocal 时清理无效键值对。
引用关系示意图
然而，自动清理无效键值对会存在 “滞后性”，在滞后的这段时间内，无效的键值对数据没有及时回收，就发生内存泄漏。
- 举例 1： 如果创建 ThreadLocal 的线程一直持续运行，整个散列表的数据就会一致存在。比如线程池中的线程（大体）是复用的，这部分复用线程中的 ThreadLocal 数据就不会被清理；
- 举例 2： 如果在数据无效后没有再访问过 ThreadLocal 对象，那么自然就没有机会触发清理；
- 举例 3： 即使访问 ThreadLocal 对象，也不一定会触发清理（原因见下文源码分析）。
综上所述：虽然 ThreadLocal 提供了自动清理无效数据的能力，但是为了避免内存泄漏，在业务开发中应该及时调用 ThreadLocal#remove 清理无效的局部存储。
2.5 ThreadLocal 的使用场景
-
场景 1 - 无锁线程安全： ThreadLocal 提供了一种特殊的线程安全方式，从根本上避免资源竞争，也体现了空间换时间的思想；
-
场景 2 - 线程级别单例： 一般的单例对象是对整个进程可见的，使用 ThreadLocal 也可以实现线程级别的单例；
-
场景 3 - 共享参数： 如果一个模块有非常多地方需要使用同一个变量，相比于在每个方法中重复传递同一个参数，使用一个 ThreadLocal 全局变量也是另一种传递参数方式。
2.6 ThreadLocal 使用示例
我们采用 Android Handler 机制中的 Looper 消息循环作为 ThreadLocal 的学习案例：
// /frameworks/base/core/java/android/os/Looper.java public class Looper { // 静态 ThreadLocal 变量，全局共享同一个 ThreadLocal 对象 static final ThreadLocal<Looper> sThreadLocal = new ThreadLocal<Looper>(); private static void prepare(boolean quitAllowed) { if (sThreadLocal.get() != null) { throw new RuntimeException("Only one Looper may be created per thread"); } // 设置 ThreadLocal 变量的值，即设置当前线程关联的 Looper 对象 sThreadLocal.set(new Looper(quitAllowed)); } public static Looper myLooper() { // 获取 ThreadLocal 变量的值，即获取当前线程关联的 Looper 对象 return sThreadLocal.get(); } public static void prepare() { prepare(true); } ... } 示例代码
new Thread(new Runnable() { @Override public void run() { Looper.prepare(); // 两个线程独立访问不同的 Looper 对象 System.out.println(Looper.myLooper()); } }).start(); new Thread(new Runnable() { @Override public void run() { Looper.prepare(); // 两个线程独立访问不同的 Looper 对象 System.out.println(Looper.myLooper()); } }).start(); 要点如下：
- 1、Looper 中的 ThreadLocal 被声明为静态类型，泛型参数为 Looper，全局共享同一个 ThreadLocal 对象；
- 2、
Looper#prepare()中调用ThreadLocal#set()设置当前线程关联的 Looper 对象； - 3、
Looper#myLooper()中调用ThreadLocal#get()获取当前线程关联的 Looper 对象。
我们可以画出 Looper 中访问 ThreadLocal 的 Timethreads 图，可以看到不同线程独立访问不同的 Looper 对象，即线程间不存在资源竞争。
Looper ThreadLocal 示意图
2.7 阿里巴巴 ThreadLocal 编程规约
在《阿里巴巴 Java 开发手册》中，亦有关于 ThreadLocal API 的编程规约：
- 【强制】 SimpleDateFormate 是线程不安全的类，一般不要定义为 static ****变量。如果定义为 static，必须加锁，或者使用 DateUtils 工具类（使用 ThreadLocal 做线程隔离）。
DataFormat.java
private static final ThreadLocal<DataFormat> df = new ThreadLocal<DateFormat>(){ // 设置缺省值 / 初始值 @Override protected DateFormat initialValue(){ return new SimpleDateFormat("yyyy-MM-dd"); } }; // 使用： DateUtils.df.get().format(new Date()); - 【参考】 （原文过于啰嗦，以下是小彭翻译转述）ThreadLocal 变量建议使用 static 全局变量，可以保证变量在类初始化时创建，所有类实例可以共享同一个静态变量（例如，在 Android Looper 的案例中，ThreadLocal 就是使用 static 修饰的全局变量）。
- 【强制】 必须回收自定义的 ThreadLocal 变量，尤其在线程池场景下，线程经常被反复用，如果不清理自定义的 ThreadLocal 变量，则可能会影响后续业务逻辑和造成内存泄漏等问题。尽量在代码中使用 try-finally 块回收，在 finally 中调用 remove() 方法。
3. ThreadLocal 源码分析
这一节，我们来分析 ThreadLocal 中主要流程的源码。
3.1 ThreadLocal 的属性
ThreadLocal 只有一个 threadLocalHashCode 散列值属性：
-
1、threadLocalHashCode 相当于 ThreadLocal 的自定义散列值，在创建 ThreadLocal 对象时，会调用
nextHashCode()方法分配一个散列值； -
2、ThreadLocal 每次调用
nextHashCode()方法都会将散列值追加HASH_INCREMENT，并记录在一个全局的原子整型nextHashCode中。
提示： ThreadLocal 的散列值序列为：0、HASH_INCREMENT、HASH_INCREMENT * 2、HASH_INCREMENT * 3、…
public class ThreadLocal<T> { // 疑问 1：OK，threadLocalHashCode 类似于 hashCode()，那为什么 ThreadLocal 不重写 hashCode() // ThreadLocal 的散列值，类似于重写 Object#hashCode() private final int threadLocalHashCode = nextHashCode(); // 全局原子整型，每调用一次 nextHashCode() 累加一次 private static AtomicInteger nextHashCode = new AtomicInteger(); // 疑问：为什么 ThreadLocal 散列值的增量是 0x61c88647？ private static final int HASH_INCREMENT = 0x61c88647; private static int nextHashCode() { // 返回上一次 nextHashCode 的值，并累加 HASH_INCREMENT return nextHashCode.getAndAdd(HASH_INCREMENT); } } static class ThreadLocalMap { // 详细源码分析见下文 ... } 不出意外的话又有小朋友出来举手提问了🙋🏻♀️：
- 🙋🏻♀️疑问 1：OK，threadLocalHashCode 类似于 hashCode()，那为什么 ThreadLocal 不重写 hashCode()？
如果重写 Object#hashCode()，那么 threadLocalHashCode 散列值就会对所有散列表生效。而 threadLocalHashCode 散列值是专门针对数组为 2 的整数幂的散列表设计的，在其他散列表中不一定表现良好。因此 ThreadLocal 没有重写 Object#hashCode()，让 threadLocalHashCode 散列值只在 ThreadLocal 内部的 ThreadLocalMap 使用。
常规做法
public class ThreadLocal<T> { // ThreadLocal 未重写 hashCode() @Override public int hashCode() { return threadLocalHashCode; } } - 🙋🏻♀️疑问 2：为什么使用 ThreadLocal 作为散列表的 Key，而不是常规思维用 Thread Id 作为 Key？
如果使用 Thread Id 作为 Key，那么就需要在每个 ThreadLocal 对象中维护散列表，而不是每个线程维护一个散列表。此时，当多个线程并发访问同一个 ThreadLocal 对象中的散列表时，就需要通过加锁保证线程安全。而 ThreadLocal 的方案让每个线程访问独立的散列表，就可以从根本上规避线程竞争。
3.2 ThreadLocal 的 API
分析代码，可以总结出 ThreadLocal API 的用法和注意事项：
- 1、ThreadLocal#get： 获取当前线程的副本；
- 2、ThreadLocal#set： 设置当前线程的副本；
- 3、ThreadLocal#remove： 移除当前线程的副本；
- 4、ThreadLocal#initialValue： 由子类重写来设置缺省值：
- 4.1 如果未命中（Map 取值为 nul），则会调用
initialValue()创建并设置缺省值； - 4.2 ThreadLocal 的缺省值只会在缓存未命中时创建，即缺省值采用懒初始化策略；
- 4.3 如果先设置后又移除副本，再次 get 获取副本未命中时依然会调用
initialValue()创建并设置缺省值。
- 4.1 如果未命中（Map 取值为 nul），则会调用
- 5、ThreadLocal#withInitial： 方便设置缺省值，而不需要实现子类。
在 ThreadLocal 的 API 会通过 getMap() 方法获取当前线程的 Thread 对象中的 threadLocals 字段，这是线程隔离的关键。
ThreadLocal.java
public ThreadLocal() { // do nothing } // 子类可重写此方法设置缺省值（方法命名为 defaultValue 获取更贴切） protected T initialValue() { // 默认不提供缺省值 return null; } // 帮助方法：不重写 ThreadLocal 也可以设置缺省值 // supplier：缺省值创建工厂 public static <S> ThreadLocal<S> withInitial(Supplier<? extends S> supplier) { return new SuppliedThreadLocal<>(supplier); } // 1. 获取当前线程的副本 public T get() { Thread t = Thread.currentThread(); // ThreadLocalMap 详细源码分析见下文 ThreadLocalMap map = getMap(t); if (map != null) { // 存在匹配的Entry ThreadLocalMap.Entry e = map.getEntry(this); if (e != null) { T result = (T)e.value; return result; } } // 未命中，则获取并设置缺省值（即缺省值采用懒初始化策略） return setInitialValue(); } // 获取并设置缺省值 private T setInitialValue() { T value = initialValue(); // 其实源码中是并不是直接调用set()，而是复制了一份 set() 方法的源码 // 这是为了防止子类重写 set() 方法后改变缺省值逻辑 set(value); return value; } // 2. 设置当前线程的副本 public void set(T value) { Thread t = Thread.currentThread(); ThreadLocalMap map = getMap(t); if (map != null) map.set(this, value); else // 直到设置值的时候才创建（即 ThreadLocalMap 采用懒初始化策略） createMap(t, value); } // 3. 移除当前线程的副本 public void remove() { ThreadLocalMap m = getMap(Thread.currentThread()); if (m != null) m.remove(this); } ThreadLocalMap getMap(Thread t) { // 重点：获取当前线程的 threadLocals 字段 return t.threadLocals; } // ThreadLocal 缺省值帮助类 static final class SuppliedThreadLocal<T> extends ThreadLocal<T> { private final Supplier<? extends T> supplier; SuppliedThreadLocal(Supplier<? extends T> supplier) { this.supplier = Objects.requireNonNull(supplier); } // 重写 initialValue() 以设置缺省值 @Override protected T initialValue() { return supplier.get(); } } 3.3 InheritableThreadLocal 如何继承父线程的局部存储？
父线程在创建子线程时，在子线程的构造方法中会批量将父线程的有效键值对数据拷贝到子线程，因此子线程可以复用父线程的局部存储。
Thread.java
// Thread 对象的实例数据 ThreadLocal.ThreadLocalMap threadLocals = null; ThreadLocal.ThreadLocalMap inheritableThreadLocals = null; // 构造方法 public Thread() { init(null, null, "Thread-" + nextThreadNum(), 0); } private void init(ThreadGroup g, Runnable target, String name, long stackSize, AccessControlContext acc, boolean inheritThreadLocals) { ... if (inheritThreadLocals && parent.inheritableThreadLocals != null) // 拷贝父线程的 InheritableThreadLocal 散列表 this.inheritableThreadLocals = ThreadLocal.createInheritedMap(parent.inheritableThreadLocals); ... } ThreadLocal.java
// 带 Map 的构造方法 static ThreadLocalMap createInheritedMap(ThreadLocalMap parentMap) { return new ThreadLocalMap(parentMap); } static class ThreadLocalMap { private ThreadLocalMap(ThreadLocalMap parentMap) { // 详细源码分析见下文 ... Object value = key.childValue(e.value); ... } } InheritableThreadLocal 在拷贝父线程散列表的过程中，会调用 InheritableThreadLocal#childValue() 尝试转换为子线程需要的数据，默认是直接传递，可以重写这个方法修改拷贝的数据。
InheritableThreadLocal.java
public class InheritableThreadLocal<T> extends ThreadLocal<T> { // 参数：父线程的数据 // 返回值：拷贝到子线程的数据，默认为直接传递 protected T childValue(T parentValue) { return parentValue; } 下面，我们来分析 ThreadLocalMap 的源码。
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 |
提示： 关于 “重建 Key 对象不等价的问题” 的更多详细论述过程，我们在这篇文章里讨论过 《WeakHashMap 和 HashMap 的区别是什么，何时使用？》，去看看。
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 思维导图
参考资料
- 数据结构与算法分析 · Java 语言描述（第 5 章 · 散列）—— [美] Mark Allen Weiss 著
- 算法导论（第 11 章 · 散列表）—— [美] Thomas H. Cormen 等 著
- 《阿里巴巴Java开发手册》 杨冠宝 编著
- 数据结构与算法之美（第 18~22 讲） —— 王争 著，极客时间 出品
- ThreadLocal 和 ThreadLocalMap源码分析 —— KingJack 著
- Why 0x61c88647? —— Dr. Heinz M. Kabutz 著
