关于android:ThreadLocal-超强图解这次终于懂了

本文已收录到 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：

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 的学习案例：

android.os.Looper.java

// /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() 创立并设置缺省值。
• 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 的属性：

能够看到，散列表必备底层数组 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 对象不等价的问题”的更多具体阐述过程，咱们在这篇文章里探讨过《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 著