浅谈 ThreadLocal-五八三

1.介绍

ThreadLocal 叫做 线程变量，即填充的变量属于当前线程，用于在多线程环境中保存线程局部变量。填充的变量对其他线程是隔离的，当前线程独享，所以不存在多线程间共享的问题。

当通过 ThreadLocal 填充变量时，ThreadLocal 为当前线程创建了一个副本 ThreadLocal.ThreadLocalMap，并保存该变量。ThreadLocal.ThreadLocalMap 的底层数据结构是数组。通过当前 ThreadLocal 的 hash 值计算索引位置，所以当前 ThreadLocal 在当前线程只能存放一个数据。

从 Entry 类的源代码中，可以知道 ThreadLocal 的引用 k 被传递给 WeakReference 的构造函数，所以 ThreadLocalMap 中的 key 为 ThreadLocal 的弱引用。被存放在强引用的容器中的弱引用，在容器没有清理前，即使对象已经被垃圾回收，弱引用对象也无法被释放，这就会导致内存泄漏。因此在设置和查找的过程中，存在清理元素的操作，但这些操作比较耗时，因此在使用完毕后应当手动清理 new ThreadLocal<>().remove();。

// 一个 Thread 代表一个线程；每个线程里都有一个 ThreadLocalMap
public class Thread implements Runnable{
    ThreadLocal.ThreadLocalMap threadLocals = null;
}

// ThreadLocal.ThreadLocalMap
static class ThreadLocalMap{
    // 存放键值对
    private Entry[] table;
    
    // 初始容量
    private static final int INITIAL_CAPACITY = 16;
    
    // 数组中当前键值对数量
    private int size = 0;
    
    // 扩容界限
    private int threshold;
    
    // 键值对；弱引用，当没有强引用指向时，发生 GC 时就会被垃圾回收
    static class Entry extends WeakReference<ThreadLocal<?>> {
        /** The value associated with this ThreadLocal. */
        Object value;


        Entry(ThreadLocal<?> k, Object v) {
            super(k);
            value = v;
        }
    }

}

2.散列算法

获取哈希值的散列算法包括：除法散列法、平方散列法、斐波那契（Fibonacci）散列法、随机数法等。ThreadLocal 使用的散列算法是 斐波那契（Fibonacci）散列法，在发生碰撞时，通过开放寻址的方法寻找下一个位置。其公式如下所示

$HASH\_INCREMENT = 1640531527$

$hash(i) = i*HASH\_INCREMENT + HASH\_INCREMENT$

2.1 特殊数字 0x61c88647

$HASH\_INCREMENT=0x61c88647=1640531527$ 是一个特殊的数字，它是一个哈希值的黄金分割点，使得散列时散列的足够均匀，减少哈希碰撞。通过下面的方式可以计算得到：

// hash_increment = -1640531527
int hash_increment = BigDecimal.valueOf(Math.pow(2,32) * 0.6180339887).intValue();
// hash_increment = 1640531527
hash_increment *= -1;

2.2 ThreadLocal 计算 hash

ThreadLocal 通过 AtomicInteger 实现哈希计算；AtomicInteger 被 $static$ 修饰，是静态变量，属于类；每当有一个 ThreadLocal 被实例化时，通过 AtomicInteger 增加一个 HASH_INCREMENT。

public class ThreadLocal<T>{
    // 当前 ThreadLocal 对象的哈希值；每次实例化都会调用 nextHashCode() 获取哈希值
    private final int threadLocalHashCode = nextHashCode();
    
    // Integer类型的原子操作类型
    private static AtomicInteger nextHashCode = new AtomicInteger();
    
    private static final int HASH_INCREMENT = 0x61c88647;
    

    // 计算哈希值
    private static int nextHashCode() {
        return nextHashCode.getAndAdd(HASH_INCREMENT);
    }

}

3.初始化

ThreadLocal 通过无参构造函数进行实例化，同时根据需要设置泛型。在实例化的过程，计算 hash 值。

public ThreadLocal() {
}

4.设置元素

设置元素时，主要有以下几种情况：

情况1：直接更新待插入的下标为空，直接插入
情况2：待插入的下标不为空，key 相同
情况3：待插入的下标不为空，key 不相同，开放式寻址
情况4：待插入的下标不为空，key = null，碰到过期 key，清理过期元素，并在该位置设置元素

// ThreadLocal$set
public void set(T value) {
    // 获取当前线程

    Thread t = Thread.currentThread();

    // 获取当前线程的 ThreadLocalMap

    ThreadLocalMap map = getMap(t);

    if (map != null) {

        // 调用 ThreadLocalMap 的 set() 方法设置元素
        map.set(this, value);
    } else {
        // 给当前线程创建 ThreadLocalMap，并设置元素
        createMap(t, value);
    }

}

// ThreadLocal.ThreadLocalMap$set
private void set(ThreadLocal<?> key, Object value) {
    // 键值对数组
    Entry[] tab = table;


    // 数组长度
    int len = tab.length;


    // 通过当前 ThreadLocal 的 hash 值计算索引位置
    int i = key.threadLocalHashCode & (len-1);
    

    // 开放寻址法，寻找一个空位置
    for (Entry e = tab[i];e != null;e = tab[i = nextIndex(i, len)]) {
        // 获取当前键值对的索引，相当于 key
        ThreadLocal<?> k = e.get();
        // 情况2：待插入的下标不为空，key 相同，直接更新
        if (k == key) {
            e.value = value;
            return;
        }
        // 情况4：待插入的下标不为空，key = null，碰到过期 key，清理过期元素，并在该位置设置元素
        if (k == null) {
            // 探测式清理过期元素
            replaceStaleEntry(key, value, i);
            return;
        }
    }
    
     // 进入了 for 循环，则是情况3：待插入的下标不为空，key 不相同，开放式寻址
     // 未进入 for 循环，则是情况1：待插入的下标为空，直接插入

    tab[i] = new Entry(key, value);
    int sz = ++size;
    // cleanSomeSlots 进行启发式清理
    // 当没有元素清理并且数组中元素大于界限时，进行扩容
    if (!cleanSomeSlots(i, sz) && sz >= threshold)
        rehash();
}

5.获取元素

获取元素主要有以下几种情况：

情况1：直接命中，返回元素
情况2：没有直接命中，开放式寻址，遇到key相同的键值对，则返回元素
情况3：没有直接命中，开放式寻址，key=null，探测式清理，继续开放式寻址

// ThreadLocal$get
public T get() {
    // 获取当前线程

    Thread t = Thread.currentThread();

    // 获取当前线程的 ThreadLocalMap

    ThreadLocalMap map = getMap(t);

    if (map != null) {

        // 获取键值对
        ThreadLocalMap.Entry e = map.getEntry(this);
        if (e != null) {
            @SuppressWarnings("unchecked")
            T result = (T)e.value;
            return result;
        }
    }
    // map 为 null，创建 ThreadLocalMap，并返回 null
    return setInitialValue();
}

// ThreadLocal.ThreadLocalMap$getEntry
private Entry getEntry(ThreadLocal<?> key) {
    // 计算索引位置
    int i = key.threadLocalHashCode & (table.length - 1);
    Entry e = table[i];
    if (e != null && e.get() == key)
        // 情况1：直接命中，返回
        return e;
    else
        // 没有直接命中，开放式寻址
        return getEntryAfterMiss(key, i, e);
}

// ThreadLocal.ThreadLocalMap$getEntryAfterMiss
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)
            // 情况2：没有直接命中，开放式寻址，找到元素返回
            return e;
        if (k == null)
            // 情况3：没有直接命中，开放式寻址，key=null，探测式清理
            expungeStaleEntry(i);
        else
            i = nextIndex(i, len);
        e = tab[i];
    }
    return null;
}

6.清理元素

6.1 替换过期的ThreadLocal键值对条目

replaceStaleEntry() 方法在设置元素时被调用。其执行流程如下：

首先，通过遍历向前查找过期条目，记录最早出现的过期槽的索引
接着，在遍历过程中，如果找到了与指定 key 相等的 ThreadLocal，就将其对应的 value 值进行更新，并将其与过期槽交换位置，以保持哈希表的顺序；并调用相关方法清理过期条目
如果在遍历过程中没有找到与指定 key 相等的 ThreadLocal，就将新的键值对放入过期槽(staleSlot)中
最后，如果存在先前的过期条目，通过调用 expungeStaleEntry 方法清理这些过期条目，并重新哈希运行中的所有其他条目

// staleSlot：当前 key=null 的索引
private void replaceStaleEntry(ThreadLocal<?> key, Object value,int staleSlot) {
    // ThreadLocalMap中的Entry数组
    Entry[] tab = table;


    // Entry数组的长度
    int len = tab.length;


    Entry e;

    // 查找在该位置之前的过期条目(先前过期条目)
    // 我们一次清理整个运行，以避免由于垃圾收集器释放引用而导致的持续递增的重新哈希问题
    int slotToExpunge = staleSlot;
    for (int i = prevIndex(staleSlot, len);(e = tab[i]) != null;i = prevIndex(i, len))
        if (e.get() == null)
            slotToExpunge = i;

    // 查找运行中的关键字或尾随空槽，以先发生的为准
    for (int i = nextIndex(staleSlot, len);(e = tab[i]) != null;i = nextIndex(i, len)) {
        ThreadLocal<?> k = e.get();


        // 如果找到关键字，我们需要将其与过期条目交换以保持哈希表的顺序 
        // 然后可以将新过期槽或上面遇到的任何其他过期槽发送到 expungeStaleEntry 中，以删除或重新哈希运行中的所有其他条目
        if (k == key) {
            e.value = value;

            tab[i] = tab[staleSlot];
            tab[staleSlot] = e;

            // 如果存在先前的过期条目，则从先前的过期条目开始清除
            if (slotToExpunge == staleSlot)
                slotToExpunge = i;
            cleanSomeSlots(expungeStaleEntry(slotToExpunge), len);
            return;
        }

        // 如果没有先前条目，并且在向后的扫描中也没有过期的条目，则将 slotToExpunge 设置为当前的过期条目
        if (k == null && slotToExpunge == staleSlot)
            slotToExpunge = i;
    }

    // 如果没有找到关键字，则将新条目放入过期槽
    tab[staleSlot].value = null;
    tab[staleSlot] = new Entry(key, value);

    // 如果运行中有其他过期条目，则清除它们
    if (slotToExpunge != staleSlot)
        cleanSomeSlots(expungeStaleEntry(slotToExpunge), len);
}

6.2 探测式清理

expungeStaleEntry() 方法用于清理过期的 ThreadLocal 键值对条目，并进行重新哈希，以维护哈希表的结构和顺序，直到遇到 null 才停止。其过程如下：

首先，清除过期槽（staleSlot）上的条目，将其 value 值置为 null，并将该条目设为 null，同时减小 size 计数器
然后，从 staleSlot 的下一个位置开始重新哈希，直到遇到 null 为止
- 在重新哈希过程中，如果遇到 key 为 null 的条目，表示该条目已过期，将其 value 值置为 null，将该条目设为 null，并减小 size 计数器
- 如果遇到的条目的 key 不为 null，就根据其 threadLocalHashCode 重新计算哈希值 h，并与当前位置 i 进行比较
  - 如果 h 与 i 不相等，说明哈希冲突发生，将当前位置 i 的条目设为 null
  - 然后，在哈希表中找到合适的位置 h，直到遇到 null 为止
  - 将之前设为 null 的条目 e 放入新的位置 h 上，以保持哈希表的顺序

// staleSlot：key=null 的索引位置
// 返回 staleSlot 之后的下一个空槽的索引
// 在 staleSlot 和该空槽之间的所有槽位都已经被检查过是否需要清理
private int expungeStaleEntry(int staleSlot) {
    Entry[] tab = table;
    int len = tab.length;



    // 清理staleSlot 位置的条目
    tab[staleSlot].value = null;
    tab[staleSlot] = null;
    size--;

    // 重新哈希直到遇到null
    Entry e;
    int i;
    for (i = nextIndex(staleSlot, len);(e = tab[i]) != null;i = nextIndex(i, len)) {
        ThreadLocal<?> k = e.get();
        
        if (k == null) {
            // 如果 k=null，则清理该位置的条目
            e.value = null;
            tab[i] = null;
            size--;
        } else {
            // 如果 k!=null，则重新哈希
            int h = k.threadLocalHashCode & (len - 1);
            // 当索引位置与当前位置不同时，则从索引位置向后遍历，直到一个空位置
            if (h != i) {
                tab[i] = null;

                // 不同于 Knuth 6.4中 的算法R，我们必须扫描到 null，因为多个条目可能已过期
                while (tab[h] != null)
                    h = nextIndex(h, len);
                tab[h] = e;
            }
        }
    }
    return i;
}

6.3 启发式清理

cleanSomeSlots() 方法用于清理一些槽位中的过期条目。它会从给定的起始索引开始，逐个扫描一些槽位，检查对应的 ThreadLocal 引用是否已经被回收（即过期）。如果发现过期的条目，将其进行清理，并返回是否有条目被清理的结果。

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) {
            // 如果当前槽位存在且对应的 ThreadLocal 引用已经被回收（即过期）
            // 则进行调用探测式清理方法执行清理操作，并更新相关变量
            n = len;
            removed = true;
            i = expungeStaleEntry(i);
        }
    } while ( (n >>>= 1) != 0); // 按对数次数进行扫描；相当于每次除 2
    return removed;
}

代码中的注释翻译如下：

根据注释说明，这段代码的作用是启发式地扫描一些单元格，寻找过期的条目。当添加新元素或清理掉另一个过期条目时，会调用该方法。它执行对数次数的扫描，作为快速但保留垃圾和以元素数量为比例的扫描之间的平衡。这样的扫描既能发现所有的垃圾，又不会导致某些插入操作的时间复杂度为O(n)。

参数：

i：已知不包含过期条目的位置。扫描将从 i 之后的元素开始。

n：扫描控制参数。默认情况下，会扫描 log2(n) 个单元格，除非发现过期条目，此时会再额外扫描 log2(table.length)-1 个单元格。当从插入操作调用时，该参数是元素的数量；当从 replaceStaleEntry 调用时，该参数是表的长度。

返回值：

如果删除了任何过期的条目，则返回 true

文章版权归作者所有，未经允许请勿转载，侵权请联系 admin@trc20.tw 删除。

THE END

后端
# Java