作者：小傅哥
博客：https://

沉淀、分享、成長，讓自己和他人都能有所收獲！😄

一、前言

說到底，你真的會造火箭嗎？

常說面試造火箭，入職擰螺絲。但你真的有造火箭的本事嗎，大部分都是不敢承認(rèn)自己的知識盲區(qū)和技術(shù)瓶頸以及經(jīng)驗不足的自嘲。

面試時：

• 我希望你懂?dāng)?shù)據(jù)結(jié)構(gòu)，因為這樣的你在使用HashMap、ArrayList、LinkedList，更加得心應(yīng)手。
• 我希望你懂散列算法，因為這樣的你在設(shè)計路由時，會有很多選擇；除法散列法、平方散列法、斐波那契（Fibonacci）散列法等。
• 我希望你懂開源代碼，因為這樣的你在遇到問題時，可以快速定位，還可能創(chuàng)造出一些系統(tǒng)服務(wù)的中間件，來更好的解耦系統(tǒng)。
• 我希望你懂設(shè)計模式，因為這樣的你可以寫出可擴(kuò)展、易維護(hù)的程序，讓整個團(tuán)隊都能向更好的方向發(fā)展。

所以，從不是CRUD選擇了你，也不是造螺絲讓你成為工具人。而是你的技術(shù)能力決定你的眼界，眼界又決定了你寫出的代碼！

二、面試題

謝飛機(jī)，小記 還沒有拿到 offer 的飛機(jī)，早早起了床，吃完兩根油條，又跑到公司找面試官取經(jīng)！

面試官：飛機(jī)，聽坦克說，你最近貪黑起早的學(xué)習(xí)呀。

謝飛機(jī)：嗯嗯，是的，最近頭發(fā)都快掉沒了！

面試官：那今天我們聊聊 ThreadLocal，一般可以用在什么場景中？

謝飛機(jī)：嗯，ThreadLocal 要解決的是線程內(nèi)資源共享 (This class provides thread-local variables.)，所以一般會用在全鏈路監(jiān)控中，或者是像日志框架 MDC 這樣的組件里。

面試官：飛機(jī)不錯哈，最近確實學(xué)習(xí)了。那你知道 ThreadLocal是怎樣的數(shù)據(jù)結(jié)構(gòu)嗎，采用的是什么散列方式？

謝飛機(jī)：數(shù)組？嗯，怎么散列的不清楚…

面試官：那 ThreadLocal 有內(nèi)存泄漏的風(fēng)險，是怎么發(fā)生的呢？另外你了解在這個過程的，探測式清理和啟發(fā)式清理嗎？

謝飛機(jī)：這…，盲區(qū)了，盲區(qū)了，可樂我放桌上了，我回家再看看書！

三、ThreadLocal 分析

ThreadLocal，作者：Josh Bloch and Doug Lea，兩位大神👍

如果僅是日常業(yè)務(wù)開發(fā)來看，這是一個比較冷門的類，使用頻率并不高。并且它提供的方法也非常簡單，一個功能只是潦潦數(shù)行代碼。但，如果深挖實現(xiàn)部分的源碼，就會發(fā)現(xiàn)事情并不那么簡單。這里涉及了太多的知識點(diǎn)，包括；數(shù)據(jù)結(jié)構(gòu)、開放尋址法、斐波那契散列、神奇的0x61c88647、弱引用Reference、過期key探測清理和啟發(fā)式清理等等。

接下來，我們就逐步學(xué)習(xí)這些盲區(qū)知識。本文涉及了較多的代碼和實踐驗證圖稿，歡迎關(guān)注公眾號：bugstack蟲洞棧，回復(fù)下載得到一個鏈接打開后，找到ID：19🤫獲取！*

1. 應(yīng)用場景

1.1 SimpleDateFormat

private SimpleDateFormat f = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");

public void seckillSku(){
    String dateStr = f.format(new Date());
    // 業(yè)務(wù)流程
}

你寫過這樣的代碼嗎？如果還在這么寫，那就已經(jīng)犯了一個線程安全的錯誤。SimpleDateFormat，并不是一個線程安全的類。

1.1.1 線程不安全驗證

private static SimpleDateFormat f = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");

public static void main(String[] args) {
    while (true) {
        new Thread(() -> {
            String dateStr = f.format(new Date());
            try {
                Date parseDate = f.parse(dateStr);
                String dateStrCheck = f.format(parseDate);
                boolean equals = dateStr.equals(dateStrCheck);
                if (!equals) {
                    System.out.println(equals + " " + dateStr + " " + dateStrCheck);
                } else {
                    System.out.println(equals);
                }
            } catch (ParseException e) {
                System.out.println(e.getMessage());
            }
        }).start();
    }
}

這是一個多線程下 SimpleDateFormat 的驗證代碼。當(dāng) equals 為false 時，證明線程不安全。運(yùn)行結(jié)果如下；

true
true
false 2020-09-23 11:40:42 2230-09-23 11:40:42
true
true
false 2020-09-23 11:40:42 2020-09-23 11:40:00
false 2020-09-23 11:40:42 2020-09-23 11:40:00
false 2020-09-23 11:40:00 2020-09-23 11:40:42
true
false 2020-09-23 11:40:42 2020-08-31 11:40:42
true

1.1.2 使用 ThreadLocal 優(yōu)化

為了線程安全最直接的方式，就是每次調(diào)用都直接 new SimpleDateFormat。但這樣的方式終究不是最好的，所以我們使用 ThreadLocal ，來優(yōu)化這段代碼。

private static ThreadLocal<SimpleDateFormat> threadLocal = ThreadLocal.withInitial(() -> new SimpleDateFormat("yyyy-MM-dd HH:mm:ss"));
public static void main(String[] args) {
    while (true) {
        new Thread(() -> {
            String dateStr = threadLocal.get().format(new Date());
            try {
                Date parseDate = threadLocal.get().parse(dateStr);
                String dateStrCheck = threadLocal.get().format(parseDate);
                boolean equals = dateStr.equals(dateStrCheck);
                if (!equals) {
                    System.out.println(equals + " " + dateStr + " " + dateStrCheck);
                } else {
                    System.out.println(equals);
                }
            } catch (ParseException e) {
                System.out.println(e.getMessage());
            }
        }).start();
    }
}

如上我們把 SimpleDateFormat ，放到 ThreadLocal 中進(jìn)行使用，即不需要重復(fù)new對象，也避免了線程不安全問題。測試結(jié)果如下；

true
true
true
true
true
true
true
...

1.2 鏈路追蹤

近幾年基于谷歌Dapper論文實現(xiàn)非入侵全鏈路追蹤，使用的越來越廣了。簡單說這就是一套監(jiān)控系統(tǒng)，但不需要你硬編碼的方式進(jìn)行監(jiān)控方法，而是基于它的設(shè)計方案采用 javaagent + 字節(jié)碼 插樁的方式，動態(tài)采集方法執(zhí)行信息。如果你想了解字節(jié)碼插樁技術(shù)，可以閱讀我的字節(jié)碼編程專欄：https:///itstack-demo-agent/itstack-demo-agent.html

重點(diǎn)，動態(tài)采集方法執(zhí)行信息。這塊是主要部分，跟 ThreadLocal 相關(guān)。字節(jié)碼插樁解決的是非入侵式編程，那么在一次服務(wù)調(diào)用時，在各個系統(tǒng)間以及系統(tǒng)內(nèi)多個方法的調(diào)用，都需要進(jìn)行采集。這個時候就需要使用 ThreadLocal 記錄方法執(zhí)行ID，當(dāng)然這里還有跨線程調(diào)用使用的也是增強(qiáng)版本的 ThreadLocal，但無論如何基本原理不變。

1.2.1 追蹤代碼

這里舉例全鏈路方法調(diào)用鏈追蹤，部分代碼

public class TrackContext {

    private static final ThreadLocal<String> trackLocal = new ThreadLocal<>();

    public static void clear(){
        trackLocal.remove();
    }

    public static String getLinkId(){
        return trackLocal.get();
    }

    public static void setLinkId(String linkId){
        trackLocal.set(linkId);
    }

}

@Advice.OnMethodEnter()
public static void enter(@Advice.Origin("#t") String className, @Advice.Origin("#m") String methodName) {
    Span currentSpan = TrackManager.getCurrentSpan();
    if (null == currentSpan) {
        String linkId = UUID.randomUUID().toString();
        TrackContext.setLinkId(linkId);
    }
    TrackManager.createEntrySpan();
}

@Advice.OnMethodExit()
public static void exit(@Advice.Origin("#t") String className, @Advice.Origin("#m") String methodName) {
    Span exitSpan = TrackManager.getExitSpan();
    if (null == exitSpan) return;
    System.out.println("鏈路追蹤(MQ)：" + exitSpan.getLinkId() + " " + className + "." + methodName + " 耗時：" + (System.currentTimeMillis() - exitSpan.getEnterTime().getTime()) + "ms");
}

• 以上這部分就是非入侵監(jiān)控中，鏈路追蹤的過程。具體的案例和代碼可以參考閱讀，系列專題文章《基于JavaAgent的全鏈路監(jiān)控》
• 這也只是其中一個實現(xiàn)方式，字節(jié)碼插樁使用的是 byte-buddy，其實還是使用，ASM 或者 Javassist。

1.2.2 測試結(jié)果

測試方法

配置參數(shù)：-javaagent:E:\itstack\GIT\itstack.org\itstack-demo-agent\itstack-demo-agent-06\target\itstack-demo-agent-06-1.0.0-SNAPSHOT.jar=testargs

public void http_lt1(String name) {
    try {
        Thread.sleep((long) (Math.random() * 500));
    } catch (InterruptedException e) {
        e.printStackTrace();
    }
    System.out.println("測試結(jié)果：hi1 " + name);
    http_lt2(name);
}

public void http_lt2(String name) {
    try {
        Thread.sleep((long) (Math.random() * 500));
    } catch (InterruptedException e) {
        e.printStackTrace();
    }
    System.out.println("測試結(jié)果：hi2 " + name);
    http_lt3(name);
}

運(yùn)行結(jié)果

onTransformation：class org.itstack.demo.test.ApiTest
測試結(jié)果：hi2 悟空
測試結(jié)果：hi3 悟空
鏈路追蹤(MQ)：90c7d543-c7b8-4ec3-af4d-b4d4f5cff760 org.itstack.demo.test.ApiTest.http_lt3 耗時：104ms

init: 256MB max: 3614MB used: 44MB committed: 245MB use rate: 18%
init: 2MB max: 0MB used: 13MB committed: 14MB use rate: 95%

name: PS Scavenge count:0 took:0 pool name:[PS Eden Space, PS Survivor Space]
name: PS MarkSweep count:0 took:0 pool name:[PS Eden Space, PS Survivor Space, PS Old Gen]
-------------------------------------------------------------------------------------------------
鏈路追蹤(MQ)：90c7d543-c7b8-4ec3-af4d-b4d4f5cff760 org.itstack.demo.test.ApiTest.http_lt2 耗時：233ms

init: 256MB max: 3614MB used: 44MB committed: 245MB use rate: 18%
init: 2MB max: 0MB used: 13MB committed: 14MB use rate: 96%

name: PS Scavenge count:0 took:0 pool name:[PS Eden Space, PS Survivor Space]
name: PS MarkSweep count:0 took:0 pool name:[PS Eden Space, PS Survivor Space, PS Old Gen]

• 以上是鏈路追蹤的測試結(jié)果，可以看到兩個方法都會打出相應(yīng)的編碼ID：90c7d543-c7b8-4ec3-af4d-b4d4f5cff760。
• 這部分也就是全鏈路追蹤的核心應(yīng)用，而且還可以看到這里打印了一些系統(tǒng)簡單的JVM監(jiān)控指標(biāo)，這也是監(jiān)控的一部分。

咳咳，除此之外所有需要活動方法調(diào)用鏈的，都需要使用到 ThreadLocal，例如 MDC 日志框架等。接下來我們開始詳細(xì)分析 ThreadLocal 的實現(xiàn)。

2. 數(shù)據(jù)結(jié)構(gòu)

了解一個功能前，先了解它的數(shù)據(jù)結(jié)構(gòu)。這就相當(dāng)于先看看它的地基，有了這個根本也就好往后理解了。以下是 ThreadLocal 的簡單使用以及部分源碼。

new ThreadLocal<String>().set("小傅哥");

private void set(ThreadLocal<?> key, Object value) {
   
    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)]) {
    ...
}

從這部分源碼中可以看到，ThreadLocal 底層采用的是數(shù)組結(jié)構(gòu)存儲數(shù)據(jù)，同時還有哈希值計算下標(biāo)，這說明它是一個散列表的數(shù)組結(jié)構(gòu)，演示如下圖；

如上圖是 ThreadLocal 存放數(shù)據(jù)的底層數(shù)據(jù)結(jié)構(gòu)，包括知識點(diǎn)如下；

1. 它是一個數(shù)組結(jié)構(gòu)。
2. Entry，這里沒用再打開，其實它是一個弱引用實現(xiàn)，static class Entry extends WeakReference<ThreadLocal<?>>。這說明只要沒用強(qiáng)引用存在，發(fā)生GC時就會被垃圾回收。
3. 數(shù)據(jù)元素采用哈希散列方式進(jìn)行存儲，不過這里的散列使用的是 斐波那契（Fibonacci）散列法，后面會具體分析。
4. 另外由于這里不同于HashMap的數(shù)據(jù)結(jié)構(gòu)，發(fā)生哈希碰撞不會存成鏈表或紅黑樹，而是使用開放尋址法進(jìn)行存儲。也就是同一個下標(biāo)位置發(fā)生沖突時，則+1向后尋址，直到找到空位置或垃圾回收位置進(jìn)行存儲。

3. 散列算法

既然 ThreadLocal 是基于數(shù)組結(jié)構(gòu)的開放尋址法存儲，那就一定會有哈希的計算。但我們翻閱源碼后，發(fā)現(xiàn)這個哈希計算與 HashMap 中的散列求數(shù)組下標(biāo)計算的哈希方式不一樣。如果你忘記了HashMap，可以翻閱文章《HashMap 源碼分析，插入、查找》、《HashMap 擾動函數(shù)、負(fù)載因子》

3.1 神秘的數(shù)字 0x61c88647

當(dāng)我們查看 ThreadLocal 執(zhí)行設(shè)置元素時，有這么一段計算哈希值的代碼；

private static final int HASH_INCREMENT = 0x61c88647;

private static int nextHashCode() {
    return nextHashCode.getAndAdd(HASH_INCREMENT);
}

看到這里你一定會有這樣的疑問，這是什么方式計算哈希？這個數(shù)字怎么來的？

講到這里，其實計算哈希的方式，絕不止是我們平?？吹?String 獲取哈希值的一種方式，還包括；除法散列法、平方散列法、斐波那契（Fibonacci）散列法、隨機(jī)數(shù)法等。

而 ThreadLocal 使用的就是 斐波那契（Fibonacci）散列法 + 開放尋址法存儲數(shù)據(jù)到數(shù)組結(jié)構(gòu)中。之所以使用斐波那契數(shù)列，是為了讓數(shù)據(jù)更加散列，減少哈希碰撞。具體來自數(shù)學(xué)公式的計算求值，公式：f(k) = ((k * 2654435769) >> X) << Y對于常見的32位整數(shù)而言，也就是 f(k) = (k * 2654435769) >> 28

第二個問題，數(shù)字 0x61c88647，是怎么來的？

其實這是一個哈希值的黃金分割點(diǎn)，也就是 0.618，你還記得你學(xué)過的數(shù)學(xué)嗎？計算方式如下；

// 黃金分割點(diǎn)：(√5 - 1) / 2 = 0.6180339887     1.618:1 == 1:0.618
System.out.println(BigDecimal.valueOf(Math.pow(2, 32) * 0.6180339887).intValue());      //-1640531527

• 學(xué)過數(shù)學(xué)都應(yīng)該知道，黃金分割點(diǎn)是，(√5 - 1) / 2，取10位近似 0.6180339887。
• 之后用 2 ^ 32 * 0.6180339887，得到的結(jié)果是：-1640531527，也就是 16 進(jìn)制的，0x61c88647。這個數(shù)呢也就是這么來的

3.2 驗證散列

既然，Josh Bloch 和 Doug Lea，兩位老爺子選擇使用斐波那契數(shù)列，計算哈希值。那一定有它的過人之處，也就是能更好的散列，減少哈希碰撞。

接下來我們按照源碼中獲取哈希值和計算下標(biāo)的方式，把這部分代碼提出出來做驗證。

3.2.1 部分源碼

private static AtomicInteger nextHashCode = new AtomicInteger();
 
private static final int HASH_INCREMENT = 0x61c88647;

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

// 獲取下標(biāo)
int i = key.threadLocalHashCode & (len-1);

如上，源碼部分采用的是 AtomicInteger，原子方法計算下標(biāo)。我們不需要保證線程安全，只需要簡單實現(xiàn)即可。另外 ThreadLocal 初始化數(shù)組長度是16，我們也初始化這個長度。

3.2.2 單元測試

@Test
public void test_idx() {
    int hashCode = 0;
    for (int i = 0; i < 16; i++) {
        hashCode = i * HASH_INCREMENT + HASH_INCREMENT;
        int idx = hashCode & 15;
        System.out.println("斐波那契散列：" + idx + " 普通散列：" + (String.valueOf(i).hashCode() & 15));
    }
}

測試代碼部分，采用的就是斐波那契數(shù)列，同時我們加入普通哈希算法進(jìn)行比對散列效果。當(dāng)然String 這個哈希并沒有像 HashMap 中進(jìn)行擾動

測試結(jié)果：

斐波那契散列：7 普通散列：0
斐波那契散列：14 普通散列：1
斐波那契散列：5 普通散列：2
斐波那契散列：12 普通散列：3
斐波那契散列：3 普通散列：4
斐波那契散列：10 普通散列：5
斐波那契散列：1 普通散列：6
斐波那契散列：8 普通散列：7
斐波那契散列：15 普通散列：8
斐波那契散列：6 普通散列：9
斐波那契散列：13 普通散列：15
斐波那契散列：4 普通散列：0
斐波那契散列：11 普通散列：1
斐波那契散列：2 普通散列：2
斐波那契散列：9 普通散列：3
斐波那契散列：0 普通散列：4

Process finished with exit code 0

發(fā)現(xiàn)沒？，斐波那契散列的非常均勻，普通散列到15個以后已經(jīng)開發(fā)生產(chǎn)碰撞。這也就是斐波那契散列的魅力，減少碰撞也就可以讓數(shù)據(jù)存儲的更加分散，獲取數(shù)據(jù)的時間復(fù)雜度基本保持在O(1)。

4. 源碼解讀

4.1 初始化

new ThreadLocal<>()

初始化的過程也很簡單，可以按照自己需要的泛型進(jìn)行設(shè)置。但在 ThreadLocal 的源碼中有一點(diǎn)非常重要，就是獲取 threadLocal 的哈希值的獲取，threadLocalHashCode。

private final int threadLocalHashCode = nextHashCode();

/**
 * Returns the next hash code.
 */
private static int nextHashCode() {
    return nextHashCode.getAndAdd(HASH_INCREMENT);
}

如源碼中，只要實例化一個 ThreadLocal ，就會獲取一個相應(yīng)的哈希值，則例我們做一個例子。

@Test
public void test_threadLocalHashCode() throws Exception {
    for (int i = 0; i < 5; i++) {
        ThreadLocal<Object> objectThreadLocal = new ThreadLocal<>();
        Field threadLocalHashCode = objectThreadLocal.getClass().getDeclaredField("threadLocalHashCode");
        threadLocalHashCode.setAccessible(true);
        System.out.println("objectThreadLocal：" + threadLocalHashCode.get(objectThreadLocal));
    }
}

因為 threadLocalHashCode ，是一個私有屬性，所以我們實例化后通過上面的方式進(jìn)行獲取哈希值。

objectThreadLocal：-1401181199
objectThreadLocal：239350328
objectThreadLocal：1879881855
objectThreadLocal：-774553914
objectThreadLocal：865977613

Process finished with exit code 0

這個值的獲取，也就是計算 ThreadLocalMap，存儲數(shù)據(jù)時，ThreadLocal 的數(shù)組下標(biāo)。只要是這同一個對象，在set、get時，就可以設(shè)置和獲取對應(yīng)的值。

4.2 設(shè)置元素

4.2.1 流程圖解

new ThreadLocal<>().set("小傅哥");

設(shè)置元素的方法，也就這么一句代碼。但設(shè)置元素的流程卻涉及的比較多，在詳細(xì)分析代碼前，我們先來看一張設(shè)置元素的流程圖，從圖中先了解不同情況的流程之后再對比著學(xué)習(xí)源碼。流程圖如下；

乍一看可能感覺有點(diǎn)暈，我們從左往右看，分別有如下知識點(diǎn)；
0. 中間是 ThreadLocal 的數(shù)組結(jié)構(gòu)，之后在設(shè)置元素時分為四種不同的情況，另外元素的插入是通過斐波那契散列計算下標(biāo)值，進(jìn)行存放的。

1. 情況1，待插入的下標(biāo)，是空位置直接插入。
2. 情況2，待插入的下標(biāo)，不為空，key 相同，直接更新
3. 情況3，待插入的下標(biāo)，不為空，key 不相同，開放尋址法尋址
4. 情況4，不為空，key 不相同，碰到過期key。其實情況4，遇到的是弱引用發(fā)生GC時，產(chǎn)生的情況。碰到這種情況，ThreadLocal 會進(jìn)行探測清理過期key，這部分清理內(nèi)容后續(xù)講解。

4.2.2 源碼分析

private void set(ThreadLocal<?> key, Object value) {
    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)]) {
        ThreadLocal<?> k = e.get();
        if (k == key) {
            e.value = value;
            return;
        }
        if (k == null) {
            replaceStaleEntry(key, value, i);
            return;
        }
    }
    tab[i] = new Entry(key, value);
    int sz = ++size;
    if (!cleanSomeSlots(i, sz) && sz >= threshold)
        rehash();
}

在有了上面的圖解流程，再看代碼部分就比較容易理解了，與之對應(yīng)的內(nèi)容包括，如下；

1. key.threadLocalHashCode & (len-1);，斐波那契散列，計算數(shù)組下標(biāo)。
2. Entry，是一個弱引用對象的實現(xiàn)類，static class Entry extends WeakReference<ThreadLocal<?>>，所以在沒有外部強(qiáng)引用下，會發(fā)生GC，刪除key。
3. for循環(huán)判斷元素是否存在，當(dāng)前下標(biāo)不存在元素時，直接設(shè)置元素 tab[i] = new Entry(key, value);。
4. 如果元素存在，則會判斷是否key值相等 if (k == key)，相等則更新值。
5. 如果不相等，就到了我們的 replaceStaleEntry，也就是上圖說到的探測式清理過期元素。

綜上，就是元素存放的全部過程，整體結(jié)構(gòu)的設(shè)計方式非常贊👍，極大的利用了散列效果，也把弱引用使用的非常6！

4.3 擴(kuò)容機(jī)制

4.3.1 擴(kuò)容條件

只要使用到數(shù)組結(jié)構(gòu)，就一定會有擴(kuò)容

if (!cleanSomeSlots(i, sz) && sz >= threshold)
    rehash();

在我們閱讀設(shè)置元素時，有以上這么一塊代碼，判斷是否擴(kuò)容。

• 首先，進(jìn)行啟發(fā)式清理*cleanSomeSlots*，把過期元素清理掉，看空間是否
• 之后，判斷sz >= threshold，其中 threshold = len * 2 / 3，也就是說數(shù)組中天填充的元素，大于 len * 2 / 3，就需要擴(kuò)容了。
• 最后，就是我們要分析的重點(diǎn)，rehash();，擴(kuò)容重新計算元素位置。

4.3.2 源碼分析

探測式清理和校驗

private void rehash() {
    expungeStaleEntries();
    
    // Use lower threshold for doubling to avoid hysteresis
    if (size >= threshold - threshold / 4)
        resize();
}

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)
            expungeStaleEntry(j);
    }
}

• 這部分是主要是探測式清理過期元素，以及判斷清理后是否滿足擴(kuò)容條件，size >= threshold * 3/4
• 滿足后執(zhí)行擴(kuò)容操作，其實擴(kuò)容完的核心操作就是重新計算哈希值，把元素填充到新的數(shù)組中。

rehash() 擴(kuò)容

private void resize() {
    Entry[] oldTab = table;
    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) {
                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;
}

以上，代碼就是擴(kuò)容的整體操作，具體包括如下步驟；

1. 首先把數(shù)組長度擴(kuò)容到原來的2倍，oldLen * 2，實例化新數(shù)組。
2. 遍歷for，所有的舊數(shù)組中的元素，重新放到新數(shù)組中。
3. 在放置數(shù)組的過程中，如果發(fā)生哈希碰撞，則鏈?zhǔn)椒樠印?/li>
4. 同時這還有檢測key值的操作 if (k == null)，方便GC。

4.4 獲取元素

4.4.1 流程圖解

new ThreadLocal<>().get();

同樣獲取元素也就這么一句代碼，如果沒有分析源碼之前，你能考慮到它在不同的數(shù)據(jù)結(jié)構(gòu)下，獲取元素時候都做了什么操作嗎。我們先來看下圖，分為如下種情況；

按照不同的數(shù)據(jù)元素存儲情況，基本包括如下情況；

1. 直接定位到，沒有哈希沖突，直接返回元素即可。
2. 沒有直接定位到了，key不同，需要開放尋址式尋找。
3. 沒有直接定位到了，key不同，開放尋址式尋找，遇到GC清理元素，需要探測式清理，再尋找元素。

4.4.2 源碼分析

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)
            expungeStaleEntry(i);
        else
            i = nextIndex(i, len);
        e = tab[i];
    }
    return null;
}

好了，這部分就是獲取元素的源碼部分，和我們圖中列舉的情況是一致的。expungeStaleEntry，是發(fā)現(xiàn)有 key == null 時，進(jìn)行清理過期元素，并把后續(xù)位置的元素，前移。

4.5 元素清理

4.5.1 探測式清理[expungeStaleEntry]

探測式清理，是以當(dāng)前遇到的 GC 元素開始，向后不斷的清理。直到遇到 null 為止，才停止 rehash 計算Rehash until we encounter null。

expungeStaleEntry

private int expungeStaleEntry(int staleSlot) {
    Entry[] tab = table;
    int len = tab.length;
    // expunge entry at staleSlot
    tab[staleSlot].value = null;
    tab[staleSlot] = null;
    size--;
    // Rehash until we encounter 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) {
            e.value = null;
            tab[i] = null;
            size--;
        } else {
            int h = k.threadLocalHashCode & (len - 1);
            if (h != i) {
                tab[i] = null;
                // Unlike Knuth 6.4 Algorithm R, we must scan until
                // null because multiple entries could have been stale.
                while (tab[h] != null)
                    h = nextIndex(h, len);
                tab[h] = e;
            }
        }
    }
    return i;
}

以上，探測式清理在獲取元素中使用到； new ThreadLocal<>().get() -> map.getEntry(this) -> getEntryAfterMiss(key, i, e) -> expungeStaleEntry(i)

4.5.2 啟發(fā)式清理[cleanSomeSlots]

Heuristically scan some cells looking for stale entries.
This is invoked when either a new element is added, or
another stale one has been expunged. It performs a
logarithmic number of scans, as a balance between no
scanning (fast but retains garbage) and a number of scans
proportional to number of elements, that would find all
garbage but would cause some insertions to take O(n) time.

啟發(fā)式清理，有這么一段注釋，大概意思是；試探的掃描一些單元格，尋找過期元素，也就是被垃圾回收的元素。當(dāng)添加新元素或刪除另一個過時元素時，將調(diào)用此函數(shù)。它執(zhí)行對數(shù)掃描次數(shù)，作為不掃描（快速但保留垃圾）和與元素數(shù)量成比例的掃描次數(shù)之間的平衡，這將找到所有垃圾，但會導(dǎo)致一些插入花費(fèi)O（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) {
            n = len;
            removed = true;
            i = expungeStaleEntry(i);
        }
    } while ( (n >>>= 1) != 0);
    return removed;
}

while 循環(huán)中不斷的右移進(jìn)行尋找需要被清理的過期元素，最終都會使用 expungeStaleEntry 進(jìn)行處理，這里還包括元素的移位。

四、總結(jié)

• 寫到這算是把 ThreadLocal 知識點(diǎn)的一角分析完了，在 ThreadLocal 的家族里還有 Netty 中用到的，FastThreadLocal。在全鏈路跨服務(wù)線程間獲取調(diào)用鏈路，還有 TransmittableThreadLocal，另外還有 JDK 本身自帶的一種線程傳遞解決方案 InheritableThreadLocal。但站在本文的基礎(chǔ)上，了解了最基礎(chǔ)的原理，在理解其他的拓展設(shè)計，就更容易接受了。
• 此外在我們文中分析時經(jīng)常會看到探測式清理，其實這也是非常耗時。為此我們在使用 ThreadLocal 一定要記得 new ThreadLocal<>().remove(); 操作。避免弱引用發(fā)生GC后，導(dǎo)致內(nèi)存泄漏的問題。
• 最后，你發(fā)現(xiàn)了嗎！我們學(xué)習(xí)這樣的底層原理性知識，都離不開數(shù)據(jù)結(jié)構(gòu)和良好的設(shè)計方案，或者說是算法的身影。這些代碼才是支撐整個系統(tǒng)良好運(yùn)行的地基，如果我們可以把一些思路抽取到我們開發(fā)的核心業(yè)務(wù)流程中，也是可以大大提升性能的。

五、系列推薦

• 握草，你竟然在代碼里下毒！
• 一次代碼評審，差點(diǎn)過不了試用期！
• HashMap核心知識，擾動函數(shù)、負(fù)載因子、擴(kuò)容鏈表拆分，深度學(xué)習(xí)
• HashMap數(shù)據(jù)插入、查找、刪除、遍歷，源碼分析
• 重學(xué)Java設(shè)計模式(22個真實開發(fā)場景)