概述

• ThreadLocal 介紹
• ThreadLocal 關(guān)鍵方法講解
• ThreadLocalMap 內(nèi)部類(lèi)介紹
• ThreadLocalMap 算法講解
• ThreadLocalMap 實(shí)現(xiàn)點(diǎn)講解

ThreadLocal

該類(lèi)提供了線(xiàn)程本地變量。該變量不同于普通的副本，因?yàn)樵L問(wèn)這個(gè)變量（通過(guò) get 或 set 方法）的每個(gè)線(xiàn)程都是自己獨(dú)立初始化該變量的。
ThreadLocal實(shí)例通常是Thread類(lèi)中典型的靜態(tài)私有屬性，由于關(guān)聯(lián)線(xiàn)程的狀態(tài)（比如，user ID 或 Transaction ID）

每個(gè)線(xiàn)程都持有其局部變量副本的隱式引用（即，每個(gè)線(xiàn)程都持有一個(gè)該變量的副本，因此，每個(gè)線(xiàn)程間的變量是獨(dú)立的），在其整個(gè)生命周期中，只要該引用可訪問(wèn)。一旦線(xiàn)程消亡，它的所有局部變量都會(huì)被GC（除非存在其他對(duì)該副本的引用）

ThreadLocal 關(guān)鍵方法

initialValue

protected T initialValue() {
    return null;
}

返回當(dāng)前線(xiàn)程局部變量的初始化值。這個(gè)方法將在 get 方法第一次調(diào)用時(shí)被調(diào)用，除非線(xiàn)程再次之前調(diào)用了 set 方法，那么該方法將不會(huì)被調(diào)用。通常，該方法只會(huì)被調(diào)用一次，但如果在后續(xù)的操作中，在調(diào)用了remove方法后調(diào)用get方法，那么該方法（initialValue）將會(huì)被調(diào)用多次（因?yàn)椋藭r(shí)線(xiàn)程的局部變量需要重新被初始化）。
也就是說(shuō)，該方法主要就是用于初始化線(xiàn)程的局部變量的，如果變量已經(jīng)通過(guò)其他方式初始化了（如，set方法），那么該方法就不會(huì)被調(diào)用。

get

public T get() {
    Thread t = Thread.currentThread();
    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;
        }
    }
    return setInitialValue();
}

返回當(dāng)前線(xiàn)程該局部變量的值。如果當(dāng)前線(xiàn)程該變量不存在，那么會(huì)調(diào)用“initialValue”方法進(jìn)行變量的初始化，并返回初始化后該變量的值。

set

public void set(T value) {
    Thread t = Thread.currentThread();
    ThreadLocalMap map = getMap(t);
    if (map != null)
        map.set(this, value);
    else
        createMap(t, value);
}

將當(dāng)前線(xiàn)程的局部變量設(shè)置為指定的值。大部分的子類(lèi)無(wú)需重寫(xiě)該方法，只需要重寫(xiě)“initialValue”方法來(lái)設(shè)置局部變量的值。

remove

public void remove() {
    ThreadLocalMap m = getMap(Thread.currentThread());
    if (m != null)
        m.remove(this);
}

刪除當(dāng)前線(xiàn)程該局部變量值。如果當(dāng)前線(xiàn)程在后續(xù)又調(diào)用了 get 方法，那么該局部變量的值會(huì)通過(guò)調(diào)用“initialValue”方法被重新初始化，除非再次期間“set”方法被調(diào)用了。這就是導(dǎo)致“initialValue”方法在當(dāng)前線(xiàn)程中被調(diào)用多次的原因。

ThreadLocalMap 內(nèi)部類(lèi)

ThreadLocalMap 是一個(gè)自定義的 hash map，它僅適用于維護(hù)線(xiàn)程的局部變量。該類(lèi)的所有操作都沒(méi)有暴露在 ThreadLocal 類(lèi)之外。為了幫助大對(duì)象和長(zhǎng)生命周期對(duì)象的使用，ThreadLocalMap 的 Key 使用 WeakReferences 類(lèi)型。然后，因?yàn)椴皇褂靡藐?duì)列，那么僅保證在 hash map 表空間不足的情況下，才會(huì)將無(wú)用的對(duì)象（stale entries）從 map 中移除。

ThreadLocalMap 是一個(gè)“懶”構(gòu)造（即，延遲構(gòu)造）。它會(huì)在至少有一個(gè) Entry 需要被輸入時(shí)，才會(huì)進(jìn)行構(gòu)造。

ThreadLocalMap 的 Key 是WeakReference 的子類(lèi)

ThreadLocalMap 是使用一個(gè) Entry 類(lèi)來(lái)表示一個(gè)線(xiàn)程局部變量（Key）和這個(gè)變量的值（Value）。 其中 Key 是 WeakReference 的子類(lèi)，而 WeakReference 所維護(hù)的引用通常就是 ThreadLocal。
注意：當(dāng) Entry#get() 返回 null 的時(shí)候，說(shuō)明對(duì)應(yīng)的 key 不存在了，即，這個(gè)對(duì)象已不再被任何對(duì)象引用了。因此，該 Entry 能被從當(dāng)前的 hash map 中清除。這樣的對(duì)象下 ThreadLocalMap 的操作中稱(chēng)為“stale entries”

WeakReference

WeakReference 是Java引用類(lèi)型的一種。用來(lái)描述非必須的對(duì)象，被弱引用關(guān)聯(lián)的對(duì)象只能生存到下一次垃圾收集發(fā)生之前。當(dāng)垃圾收集器工作時(shí)，無(wú)論當(dāng)前內(nèi)存是否足夠，都會(huì)回收掉只被弱引用關(guān)聯(lián)的對(duì)象。

ThreadLocalMap 其中涉及的 Hash 算法

理想情況下，不同的鍵都能轉(zhuǎn)化為不同的索引值。當(dāng)然，這只是理想情況，所以我們需要面對(duì)兩個(gè)或者多個(gè)鍵都會(huì)散列到相同的索引值的情況。

因此，一個(gè) Hash 算法主要有2個(gè)部分：Hash函數(shù)、解決碰撞的方法

ThreadLocalMap 使用的 Hash 函數(shù)是“斐波那契（Fibonacci）哈希法”；而解決碰撞的方法是“線(xiàn)性探測(cè)法”

斐波那契（Fibonacci）哈希法

在說(shuō)“斐波那契（Fibonacci）哈希法”前，我們先來(lái)說(shuō)說(shuō)“乘法哈希法”

• 乘法哈希法
  公式：hash(key) = floor( M/W * ( a * key mod W) )
  其中 floor 表示對(duì)表達(dá)式進(jìn)行下取整

注意：

1. 通常設(shè)置 M 為 2 的冪次方。
2. W 為計(jì)算機(jī)字長(zhǎng)大?。ㄒ矠?的冪次方）。
3. a 為一個(gè)非常接近于W的數(shù)。

其實(shí)，“乘法哈?！钡乃枷刖褪牵禾崛￡P(guān)鍵字 key 中間 k 位數(shù)字。

• 斐波那契（Fibonacci）哈希法
  而斐波那契（Fibonacci）哈希法就是當(dāng) “乘法哈希法” 的 a ≈ W/φ，1/φ ≈ (√5-1)/2 = 0.618 033 988 時(shí)情況。而，1/φ ≈ (√5-1)/2 = 0.618 033 988，可稱(chēng)為黃金分割點(diǎn)。

Q：那，為什么“斐波那契（Fibonacci）哈希法”能夠更好的將關(guān)鍵字 key 進(jìn)行散列了?

A：Why is 'a ≈ W/φ' special? It has to do with what happens to consecutive keys when they are hashed using the multiplicative method. As shown in Figure ‘Fibonacci Hashing’ , consecutive keys are spread out quite nicely. In fact, when we use 'a ≈ W/φ' to hash consecutive keys, the hash value for each subsequent key falls in between the two widest spaced hash values already computed. Furthermore, it is a property of the golden ratio, φ , that each subsequent hash value divides the interval into which it falls according to the golden ratio!

線(xiàn)性探測(cè)法（linear probing）

• “開(kāi)放地址”哈希表
  實(shí)現(xiàn)哈希表的另一種方式就是用大小為 M 的數(shù)組保存 N 個(gè)鍵值對(duì)，其中 M > N。我們需要依靠數(shù)組中的空位解決碰撞沖突?；谶@種策略的所有方法被統(tǒng)稱(chēng)為“開(kāi)放地址”哈希表

• 線(xiàn)性探測(cè)法（“開(kāi)放地址”哈希表的一種實(shí)現(xiàn)方式）
  開(kāi)放地址哈希表中最簡(jiǎn)單的方法叫做“線(xiàn)性探測(cè)”法：當(dāng)碰撞發(fā)生時(shí)（當(dāng)一個(gè)鍵的Hash值已經(jīng)被另一個(gè)不同的鍵占用），我們直接檢測(cè)哈希表中的下一個(gè)位置（將索引值加 1）。這樣的線(xiàn)性探測(cè)可能會(huì)產(chǎn)生三種結(jié)果：
  a）命中，該位置的鍵和被查找的鍵相同；
  b）未命中，鍵為空（該位置沒(méi)有鍵）
  c）繼續(xù)查找，該位置的鍵和被查找的鍵不同。

  我們用Hash函數(shù)找到鍵在數(shù)組中的索引，檢查其中的鍵和被查找的鍵是否相同。如果不同則繼續(xù)查找（將索引增大，到達(dá)數(shù)組結(jié)尾時(shí)折回?cái)?shù)組的開(kāi)頭），直到找到該鍵或者遇到一個(gè)空元素。
  我們習(xí)慣將檢查一個(gè)數(shù)組位置是否含有被查找的鍵的操作稱(chēng)作探測(cè)。在這里它可以等價(jià)于我們一直使用的比較，不過(guò)有些探測(cè)實(shí)際上是在測(cè)試鍵是否為空。

• 核心思想
  “開(kāi)放地址”哈希表的核心思想是與其將內(nèi)存用于鏈表，不如將它們作為哈希表的空元素。這些空元素可以作為查找結(jié)束的標(biāo)志。

• 刪除操作
  如何從基于線(xiàn)性探測(cè)的哈希表中刪除一個(gè)鍵？仔細(xì)想一想，你會(huì)發(fā)現(xiàn)直接將該鍵所在的位置設(shè)為null是不行的，因?yàn)檫@會(huì)使得在此位置之后的元素?zé)o法被查找。
  因此，我們需要將簇中被刪除鍵的右側(cè)的所有鍵重新插入哈希表。

• 鍵簇
  線(xiàn)性探測(cè)的平均成本取決于元素在插入數(shù)組后聚集成的一組連續(xù)的條目，也叫做鍵簇。
  如圖??所示，例如，在示例中插入鍵 C 會(huì)產(chǎn)生一個(gè)長(zhǎng)度為 3 的鍵簇（ A C S ）。這意味著插入 H 需要探測(cè) 4 次，因?yàn)?H 的Hash值為該鍵簇的第一個(gè)位置。

  
  

  顯然，短小的鍵簇才能保證較高的效率。隨著插入的鍵越來(lái)越多，這個(gè)要求很難滿(mǎn)足，較長(zhǎng)的鍵簇也會(huì)越來(lái)越多。另外因?yàn)椋ɑ诰鶆蛐约僭O(shè)）數(shù)組的每個(gè)位置都有相同的可能性被插入一個(gè)新鍵，長(zhǎng)鍵簇被選中的可能被短鍵簇更大，同時(shí)因?yàn)樾骆I的Hash值無(wú)論落在簇中的任何位置都會(huì)使簇的長(zhǎng)度加 1（甚至更多，如果這個(gè)簇和相鄰的簇之間只有一個(gè)空元素相隔的話(huà)）

• 線(xiàn)性探測(cè)法的性能分析
  開(kāi)放地址哈希表的性能依賴(lài)于 α = N/M 的比值。我們將 α 稱(chēng)為哈希表的使用率。對(duì)于基于拉鏈法的哈希表，α 是每條拉鏈表的長(zhǎng)度，因此一般大于 1 ；對(duì)于基于線(xiàn)性探測(cè)的哈希表，α 是表中已被占用的空間的比例，它是不可能大于 1 的。事實(shí)上，在 LinearProbingHashST 中我們不允許 α 達(dá)到 1 （列表被占滿(mǎn)），因?yàn)榇藭r(shí)未命中的查找會(huì)導(dǎo)致無(wú)限循環(huán)（因?yàn)椋谠夭淮嬖诘那闆r下，空元素作為查找結(jié)束的標(biāo)志）。為了保證性能，我們會(huì)動(dòng)態(tài)調(diào)整數(shù)組的大小來(lái)保證使用率在 1/8 到 1/2 之間。

假設(shè)J（均勻哈希假設(shè)）。我們使用的Hash函數(shù)能夠均勻并獨(dú)立地將所有的鍵散布于 0 到 M-1 之間。
討論。我們?cè)趯?shí)現(xiàn)Hash函數(shù)時(shí)隨意指定了很多參數(shù)，這顯然無(wú)法實(shí)現(xiàn)一個(gè)能夠在數(shù)學(xué)意義上均勻并獨(dú)立地散布所有鍵的Hash函數(shù)。事實(shí)上，深入的理論研究報(bào)告告訴我們想要找到一個(gè)計(jì)算簡(jiǎn)單但又擁有一致性和均勻性的Hash函數(shù)是不太可能的。在實(shí)際應(yīng)用中，和使用 Math.random() 生成隨機(jī)數(shù)一樣，大多數(shù)程序員都會(huì)滿(mǎn)足于隨機(jī)數(shù)生成器類(lèi)的Hash函數(shù)。很少人會(huì)去檢驗(yàn)獨(dú)立性，而這個(gè)性質(zhì)一般都不會(huì)滿(mǎn)足。

特別是當(dāng) α 約為 1/2 時(shí)，查找命中所需要的探測(cè)次數(shù)約為 3/2，未命中所需要的約為 5/2。當(dāng) α 趨于 1 時(shí)，這些估計(jì)值的精確度會(huì)下降，但不需要擔(dān)心這些情況，因?yàn)槲覀儠?huì)保證哈希表的使用率小于 1/2。
當(dāng)哈希表快滿(mǎn)的時(shí)候查找所需的探測(cè)次數(shù)是巨大的（α 越趨近于1，由公式可知探測(cè)的次數(shù)也越來(lái)越大），但當(dāng)使用率 α 小于 1/2 時(shí)探測(cè)的預(yù)計(jì)次數(shù)只在 1.5 到 2.5 之間。

ThreadLocalMap 實(shí)現(xiàn)點(diǎn)講解

其中，ThreadLocalMap 會(huì)在 get()、set() —— 添加或修改 操作對(duì)表中的失效元素進(jìn)行清除。

• get方法會(huì)清除，發(fā)現(xiàn)的第一個(gè) key為null（即，entry != null && null == entry.get()）的slot 到 遇到的第一個(gè) entry 為null 之間的所有entry。

• 而set方法，發(fā)現(xiàn) key 對(duì)應(yīng)的 slot 非空，且 nextIndex 的slot發(fā)現(xiàn)了失效entry（即，hash(key)'entry != null && hash(nextIndex)’entry != null && null == nextIndex_entry.get() ）時(shí)會(huì)清除 key slot所在的整個(gè)鍵簇上的失效的entry。這是因?yàn)?，key 本應(yīng)該待的索引位置已經(jīng)被其他entry占用了，這個(gè)被占用的entry可能不屬于該位置。而根據(jù)“線(xiàn)性探測(cè)法”，key 真是的 slot >= hash(key)，這個(gè)占用目標(biāo) key 位置的 entry 可能它本身的位置在更前面（但肯定是在這個(gè)簇族的范圍內(nèi)），而這個(gè)’侵占者’的真是slot上的entry可能也失效了，這樣的話(huà)應(yīng)該讓’侵占者’回到它的位置，而將其侵占的位置還出。
  而這么做的目的，是為了避免簇族的長(zhǎng)度持續(xù)的增長(zhǎng)。

ThreadLocalMap 會(huì)在“添加”操作中，判斷是否需要對(duì)表進(jìn)行“擴(kuò)張”（resize()操作），其中 α = 1/2；但，不會(huì)在remove操作對(duì)表進(jìn)行“縮減”

當(dāng)執(zhí)行“添加"操作后，hash map 元素（可能包括“失效”還未清除的元素）的長(zhǎng)度超過(guò)表長(zhǎng)度的 2/3 時(shí)，就會(huì)觸發(fā) rehash()操作。而rehash()操作，則會(huì)先對(duì)這個(gè) hash map 中的失效元素進(jìn)行清除，若清除后hash map中元素個(gè)數(shù)，依舊大等于表長(zhǎng)度的 1/2 （size >= threshold - threshold / 4，即，size >= tab.length/2），則進(jìn)行 hash map resize操作，將表長(zhǎng)度擴(kuò)大為原先的 2 倍。并將所有有效元素，重新插入擴(kuò)建后的 hash map中。

null == entry 以及 null != entry && null == entry.get() 的含義

• null == entry：表示給位置沒(méi)有對(duì)象

• null != entry && null == entry.get() ：表示該位置有對(duì)象，但對(duì)象已經(jīng)失效了，即，該對(duì)象除了被entry引用外，不再被其他可達(dá)性對(duì)象引用，并且還說(shuō)明，這個(gè)對(duì)象已經(jīng)被垃圾收集器回收了。因?yàn)檫@里的 entry.get() 實(shí)際上就是調(diào)用 WeakReference#get() 方法。

ThreadLocal 與 Thread 之間的關(guān)系

• 一個(gè) thread 可以有多個(gè) ThreadLocal 對(duì)象。一個(gè) ThreadLocal 對(duì)象維護(hù)了一個(gè)線(xiàn)程本地變量。
• 每個(gè) Thread 對(duì)象通過(guò) threadLocals 屬性來(lái)維護(hù)它的 ThreadLocals（ThreadLocal.ThreadLocalMap threadLocals）