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

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

一、前言

說(shuō)到底，你真的會(huì)造火箭嗎？

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

面試時(shí)：

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

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

二、面試題

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

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

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

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

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

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

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

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

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

三、ThreadLocal 分析

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

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

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

1. 應(yīng)用場(chǎ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ù)流程
}

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

1.1.1 線程不安全驗(yàn)證

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

這是一個(gè)多線程下 SimpleDateFormat 的驗(yàn)證代碼。當(dāng) equals 為false 時(shí)，證明線程不安全。運(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 ，來(lái)優(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對(duì)象，也避免了線程不安全問(wèn)題。測(cè)試結(jié)果如下；

true
true
true
true
true
true
true
...

1.2 鏈路追蹤

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

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

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 + " 耗時(shí)：" + (System.currentTimeMillis() - exitSpan.getEnterTime().getTime()) + "ms");
}

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

1.2.2 測(cè)試結(jié)果

測(cè)試方法

配置參數(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("測(cè)試結(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("測(cè)試結(jié)果：hi2 " + name);
    http_lt3(name);
}

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

onTransformation：class org.itstack.demo.test.ApiTest
測(cè)試結(jié)果：hi2 悟空
測(cè)試結(jié)果：hi3 悟空
鏈路追蹤(MQ)：90c7d543-c7b8-4ec3-af4d-b4d4f5cff760 org.itstack.demo.test.ApiTest.http_lt3 耗時(shí)：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 耗時(shí)：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]

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

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

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

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

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)存儲(chǔ)數(shù)據(jù)，同時(shí)還有哈希值計(jì)算下標(biāo)，這說(shuō)明它是一個(gè)散列表的數(shù)組結(jié)構(gòu)，演示如下圖；

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

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

3. 散列算法

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

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

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

private static final int HASH_INCREMENT = 0x61c88647;

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

看到這里你一定會(huì)有這樣的疑問(wèn)，這是什么方式計(jì)算哈希？這個(gè)數(shù)字怎么來(lái)的？

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

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

第二個(gè)問(wèn)題，數(shù)字 0x61c88647，是怎么來(lái)的？

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

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

3.2 驗(yàn)證散列

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

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

3.2.1 部分源碼

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

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

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

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

3.2.2 單元測(cè)試

@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));
    }
}

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

測(cè)試結(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)沒(méi)？，斐波那契散列的非常均勻，普通散列到15個(gè)以后已經(jīng)開發(fā)生產(chǎn)碰撞。這也就是斐波那契散列的魅力，減少碰撞也就可以讓數(shù)據(jù)存儲(chǔ)的更加分散，獲取數(shù)據(jù)的時(shí)間復(fù)雜度基本保持在O(1)。

4. 源碼解讀

4.1 初始化

new ThreadLocal<>()

初始化的過(guò)程也很簡(jiǎn)單，可以按照自己需要的泛型進(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);
}

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

@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));
    }
}

因?yàn)?threadLocalHashCode ，是一個(gè)私有屬性，所以我們實(shí)例化后通過(guò)上面的方式進(jìn)行獲取哈希值。

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

Process finished with exit code 0

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

4.2 設(shè)置元素

4.2.1 流程圖解

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

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

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

1. 情況1，待插入的下標(biāo)，是空位置直接插入。
2. 情況2，待插入的下標(biāo)，不為空，key 相同，直接更新
3. 情況3，待插入的下標(biāo)，不為空，key 不相同，開放尋址法尋址
4. 情況4，不為空，key 不相同，碰到過(guò)期key。其實(shí)情況4，遇到的是弱引用發(fā)生GC時(shí)，產(chǎn)生的情況。碰到這種情況，ThreadLocal 會(huì)進(jìn)行探測(cè)清理過(guò)期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();
}

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

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

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

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

4.3.1 擴(kuò)容條件

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

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

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

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

4.3.2 源碼分析

探測(cè)式清理和校驗(yàn)

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);
    }
}

• 這部分是主要是探測(cè)式清理過(guò)期元素，以及判斷清理后是否滿足擴(kuò)容條件，size >= threshold * 3/4
• 滿足后執(zhí)行擴(kuò)容操作，其實(shí)擴(kuò)容完的核心操作就是重新計(jì)算哈希值，把元素填充到新的數(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ù)組長(zhǎng)度擴(kuò)容到原來(lái)的2倍，oldLen * 2，實(shí)例化新數(shù)組。
2. 遍歷for，所有的舊數(shù)組中的元素，重新放到新數(shù)組中。
3. 在放置數(shù)組的過(guò)程中，如果發(fā)生哈希碰撞，則鏈?zhǔn)椒樠印?/li>
4. 同時(shí)這還有檢測(cè)key值的操作 if (k == null)，方便GC。

4.4 獲取元素

4.4.1 流程圖解

new ThreadLocal<>().get();

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

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

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

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 時(shí)，進(jìn)行清理過(guò)期元素，并把后續(xù)位置的元素，前移。

4.5 元素清理

4.5.1 探測(cè)式清理[expungeStaleEntry]

探測(cè)式清理，是以當(dāng)前遇到的 GC 元素開始，向后不斷的清理。直到遇到 null 為止，才停止 rehash 計(jì)算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;
}

以上，探測(cè)式清理在獲取元素中使用到； 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ā)式清理，有這么一段注釋，大概意思是；試探的掃描一些單元格，尋找過(guò)期元素，也就是被垃圾回收的元素。當(dāng)添加新元素或刪除另一個(gè)過(guò)時(shí)元素時(shí)，將調(diào)用此函數(shù)。它執(zhí)行對(duì)數(shù)掃描次數(shù)，作為不掃描（快速但保留垃圾）和與元素?cái)?shù)量成比例的掃描次數(shù)之間的平衡，這將找到所有垃圾，但會(huì)導(dǎo)致一些插入花費(fèi)O（n）時(shí)間。

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)行尋找需要被清理的過(guò)期元素，最終都會(huì)使用 expungeStaleEntry 進(jìn)行處理，這里還包括元素的移位。

四、總結(jié)

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

五、系列推薦

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