第一贰健、前言
ThreadLocal使用的是自定義的ThreadLocalMap乳附，接下來我們來探究一下ThreadLocalMap的hash沖突解決方式。
ThreadLocal通過線性探測(cè)法/開放地址法來解決hash沖突逻悠，
HashMap則通過鏈地址法來解決hash沖突
第二志笼、ThreadLocal的set()方法
public void set(T value) {
Thread t = Thread.currentThread();
ThreadLocal.ThreadLocalMap map = getMap(t);
if (map != null)
map.set(this, value);
else
createMap(t, value);
}
ThreadLocal.ThreadLocalMap getMap(Thread t) {
return t.threadLocals;
}
void createMap(Thread t, T firstValue) {
t.threadLocals = new ThreadLocal.ThreadLocalMap(this, firstValue);
}
1.代碼很簡(jiǎn)單,獲取當(dāng)前線程,并獲取當(dāng)前線程的ThreadLocalMap實(shí)例（從getMap(Thread t)中很容易看出來）。
2.如果獲取到的map實(shí)例不為空,調(diào)用map.set()方法,否則調(diào)用構(gòu)造函數(shù)ThreadLocal.ThreadLocalMap(this, firstValue)實(shí)例化map痊土∫拊可以看出來線程中的ThreadLocalMap使用的是延遲初始化,在第一次調(diào)用get()或者set()方法的時(shí)候才會(huì)進(jìn)行初始化。
第三赁酝、構(gòu)造函數(shù)ThreadLocalMap(ThreadLocal<?> firstKey, Object firstValue)
ThreadLocalMap(ThreadLocal<?> firstKey, Object firstValue) {
//初始化table
table = new ThreadLocal.ThreadLocalMap.Entry[INITIAL_CAPACITY];
//計(jì)算索引
int i = firstKey.threadLocalHashCode & (INITIAL_CAPACITY - 1);
//設(shè)置值
table[i] = new ThreadLocal.ThreadLocalMap.Entry(firstKey, firstValue);
size = 1;
//設(shè)置閾值
setThreshold(INITIAL_CAPACITY);
}
主要說一下計(jì)算索引犯祠，firstKey.threadLocalHashCode & (INITIAL_CAPACITY - 1)。
關(guān)于& (INITIAL_CAPACITY - 1),這是取模的一種方式酌呆，對(duì)于2的冪作為模數(shù)取模衡载，用此代替%(2^n)，這也就是為啥容量必須為2的冥隙袁，在這個(gè)地方也得到了解答痰娱。
關(guān)于firstKey.threadLocalHashCode：
private final int threadLocalHashCode = nextHashCode();
private static int nextHashCode() {
return nextHashCode.getAndAdd(HASH_INCREMENT);
}
private static AtomicInteger nextHashCode = new AtomicInteger();
private static final int HASH_INCREMENT = 0x61c88647;
這里定義了一個(gè)AtomicInteger類型弃榨，每次獲取當(dāng)前值并加上HASH_INCREMENT，HASH_INCREMENT = 0x61c88647,這個(gè)值和斐波那契散列有關(guān)（這是一種乘數(shù)散列法猜揪，只不過這個(gè)乘數(shù)比較特殊惭墓，是32位整型上限2^32-1乘以黃金分割比例0.618…的值2654435769，用有符號(hào)整型表示就是-1640531527而姐，去掉符號(hào)后16進(jìn)制表示為0x61c88647），其主要目的就是為了讓哈希碼能均勻的分布在2的n次方的數(shù)組里, 也就是Entry[] table中划咐，這樣做可以盡量避免hash沖突拴念。
第四、ThreadLocalMap中的set()
ThreadLocalMap使用閉散列:(開放地址法或者也叫線性探測(cè)法)解決哈希沖突褐缠。
線性探測(cè)法的地址增量di = 1, 2, … 其中政鼠，i為探測(cè)次數(shù)。該方法一次探測(cè)下一個(gè)地址队魏，直到有空的地址后插入公般，若整個(gè)空間都找不到空余的地址，則產(chǎn)生溢出胡桨。
假設(shè)當(dāng)前table長(zhǎng)度為16官帘，也就是說如果計(jì)算出來key的hash值為14，如果table[14]上已經(jīng)有值昧谊，并且其key與當(dāng)前key不一致刽虹，那么就發(fā)生了hash沖突，這個(gè)時(shí)候?qū)?4加1得到15呢诬，取table[15]進(jìn)行判斷涌哲，這個(gè)時(shí)候如果還是沖突會(huì)回到0，取table[0],以此類推尚镰，直到可以插入阀圾。
按照上面的描述，可以把table看成一個(gè)環(huán)形數(shù)組狗唉。
先看一下線性探測(cè)相關(guān)的代碼初烘，從中也可以看出來table實(shí)際是一個(gè)環(huán)：
private static int nextIndex(int i, int len) {
return ((i + 1 < len) ? i + 1 : 0);
}
private static int prevIndex(int i, int len) {
return ((i - 1 >= 0) ? i - 1 : len - 1);
}
private void set(ThreadLocal<?> key, Object value) {
ThreadLocal.ThreadLocalMap.Entry[] tab = table;
int len = tab.length;
//計(jì)算索引，上面已經(jīng)有說過敞曹。
int i = key.threadLocalHashCode & (len-1);
/**根據(jù)獲取到的索引進(jìn)行循環(huán)账月，如果當(dāng)前索引上的table[i]不為空，在沒有return的情況下澳迫，
* 就使用nextIndex()獲取下一個(gè)（上面提到到線性探測(cè)法）局齿。*/
for (ThreadLocal.ThreadLocalMap.Entry e = tab[i]; e != null;
e = tab[i = nextIndex(i, len)]) {
ThreadLocal<?> k = e.get();
//table[i]上key不為空，并且和當(dāng)前key相同橄登，更新value
if (k == key) {
e.value = value;
return;
}
/**table[i]上的key為空抓歼，說明被回收了
* 說明改table[i]可以重新使用讥此，用新的key-value將其替換,并刪除其他無效的entry*/
if (k == null) {
replaceStaleEntry(key, value, i);
return;
}
}
//不存在也沒有舊元素就創(chuàng)建一個(gè)
tab[i] = new Entry(key, value);
int sz = ++size;
if (!cleanSomeSlots(i, sz) && sz >= threshold)
rehash();//擴(kuò)容
}
第五、閉散列
當(dāng)我們要往哈希表中插入一個(gè)數(shù)據(jù)時(shí)谣妻，通過哈希函數(shù)計(jì)算該值的哈希地址萄喳，當(dāng)我們找到哈希地址時(shí)卻發(fā)現(xiàn)該位置已經(jīng)被別的數(shù)據(jù)插入了，那么此時(shí)我們就找緊跟著這一位置的下一個(gè)位置蹋半，看是否能夠插入他巨，如果能則插入，不能則繼續(xù)探測(cè)緊跟著當(dāng)前位置的下一個(gè)位置减江。
假設(shè)要將key=y的元素存入哈希表染突，通過哈希函數(shù)求出哈希地址為7，比較哈希地址7的元素的key是否等于y辈灼，不相等份企，繼續(xù)比對(duì)哈希地址為8的元素…直到找到哈希地址為2的位置，可以存儲(chǔ)巡莹。
轉(zhuǎn)自 https://blog.csdn.net/fengyuyeguirenenen/article/details/124897002
