深入剖析大厂经典面试题之ThreadLocal原理（涉及斐波拉契散列、线性探测、扩容以及内存泄露问题）

1、简介

ThreadLocal也称线程变量，它是一个以ThreadLocal对象为键、任意对象为值的存储结构(ThreadLocal中ThreadLocalMap的Entry结构)，这个结构会被附带在线程上，以此来做线程数据的隔离。ThreadLocal是维持线程的封闭性的一种规范，它提供set()/get()等方法维护和访问线程中存储的私有副本，ThreadLocal通常用于防止对可变的单实例变量或者全局变量进行共享。

ThreadLocal和synchronized两者经常会被拿出来一起讨论，虽然二者都是用来解决多线程中资源的访问冲突等问题，但是二者存在本质上的区别具有完全不一样的使用场景。这里简单说明一下：

synchronized是通过线程阻塞（加锁），只允许同步区域内同一时刻只有一个线程在执行来实现共享资源的互斥访问，牺牲了程序的执行时间

ThreadLocal是每个线程具有不同的数据副本，通过线程数据隔离互不影响的方式来解决并发资源的访问，牺牲的是存储空间

相比之下ThreadLocal的使用场景比较特殊，在某些需要以线程为作用域做资源隔离的场景下使用，比如应用程序中以线程为单位发起的数据库连接，可以通过将JDBC的连接保存到ThreadLocal对象中来保证线程安全。

ThreadLocal的简单使用示例：

深入剖析大厂经典面试题之ThreadLocal原理（涉及斐波拉契散列、线性探测、扩容以及内存泄露问题）

java.lang.ThreadLocal.ThreadLocalMap中的代码片段：

static class ThreadLocalMap {
    /** 默认的初始Entry的大小 */
    private static final int INITIAL_CAPACITY = 16;
    /** 定义一个Entry数组，用来存放多个ThreadLocal */
    private Entry[] table;
    /** 数组扩容因子 */
    private int threshold;
    /** 记录table中Entry的个数 */
    private int size = 0;

    /**
     * ThreadLocalMap中有静态内部类Entry，Entry继承了WeakReference弱引用，引用类型是ThreadLocal<?>
     */
    static class Entry extends WeakReference<ThreadLocal<?>> {
        /** The value associated with this ThreadLocal. */
        Object value;

        /**
          *  key是ThreadLocal对象
          *   value是ThreadLocal中的value
          */
        Entry(ThreadLocal<?> k, Object v) {
            super(k);
            value = v;
        }
    }

    /**
      * ThreadLocalMap的构造函数
      */
    ThreadLocalMap(ThreadLocal<?> firstKey, Object firstValue) {
        // 初始化数组，默认16
        table = new Entry[INITIAL_CAPACITY];
        // 通过一定的算法计算ThreadLocal在table数组中的索引 -> 这个3.2中我做了详细讲解
        int i = firstKey.threadLocalHashCode & (INITIAL_CAPACITY - 1);
        // 赋值table[i]位置Entry对象key -> ThreadLocal | value -> 传入的值
        table[i] = new Entry(firstKey, firstValue);
        // 记录 table中Entry的个数
        size = 1;
        // 计算扩容因子 16 * 2 / 3
        setThreshold(INITIAL_CAPACITY);
    }
}

看了上述的代码和代码的注释，可以很明确的看到Thread、ThreadLocal、ThreadLocalMap这三者关系

Thread线程类内部维护了一个ThreadLocalMap成员变量（ThreadLocalMap的实例）

ThreadLocalMap是ThreadLocal的静态内部类，此外ThreadLocalMap内部维护了一个Entry数组table，用来存放多个ThreadLocal

ThreadLocal类用于存储以线程为作用域的数据，用于数据隔离

从这张图能非常清晰的看出，ThreadLocal只是ThreadLocalMap操作的一个入口，它提供的set()/get()方法供程序员开发使用，具体的数据存取都是在ThreadLocalMap中去实现，而每一个Thread对象中持有一个ThreadLocalMap对象，不难看出ThreadLocalMap才是实现的关键和重难点。

3、ThreadLocal源码分析

ThreadLocal是JDK提供给程序员直接使用的类，其重点在于ThreadLocalMap，因此下面主要介绍ThreadLocal的关键成员属性、如何通过魔数计算散列均匀的索引、get()/set()方法。重点将在ThreadLocalMap中去介绍。

3.1 ThreadLocal重要成员属性

ThreadLocal中有几个重要的成员属性如下所示：

3.2 ThreadLocal计算其在ThreadLocalMap的Entry数组的下标

上面的魔数与斐波拉契散列有关，它可以让生成出来的值或者说ThreadLocal在table的Index均匀的分布在2^n的数组大小中，我们通过计算的值再取模数组的length-1，就能得到ThreadLocal在ThreadLocalMap的Entry中的索引下标。下面通过自己写一个测试案例来简单的讲述下这个魔数和计算数组索引：

package com.lizba.currency.threadlocal;

import java.util.concurrent.atomic.AtomicInteger;

/**
 * <p>
 *      通过魔数0x61c88647来计算数组索引下标
 * </p>
 *
 * @Author: Liziba
 * @Date: 2021/7/2 22:02
 */
public class ThreadLocal0x61c88647 {

    /** 定义数组的初始大小 */
    private static final int INITIAL_CAPACITY = 16;
    /** 魔数 -> 可以让生成出来的值或者说ThreadLocal的Index均匀的分布在2^n的数组大小中 */
    private static final int HASH_INCREMENT = 0x61c88647;
    /** 魔数 */
    private final int threadLocalHashCode = nextHashCode();
    /** 定义一个线程安全的原子类AtomicInteger，用于魔数的累加 */
    private static AtomicInteger nextHashCode = new AtomicInteger();
    
    /** 计算下一个code(魔数累加) */
    private static int nextHashCode() {
        return nextHashCode.getAndAdd(HASH_INCREMENT);
    }

    /**
     * 根据生成的均匀分布的随机数threadLocalHashCode 取模(%) （数组大小INITIAL_CAPACITY-1（因为数组索引从0开始）)
     *
     * @return
     */
    public int index() {
        return this.threadLocalHashCode & (INITIAL_CAPACITY - 1);
    }
}

ThreadLocalMap为空初始化 -> createMap(t, value)

void createMap(Thread t, T firstValue) {
    // 实例化一个ThreadLocalMap，赋值给当前线程的threadLocals成员变量
    // new ThreadLocalMap(this, firstValue) -> 源码分析放到后面ThreadLocalMap中去讲解，这里只需要明白这是初始化一个ThreadLocalMap即可，加上第二节中三者的说明，也能理解其中的原理。
    t.threadLocals = new ThreadLocalMap(this, firstValue);
}

4、ThreadLocalMap源码分析

ThreadLocalMap是整篇文章的重点，ThreadLocalMap是ThreadLocal的内部类，它提供了真正数据存取的能力；ThreadLocalMap为每个Thread都维护了一个table，这个table中的每一个Entry代表一个ThreadLocal（注意一个线程可以定义多个ThreadLocal，此时它们会存储在table中不同的下标位置）和vlaue的组合。接下来通过源码一层层的分析ThreadLocalMap的原理及实现。

4.1 Entry源码分析

Entry是ThreadLocalMap的静态内部类，它是一个负责元素存储的key-value键值对数据结构，key是ThreadLocal，value是ThreadLocal传入的相关的值。这里有一个重点知识，Entry继承了WeakReference，所以很明显的看出ThreadLocal<?> k将会是一个弱引用，弱引用容易被JVM垃圾收集器回收，因此可能导致内存泄露的问题（后续在详细分析，这里的重点是ThreadLocalMap的实现）。

4.3 set()方法源码分析

在ThreadLocal的set()方法中，当ThreadLocalMap不为空时，也就是说在上面4.2初始化之后，当前线程再次调用ThreadLocal的set()方法将会执行的是下面的逻辑。

set()方法中有三个重点知识：

当计算的Entry下标位置不存在数据时，直接插入

当存在数据时，通过线性探测来解决hash冲突

当table中的Entry个数达到扩容阈值时，进行扩容处理

set() -> replaceStaleEntry(key, value, i)方法：

这个方法非常重要，它负责对过期的entry(引用被垃圾收集器回收了，因为Entry的key是弱引用，前面Entry源码中有介绍)进行清理，寻找合适的位置插入新的节点、对数组中已有的Entry做rehash寻找新的下标。设计源码的作者思路主要分为如下两个方面：

向前搜索，寻找其他同样key为null被GC的Entry节点，并记录下最后遍历到的Entry索引，遍历结束条件是Entry为null。这样的好处是为了清理这些Entry的key被GC了的Entry节点。

向后遍历，ThreadLocal不同于hashmap，它是开放地址法，因此当前索引位置不一定就是这个Entry存放的位置，可能第一次存放的时候发生了hash碰撞，Entry的存储发生了后移，因此要向后遍历，寻找当前与Entry的key相等的槽。

关于replaceStaleEntry(key, value, i)方法，我画了一个简图，图中并未包含所有场景，具体请详细阅读源码（非常精彩的设计思路），假设进入这个方法时staleSlot = 8，并且key的hashcode = 0xx68

源码分析：

private void replaceStaleEntry(ThreadLocal<?> key, Object value,
                               int staleSlot) {
    Entry[] tab = table;
    int len = tab.length;
    Entry e;
    
    // 将当前索引的值赋值给slotToExpunge，用于清理
    int slotToExpunge = staleSlot;
    
    // 向前搜索，知道tab[i] == null
    // 如果tab[i] 不为空，但是tab[i]的key为空，也就是和当前节点一样的情况，key被GC了，那么将当前索引下标的值赋值给slotToExpunge，记录最小的索引值，后续从这里开始清理
    for (int i = prevIndex(staleSlot, len);
         (e = tab[i]) != null;
         i = prevIndex(i, len))
        if (e.get() == null)
            slotToExpunge = i;

  
    // 向后遍历，直到tab[i]==null
    for (int i = nextIndex(staleSlot, len);
         (e = tab[i]) != null;
         i = nextIndex(i, len)) {
        
        // 获取当前索引位置Entry的key
        ThreadLocal<?> k = e.get();

        // 如果key相等，证明当前这个节点后移到这里了，需要替换value
        // 替换的时候我们可以做一些优化，因为我们第一次命中的索引出存在Entry但是Entry的key被GC了，也就是说无法被访问了，而我们这个节点是因为后移才存储在这里，这个时候我们这个节点是不是可以重新放回去呢？放回去后下次不是一次就命中了么？就不需要往后遍历寻找了么？
        if (k == key) {
            
            // 更新value
            e.value = value;

            // tab[i] 与 tab[staleSlot]交换位置
            tab[i] = tab[staleSlot];
            tab[staleSlot] = e;

            // 如果往前探索的第一个key=null的索引下标和当前替换回去的索引相同
            // 由于做了交换，我们又能保证前面不存在key == null的节点了，那么只需将替换后的i的值赋值给slotToExpunge，这样可以减少清理的循环次数
            if (slotToExpunge == staleSlot)
                slotToExpunge = i;
            // 做清理工作和rehash
            cleanSomeSlots(expungeStaleEntry(slotToExpunge), len);
            return;
        }

       // 初始进来的时候我们有这句代码 slotToExpunge == staleSlot
        // 所以如果slotToExpunge == staleSlot仍然成立，并且当前的key == null，那么我们就把当前的下标值赋值给slotToExpunge，很好理解还是为了缩小清理的范围，大师们对提升性能总是那么极致
        if (k == null && slotToExpunge == staleSlot)
            slotToExpunge = i;
    }

    // 执行到了这里，说明替换失败了，没找到要么就是它的key也被GC了，要么就是它是第一次set
    // 但是当前Entry的key是null，那我们就放这里吧，毕竟这个Entry也用不了
    tab[staleSlot].value = null;
    tab[staleSlot] = new Entry(key, value);

    // slotToExpunge != staleSlo表名需要清理key为null的Entry
    if (slotToExpunge != staleSlot)
        cleanSomeSlots(expungeStaleEntry(slotToExpunge), len);
}

expungeStaleEntry(int staleSlot)源码分析：

expungeStaleEntry(int staleSlot)主要做了三件事

从staleSlot索引开始往后遍历到第一个Entry节点不为空的下标这段区间中key=null的Entry节点清空处理

在遍历中如果key != null 需要做rehash处理，因为前面可能存在节点被清空了，重新根据k.threadLocalHashCode & (len - 1)计算索引，往后遍历寻找第一个为null的Entry移动到这里

返回i，这个i是从staleSlot往后遍历到的第一个为null的Entry，这个值返回为了cleanSomeSlots(int i, int n)，去清理后面的Entry，这里你可能会疑问为啥不直接用expungeStaleEntry(int staleSlot)方法直接全部遍历一遍得了，但是你可以发现源码这分块的清理做了优化，具体实现请看后面的cleanSomeSlots(int i, int n)讲解

cleanSomeSlots(int i, int n)源码分析：

cleanSomeSlots(int i, int n)也是对上面expungeStaleEntry(int staleSlot)方法中找到的第一个为null的Entry节点到table.legth的区间范围内，Entry不为空但Entry的key为空的节点进行清理，这个清理不一定会进行到table的最后，因为它做了一个(n >>>= 1) != 0判断，如果在n无符号右移1 == 0 时，并且这右移的期间没有发现满足清理的Entry那么就会结束往后寻找。

n >>>=1 相当于 n= n>>>1，位运算右移一位相当于除以2

举个例子，如果i=5，n=16，此时如果在往后遍历四次，也就是到i=9，仍然没有满足e != null && e.get() == null的Entry，那么后续10-16就不再遍历了，这些都是对算法的优化。

4.4.2 expungeStaleEntries()源码分析

expungeStaleEntries()源码非常简单，从table数组的第一个节点到最后一个节点中e != null && e.get() == null的Entry执行上面的expungeStaleEntry(int staleSlot)方法。

4.4.3 resize()源码分析

resize()的源码也比较简单，主要做了三个操作：

实例化一个原先大小两倍的数组newTab

遍历原先的旧数组中的每一个节点，将不为空的Entry节点计算其在新数组中的下标，放入新的数组中，放入的方式与set一致，使用线性探测解决hash冲突，注意如果节点不为空，key为空，需要将节点和节点的value置为空，帮助GC

设置新的扩容阈值，记录新的size，替换table的引用

getEntryAfterMiss(key, i, e)源码分析：

进入这个方法存在多种情况：

节点发生了hash冲突，节点插入后移了（这种情况也有可能会被GC）
节点为发送hash冲突，但是key被GC了

深入剖析大厂经典面试题之ThreadLocal原理（涉及斐波拉契散列、线性探测、扩容以及内存泄露问题）

深入剖析大厂经典面试题之ThreadLocal原理（涉及斐波拉契散列、线性探测、扩容以及内存泄露问题）
我们知道Entry extends WeakReference<ThreadLocal<?>>，也就是说ThreadLocal作为一个弱引用key，如果没有被强引用所引用，那么它将活不过下次GC，这个也是上面产生那么多Entry的key为null的原因。当弱引用被指向的对象被GC那么将会导致我们程序员无法访问到这个Entry中的value对象，再加上table中的Entry它不发生hash冲突或者扩容（这些方法中都会去处理这些key为null的Entry，java大佬们一直在优化这些问题），如果线程长期存活，那么这些key为null的Entry的value将永远得不到GC，从而内存泄露。

5.2 防止内存泄露

防止内存泄露的处理方式很简单，ThreadLocal提供了remove()方法，供程序员主动清除Entry

ThreadLocal的remove()方法：

深入剖析大厂经典面试题之ThreadLocal原理（涉及斐波拉契散列、线性探测、扩容以及内存泄露问题）

继续阅读

27 Best Free Eclipse Plug-ins for Java Developer to be ProductiveCode Quality PluginsText Editor PluginsDependency ManagementVersion Control Integration PluginsFramework Development Continuous Integration Related PluginsOther Utility Plugins

Java String.format方法的简单使用

neo4j之cypher使用文档

Dijkstra--简易版（最短路径）

GitHub连夜封杀！这份阿里 10W 字内部 Java 字面试手册到底有多强？

spark/scala关于【资源文件】加载方法概述外部文件加载方案测试资源文件打包入jar包中小结

mybatis_入门程序Mybatis入门

AOP编程_Android优雅权限框架(1)概念基础，2021金三银四前言正文大纲正文

面试题解析：你接口测试是怎么做的？

Effective Java 8:通用程序设计

OOM三种类型

工厂模式-三种类型

【递归】高效率求2的n次幂

win10本地scala和spark安装安装scala安装spark

scala (3) Function 和 Method

hdu7108哈希