深入剖析大廠經典面試題之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哈希