ThreadLocalMapLocalMap 簡(jiǎn)介
ThreadLocalMapLocalMap 是一個(gè)散列表結(jié)構(gòu)的容器，用來(lái)存儲(chǔ)線程的本地變量。使用開(kāi)放地址法解決散列沖突。它是ThreadLocal的一個(gè)靜態(tài)內(nèi)部類。
數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)
ThreadLocal對(duì)象作為hash表的key,通過(guò)散列函數(shù)計(jì)算hash表中的下標(biāo)，哈希表中每個(gè)下標(biāo)下保存Entry類實(shí)例。里面存在兩個(gè)屬性一個(gè)是ThreadLocal作為散列表的key，另一個(gè)是key對(duì)應(yīng)值(value)
image
源碼中定義
static class ThreadLocalMap {
/**
* 哈希表中節(jié)點(diǎn)對(duì)象
* key ：類型ThreadLocal，被定義為WeakReference
* value：類型Object，引用存儲(chǔ)值
* */
static class Entry extends WeakReference<ThreadLocal<?>> {
/** ThreadLocal */
Object value;
Entry(ThreadLocal<?> k, Object v) {
super(k);
value = v;
}
}
/**
* 默認(rèn)哈希表容量，必須是2的冪次方
*/
private static final int INITIAL_CAPACITY = 16;
/**
* 哈希表(Entry)數(shù)組
*/
private Entry[] table;
/**
* 容器中存儲(chǔ)Entry的個(gè)數(shù)
*/
private int size = 0;
/**
* 下一次需要擴(kuò)容的閾值
*/
private int threshold; // Default to 0
...省略代碼
Entry在數(shù)組中存在類型
image
USED:表示數(shù)組中下標(biāo)位置被一個(gè)Entry占用
NULL:表示數(shù)組中下標(biāo)位置為NULL
STALE:表示數(shù)組中下標(biāo)位置被一個(gè)臟Entry占用，key為NULL的Entry。
什么時(shí)候存在臟Entry
image
由于Entry被WeakReference所引用，即使存在一條線程對(duì)象GCROOT(虛線路徑),因而當(dāng)gc回收時(shí)，如果TheadLocal對(duì)象沒(méi)有被強(qiáng)引用則會(huì)被回收。
案例
定義一個(gè)Entry類
package threadLocal;
import java.lang.ref.WeakReference;
public class Entry extends WeakReference<ThreadLocal<Object>> {
public Object value;
Entry(ThreadLocal<Object> k, Object v) {
super(k);
value = v;
}
}
編寫(xiě)測(cè)試類
/**
* Salad salad = new Salad(threadLocal,new Object());
* 存在一條到GC root通路 thread <-- Salad <-- WeakReference <-- ThreadLocal
* 由于是WeakReference，因而如果ThreadLocal并沒(méi)有存在其他強(qiáng)引用時(shí)會(huì)被gc回收
* 即threadLocal=null 代碼開(kāi)啟將被回收
*/
public class WeakReferenceTest {
public static void main(String[] args) {
ThreadLocal<Object> threadLocal = new ThreadLocal<Object>();
Entry salad = new Entry(threadLocal,new Object());
//通過(guò)WeakReference的get()方法獲取Apple
System.out.println("ThreadLocal:" + salad.get());
//開(kāi)啟代碼threadLocal將被回收
threadLocal=null;
System.gc();
try {
//休眠一下，在運(yùn)行的時(shí)候加上虛擬機(jī)參數(shù)-XX:+PrintGCDetails，輸出gc信息，確定gc發(fā)生了。
Thread.sleep(5000);
} catch (InterruptedException e) {
e.printStackTrace();
}
//如果為空，代表被回收了
if (salad.get() == null) {
System.out.println("clear Apple。");
}
}
}
核心方法
設(shè)置值
當(dāng)我們往散列表中插入數(shù)據(jù)時(shí)，如果某個(gè)數(shù)據(jù)經(jīng)過(guò)散列函數(shù)散列之后，存儲(chǔ)位置已經(jīng)被占用了，我們就從當(dāng)前位置開(kāi)始，依次往后查找，看是否有空閑位置，直到找到為止。
image
我們來(lái)看下ThreadLocalMap實(shí)現(xiàn)
/**
* 設(shè)置ThreadLocal（key），對(duì)應(yīng)值
*/
private void set(ThreadLocal<?> key, Object value) {
/** 獲取哈希數(shù)組 **/
Entry[] tab = table;
/** 獲取哈希數(shù)組長(zhǎng)度 **/
int len = tab.length;
/** 通過(guò)hash運(yùn)算獲取ThreadLocal在哈希表的 i位置**/
int i = key.threadLocalHashCode & (len-1);
/** 獲取下標(biāo)位置的Entry，判斷Entry是否存在，且Entry.key和傳入key相同
* 如果Entry存在且Entry.key和傳入key相同，則覆蓋值
* 如果Entry存在且Entry,key和傳入key不相同，表明發(fā)生hash碰撞，按照開(kāi)放定址法，從下標(biāo)位置向后查找未被暫用的哈希表節(jié)點(diǎn)插入
* 如果Entry存在且Entry,key==null,表明此Entry是一個(gè)臟Entry，用當(dāng)前傳入值構(gòu)造一個(gè)新Entry，替換這個(gè)下標(biāo)位置臟Entry
* **/
for (Entry e = tab[i];
e != null;
e = tab[i = nextIndex(i, len)]) {
ThreadLocal<?> k = e.get();
/** 如果Entry存在且Entry.key和傳入key相同，則覆蓋值 **/
if (k == key) {
e.value = value;
return;
}
/** 如果Entry存在且Entry,key==null,表明此Entry是一個(gè)臟Entry，用當(dāng)前傳入值構(gòu)造一個(gè)新Entry，替換這個(gè)下標(biāo)位置臟Entry **/
if (k == null) {
replaceStaleEntry(key, value, i);
return;
}
/** 如果Entry存在且Entry,key和傳入key不相同，表明發(fā)生hash碰撞，按照開(kāi)放定址法，從下標(biāo)位置向后查找未被暫用的哈希表節(jié)點(diǎn)插入 **/
}
/** 新建entry并插入哈希表 i 位置 **/
tab[i] = new Entry(key, value);
/** 哈希表節(jié)點(diǎn)數(shù)量+1 **/
int sz = ++size;
/** 插入后從哈希表中查找并擦除臟Entry,如果未找到臟，且哈希表容量大于閾值就需要擴(kuò)容 **/
if (!cleanSomeSlots(i, sz) && sz >= threshold)
rehash();
}
這里cleanSomeSlots，replaceStaleEntry對(duì)臟Entry處理留到下一篇。
查找元素
在散列表中查找元素的過(guò)程有點(diǎn)兒類似插入過(guò)程。我們通過(guò)散列函數(shù)求出要查找元素的鍵值對(duì)應(yīng)的散列值，然后比較數(shù)組中下標(biāo)為散列值的元素和要查找的元素。如果相等，則說(shuō)明就是我們要找的元素；否則就順序往后依次查找。如果遍歷到數(shù)組中的空閑位置，還沒(méi)有找到，就說(shuō)明要查找的元素并沒(méi)有在散列表中
為什么遍歷到空位置就表示不存在？
因?yàn)椴迦朐貢r(shí)發(fā)生散列沖突，會(huì)找到數(shù)組一個(gè)空位置就插入了。如果查找時(shí)遍歷到一個(gè)空位置還沒(méi)有找到則說(shuō)明要查找的元素并沒(méi)有在散列表中
image
我們來(lái)看下ThreadLocalMap實(shí)現(xiàn)
/**
* 給定指定key，查找Entry
*/
private Entry getEntry(ThreadLocal<?> key) {
/** 通過(guò)hash運(yùn)算獲取ThreadLocal在哈希表的 i位置**/
int i = key.threadLocalHashCode & (table.length - 1);
/** 獲取哈希表 i位置Entry **/
Entry e = table[i];
/** 如果Entry存在且Entry.key和傳入的key匹配，則直接返回Entry **/
if (e != null && e.get() == key)
return e;
else
/**
* 1 傳入key對(duì)應(yīng)Entry不存在直接返回
* 2 傳入key對(duì)應(yīng)Entry存在，傳入key和Entry.key不匹配(hash碰撞)，使用開(kāi)放定址法在哈希表中查找
* **/
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();
/** 對(duì)比key是否相同，如果相同則返回 **/
if (k == key)
return e;
/** 如果發(fā)現(xiàn)臟節(jié)點(diǎn)，則調(diào)用expungeStaleEntry清理 **/
if (k == null)
expungeStaleEntry(i);
else
/** 獲取當(dāng)前位置下一個(gè)哈希表節(jié)點(diǎn) **/
i = nextIndex(i, len);
e = tab[i];
}
/** 如果ashCode映射到哈希表數(shù)組下標(biāo)位置為null，說(shuō)明傳入key對(duì)應(yīng)的節(jié)點(diǎn)在哈希表中不存在 **/
return null;
}
刪除元素
在散列表中刪除元素有些特殊，首先我們通過(guò)散列函數(shù)求出要查找元素的鍵值對(duì)應(yīng)的散列值，然后比較數(shù)組中下標(biāo)為散列值的元素和要查找的元素。如果相等，則說(shuō)明就是我們要找的元素。如果相等。此時(shí)我們?nèi)绻麅H僅只是刪除元素對(duì)于刪除元素來(lái)說(shuō)是沒(méi)有問(wèn)題。但會(huì)影響查詢?cè)?/strong>。
在查找的時(shí)候，一旦我們通過(guò)線性探測(cè)方法，找到一個(gè)空閑位置，我們就可以認(rèn)定散列表中不存在這個(gè)數(shù)據(jù)。但是，如果這個(gè)空閑位置是我們后來(lái)刪除的，就會(huì)導(dǎo)致原來(lái)的查找算法失效。本來(lái)存在的數(shù)據(jù)，會(huì)被認(rèn)定為不存在。
解決思路
從數(shù)組中刪除該元素，同時(shí)繼續(xù)向后探測(cè)，將散列沖突的元素填入刪除元素的位置。
我們來(lái)看下ThreadLocalMap實(shí)現(xiàn)
/**
* 刪除ThreadLocal（key），對(duì)應(yīng)的副本變量值
*/
private void remove(ThreadLocal<?> key) {
Entry[] tab = table;
int len = tab.length;
/** 通過(guò)hash運(yùn)算獲取ThreadLocal在哈希表的 i位置**/
int i = key.threadLocalHashCode & (len-1);
/** 獲取下標(biāo)位置的Entry，判斷Entry是否存在，且Entry.key和傳入key相同
* 如果Entry存在，且Entry.key和傳入key相同，則將查找到Entry設(shè)置為臟節(jié)點(diǎn)，然后調(diào)用expungeStaleEntry清理
* 如果Entry存在，且Entry.key和傳入key不相同，表明發(fā)生hash碰撞，按照開(kāi)放定址法，從下標(biāo)位置向后查找key和傳入相同哈希表節(jié)
* 如果找到則將查找到Entry設(shè)置為臟節(jié)點(diǎn)，然后調(diào)用expungeStaleEntry清理
*/
for (Entry e = tab[i];
e != null;
e = tab[i = nextIndex(i, len)]) {
if (e.get() == key) {
e.clear();
expungeStaleEntry(i);
return;
}
}
}
/**
* 1 擦除臟Entry，并從臟Entry位置開(kāi)始向后查找臟Entry，發(fā)現(xiàn)則擦除直到一個(gè)空節(jié)點(diǎn)結(jié)束
* 2 從當(dāng)前staleSlot位置向后環(huán)形（nextIndex）繼續(xù)搜索，發(fā)現(xiàn)沖突的節(jié)點(diǎn)填充到前面的擦除節(jié)點(diǎn)
*/
private int expungeStaleEntry(int staleSlot) {
Entry[] tab = table;
int len = tab.length;
/** 直接擦除指定索引位置Entry； **/
tab[staleSlot].value = null;
tab[staleSlot] = null;
size--;
Entry e;
int i;
for (i = nextIndex(staleSlot, len);
(e = tab[i]) != null;
i = nextIndex(i, len)) {
ThreadLocal<?> k = e.get();
/** 直接擦除指定索引位置Entry； **/
if (k == null) {
e.value = null;
tab[i] = null;
size--;
} else {
/** 通過(guò)hash運(yùn)算獲取ThreadLocal在哈希表的 i位置**/
int h = k.threadLocalHashCode & (len - 1);
/** 比較有無(wú)碰撞，存在則使用 開(kāi)放定址法，從下標(biāo)位置向后查找未被暫用的哈希表節(jié)點(diǎn)插入**/
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;
}
擴(kuò)容
構(gòu)建一個(gè)新的hash表，容量*2，表示原始hash表數(shù)據(jù)拷貝過(guò)去。
/**
* 哈希表擴(kuò)容
*/
private void rehash() {
/** 擦除哈希表中所有臟Entry **/
expungeStaleEntries();
/** 當(dāng)容量大于閾值的3/4則擴(kuò)容 **/
if (size >= threshold - threshold / 4)
resize();
}
/**
* 每次擴(kuò)容偶會(huì)創(chuàng)建當(dāng)前容量*2的哈希表，并將原來(lái)哈希表中的數(shù)據(jù)拷貝過(guò)去
*/
private void resize() {
Entry[] oldTab = table;
int oldLen = oldTab.length;
int newLen = oldLen * 2;
Entry[] newTab = new Entry[newLen];
int count = 0;
/** 遍歷原始的哈希表，臟Entry擦除，非臟Entry重新計(jì)算ThreadLocal在新哈希表的 i位置
* 并插入 **/
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++;
}
}
}
/** 重新設(shè)置新的閾值 **/
setThreshold(newLen);
/** 重新設(shè)置新的大小 **/
size = count;
table = newTab;
}
/**
* 擦除哈希表中所有臟Entry
* 1 擦除哈希表中所有臟Entry
*/
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);
}
}
