hello啊，各位觀眾姥爺們！！！本baby今天來報道了！哈哈哈哈哈嗝🐶

面試官：ThreadLocalMap 怎么解決 Hash 沖突的？

ThreadLocalMap 是 ThreadLocal 的核心實現，它采用 開放地址法（Open Addressing）中的線性探測（Linear Probing） 來解決哈希沖突。與 HashMap 的拉鏈法（鏈式地址法）不同，ThreadLocalMap 直接在數組上順序查找下一個可用槽位。以下是其詳細實現機制：

---

1. 哈希沖突解決原理

(1) 數據結構

• 底層數組：Entry[] table，每個 Entry 以 ThreadLocal<?> 為鍵（弱引用），存儲線程本地變量的值。
• 初始容量：默認 16，擴容閾值為數組長度的 2/3。

(2) 哈希函數

• 哈希計算：
  ThreadLocal 實例的 threadLocalHashCode 通過原子遞增生成，確保哈希分布均勻。

  private final int threadLocalHashCode = nextHashCode();
  private static AtomicInteger nextHashCode = new AtomicInteger();
  private static final int HASH_INCREMENT = 0x61c88647; // 黃金分割數
  private static int nextHashCode() {return nextHashCode.getAndAdd(HASH_INCREMENT);
  }
  

• 索引計算：
  通過 hashCode & (table.length - 1) 確定初始槽位（類似 HashMap 的取模優化）。

(3) 線性探測流程

當插入或查找鍵值對時，若目標槽位已被占用（鍵不同或哈希沖突），則按順序向后查找空槽位（到數組末尾后折返到頭部）。

操作步驟：

1. 計算初始索引：i = key.threadLocalHashCode & (len - 1)。
2. 遍歷數組：
   • 若 Entry[i] 的鍵匹配 → 直接操作該槽位。
   • 若 Entry[i] 的鍵為 null（弱引用被回收）→ 觸發清理（expungeStaleEntry）。
   • 若 Entry[i] 被占用但鍵不匹配 → i = nextIndex(i, len)（即 i+1，超過長度則回繞到 0）。
3. 找到空槽或完成清理：插入新鍵值對或更新現有值。

---

2. 關鍵代碼解析（以 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<?> k = e.get();if (k == key) { // 鍵匹配，直接更新值e.value = value;return;}if (k == null) { // 遇到過期 Entry（鍵被回收），替換過期槽位replaceStaleEntry(key, value, i);return;}}// 找到空槽位，插入新 Entrytab[i] = new Entry(key, value);int sz = ++size;// 清理部分過期 Entry 后若仍超過閾值，觸發擴容if (!cleanSomeSlots(i, sz) && sz >= threshold)rehash();
}

---

3. 線性探測的優缺點

優點	缺點
節省內存：無鏈表指針開銷	沖突較多時查找效率下降（最差 O(n)）
適合小規模數據（ThreadLocalMap 通常條目少）	擴容成本高（需全量 rehash）
內存局部性好（數組連續遍歷）	需要處理過期 Entry 清理邏輯

---

4. 清理過期 Entry（解決內存泄漏）

在線性探測過程中，若遇到鍵為 null 的過期 Entry，會觸發清理：

1. expungeStaleEntry(int staleSlot)：
   • 清理當前過期槽位，并向后探測，重新哈希未過期的 Entry，直到遇到空槽。
   • 解決因哈希沖突導致過期 Entry 殘留的問題。
2. cleanSomeSlots()：
   • 啟發式清理，掃描 log(n) 次，平衡清理開銷與內存釋放。

---

5. 示例場景

假設 ThreadLocalMap 的數組長度為 8，插入兩個鍵 A 和 B，其哈希計算后的初始索引均為 3：

1. 插入鍵 A：直接放入索引 3。
2. 插入鍵 B：
   • 索引 3 已被 A 占用，向后探測到索引 4，放入 B。
3. 查找鍵 B：
   • 計算初始索引 3，發現是 A → 繼續探測索引 4，找到 B。

---

6. 對比 HashMap 的拉鏈法

特性	ThreadLocalMap（開放地址法）	HashMap（拉鏈法）
沖突解決	線性探測，順序查找空槽	鏈表或紅黑樹鏈接沖突節點
內存占用	更緊湊（無鏈表指針）	需要額外指針存儲鏈表/樹結構
適用場景	預期條目少，內存敏感	高并發、大數據量
擴容機制	全量 rehash，成本高	鏈表拆分，增量遷移

---

總結

• 核心機制：ThreadLocalMap 通過線性探測解決哈希沖突，犧牲一定查找效率換取內存緊湊性。
• 內存安全：結合弱引用鍵和主動清理過期 Entry，減少內存泄漏風險。
• 適用場景：適合線程本地變量數量少、生命周期與線程綁定的場景。