一、get方法為什么不需要加鎖

1. 為什么 get 不需要加鎖

在 JDK8 的 ConcurrentHashMap 里：

• get 方法內(nèi)部基本是：

   1 public V get(Object key) {
   2     Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
   3     int h = spread(key.hashCode());
   4     if ((tab = table) != null && (n = tab.length) > 0 &&
   5         (e = tabAt(tab, (n - 1) & h)) != null) {
   6         if ((eh = e.hash) == h) {
   7             if ((ek = e.key) == key || (ek != null && key.equals(ek)))
   8                 return e.val;
   9         } else if (eh < 0)
  10             return (p = e.find(h, key)) != null ? p.val : null;
  11         while ((e = e.next) != null) {
  12             if (e.hash == h &&
  13                 ((ek = e.key) == key || (ek != null && key.equals(ek))))
  14                 return e.val;
  15         }
  16     }
  17     return null;
  18 }

• 這里沒(méi)有鎖，依賴的是：

  • 哈希桶數(shù)組 table 使用了 volatile 修飾，保證可見(jiàn)性。

  • 節(jié)點(diǎn)鏈表的 next 也是 final 或 volatile 方式保證可見(jiàn)性。

  • 讀取過(guò)程是只讀操作，不會(huì)修改節(jié)點(diǎn)本身，所以不需要鎖。

?? 2. 那么擴(kuò)容 (resize) 階段會(huì)不會(huì)丟數(shù)據(jù)？

我們分析下 JDK8 ConcurrentHashMap 的遷移邏輯。

2.1 擴(kuò)容觸發(fā)

當(dāng)元素過(guò)多，ConcurrentHashMap 會(huì)創(chuàng)建一個(gè)新的 nextTable，并遷移節(jié)點(diǎn)。遷移由多個(gè)線程共同完成，每個(gè)線程負(fù)責(zé)一部分桶。

2.2 ForwardingNode 協(xié)調(diào)

在遷移過(guò)程中，一個(gè)桶被遷移完后，會(huì)被替換成一個(gè)特殊的節(jié)點(diǎn) ForwardingNode，代碼大概是：

static final class ForwardingNode<K,V> extends Node<K,V> {
    final Node<K,V>[] nextTable;
    ForwardingNode(Node<K,V>[] tab) {
        super(MOVED, null, null, null);
        this.nextTable = tab;
    }
    Node<K,V> find(int h, Object k) {
        // 在新表 nextTable 里找
        return findInNewTable(h, k);
    }
}

• 當(dāng) get 過(guò)程中遇到 ForwardingNode，說(shuō)明該桶已經(jīng)遷移完畢，它會(huì)自動(dòng)去 新表里找對(duì)應(yīng)的 key。

2.3 桶未遷移完的情況

• 如果桶還沒(méi)遷移完（部分鏈表節(jié)點(diǎn)遷移了，部分還在舊表），那么該桶位置還指向舊鏈表。

• 此時(shí) get 會(huì)直接在舊鏈表里遍歷，仍然能讀到尚未遷移的節(jié)點(diǎn)。

• 所以不會(huì)出現(xiàn)“key 丟失”。

換句話說(shuō)：

• 遷移過(guò)程中，某個(gè) key 只會(huì)存在于舊表或新表之一，不會(huì)丟失。

• 遷移完成的桶會(huì)被替換成 ForwardingNode，get 會(huì)跳去新表找；

• 未完成遷移的桶還保留舊鏈表，get 就在舊表找。

?? 3. 會(huì)不會(huì)少讀？

不會(huì)。

• get 要么在舊表里讀（未遷移完成的桶），

• 要么被 ForwardingNode 引導(dǎo)到新表里讀（遷移完成的桶）。

• 不存在讀到“一半”的情況，因?yàn)殒湵磉w移是逐桶完成的，而不是逐節(jié)點(diǎn)即時(shí)替換。

?? 4. 具體代碼支撐

關(guān)鍵邏輯在 ConcurrentHashMap.transfer() 和 ForwardingNode.find()：

// 當(dāng)桶遷移完成后，會(huì)用 ForwardingNode 替換
setTabAt(tab, i, fwd);

// get 中遇到 hash < 0 （MOVED）時(shí)，會(huì)走 ForwardingNode.find()
else if (eh < 0)
    return (p = e.find(h, key)) != null ? p.val : null;

保證了 get 在遷移期間的正確性。

5. 總結(jié)

1. get 不加鎖，是因?yàn)橹蛔x + volatile 保證可見(jiàn)性。

2. 擴(kuò)容時(shí)，桶級(jí)別遷移，未遷移的桶仍在舊表查，遷移完的桶被 ForwardingNode 引導(dǎo)到新表查。

3. 不存在“只遷移了一半鏈表導(dǎo)致 key 丟失”的情況。

4. 這樣既保證了性能（無(wú)鎖讀），又保證了正確性（ForwardingNode + 桶級(jí)遷移）。

二、擴(kuò)容的時(shí)候是新建節(jié)點(diǎn)還是直接修改原節(jié)點(diǎn)

先給出結(jié)論：

• 擴(kuò)容的時(shí)候是新建節(jié)點(diǎn)，而不是像Hashmap那樣在原節(jié)點(diǎn)基礎(chǔ)上做修改

• 不會(huì)出現(xiàn) get 在擴(kuò)容過(guò)程中丟失節(jié)點(diǎn)的情況。原因是：在 JDK8 的實(shí)現(xiàn)里，遷移是按照「桶（bin）級(jí)別」完成的；遷移線程要么為該桶構(gòu)建并安裝好新表的節(jié)點(diǎn)（通常是新建節(jié)點(diǎn)的鏈表或復(fù)用一個(gè)完整的尾子鏈），然后原子地把舊桶位置替換成 ForwardingNode；在替換之前，舊鏈表保持可遍歷（沒(méi)有被破壞）。因此，get 要么在舊鏈上找到節(jié)點(diǎn)，要么遇到 ForwardingNode 被引導(dǎo)到新表查找，新表里也有完整節(jié)點(diǎn) —— 不會(huì)“少讀”節(jié)點(diǎn)。

下面分步驟、帶關(guān)鍵代碼片段（簡(jiǎn)化版）說(shuō)明實(shí)現(xiàn)細(xì)節(jié)與不丟失的理由。

1) 相關(guān)數(shù)據(jù)結(jié)構(gòu)簡(jiǎn)要（關(guān)鍵字段）

static class Node<K,V> {
    final int hash;
    final K key;
    volatile V val;
    volatile Node<K,V> next;
    Node(int hash, K key, V val, Node<K,V> next) {
        this.hash = hash; this.key = key; this.val = val; this.next = next;
    }
}
static final class ForwardingNode<K,V> extends Node<K,V> {
    final Node<K,V>[] nextTable;
    ForwardingNode(Node<K,V>[] nt) { super(MOVED, null, null, null); nextTable = nt; }
    Node<K,V> find(int h, Object k) { /* 查新表 */ }
}

關(guān)鍵點(diǎn)：

• hash、key 是 final（不可變）；

• val 和 next 是 volatile（寫(xiě)后其他線程可見(jiàn)）；

• ForwardingNode 用來(lái)標(biāo)識(shí)該舊桶已被遷移完，并包含 nextTable 指向新表。

2) get 的行為（簡(jiǎn)化）

V get(Object key) {
  Node<K,V>[] tab = table; int n = tab.length; 
  Node<K,V> e = tabAt(tab, index);
  if (e == null) return null;
  int eh = e.hash;
  if (eh == h && equals) return e.val;
  else if (eh < 0)          // 注意：負(fù) hash 表示特殊節(jié)點(diǎn)，如 ForwardingNode
      return e.find(h, key); // ForwardingNode.find 會(huì)在 newTable 中繼續(xù)查
  while ((e = e.next) != null) { ... } // 遍歷鏈表或 tree
  return null;
}

要點(diǎn)：get 不加鎖、直接讀 tab[index]，如果遇到 ForwardingNode（hash < 0，表示已經(jīng)遷移），它會(huì)查 nextTable（新表）。

3) transfer（遷移）核心邏輯（簡(jiǎn)化偽碼）

下面是關(guān)鍵流程的簡(jiǎn)化表示（真實(shí)代碼更復(fù)雜，有優(yōu)化）：

void transfer(Node<K,V>[] tab, Node<K,V>[] nextTab) {
  int n = tab.length;
  for (int i = 0; i < n; ++i) {
    Node<K,V> f = tabAt(tab,i);
    if (f == null) {
      setTabAt(tab, i, new ForwardingNode<>(nextTab)); // 桶為空，直接放轉(zhuǎn)發(fā)節(jié)點(diǎn)
      continue;
    }
    if (f instanceof ForwardingNode) continue; // 已被遷移
    // 關(guān)鍵：對(duì) f 同步（或其他協(xié)作）以避免并發(fā)重復(fù)遷移
    synchronized (f) {
       if (tabAt(tab,i) != f) continue; // recheck
       // 將 old 鏈表拆分為 lo 和 hi 兩條鏈（按 hash & n）
       Node<K,V> loHead = null, hiHead = null;
       Node<K,V> e = f;
       for (; e != null; e = e.next) {
           if ((e.hash & n) == 0) {
               // 創(chuàng)建新節(jié)點(diǎn)（注意：通常會(huì) new Node(...)，不是直接改舊節(jié)點(diǎn)）
               loHead = new Node<>(e.hash, e.key, e.val, loHead);
           } else {
               hiHead = new Node<>(e.hash, e.key, e.val, hiHead);
           }
       }
       // 寫(xiě)入 nextTab 的對(duì)應(yīng)槽位（新表）
       setTabAt(nextTab, i, reverse(loHead));
       setTabAt(nextTab, i + n, reverse(hiHead));
       // 最后，用 ForwardingNode 原子替換舊表該槽，表示遷移完成
       setTabAt(tab, i, new ForwardingNode<>(nextTab));
    }
  }
}

重要細(xì)節(jié)：

• 對(duì)多數(shù)節(jié)點(diǎn)，遷移過(guò)程是 新建節(jié)點(diǎn)（new Node(...)）并鏈成新表的鏈表；也就是說(shuō)舊鏈表的 next 指針并沒(méi)有被破壞或改寫(xiě)——舊鏈仍然完整可遍歷，直到遷移線程把 tab[i] 替換成 ForwardingNode 為止。

• 有個(gè)優(yōu)化（lastRun）會(huì)嘗試在滿足條件時(shí)直接重用舊鏈表的一段尾部以減少分配，但那段被重用的是一個(gè)連續(xù)的子鏈，遷移代碼確保不會(huì)把舊鏈拆成不連續(xù)段從而破壞舊鏈的可遍歷性。

因此：在安裝 ForwardingNode 之前，舊桶鏈保持可遍歷（未被破壞）。一旦 ForwardingNode 安裝完成，get 若遇到它會(huì)自動(dòng)到新表查找（新表已被完整填充該桶對(duì)應(yīng)的節(jié)點(diǎn)）。

4) 并發(fā)場(chǎng)景逐步說(shuō)明（關(guān)鍵保證）

考慮你舉的“總共 7 個(gè)節(jié)點(diǎn)，遷移了 3 個(gè)到 new table，新表已有 4 個(gè)，舊表剩 3 個(gè)” 的假設(shè) —— 這在實(shí)現(xiàn)上不會(huì)發(fā)生，因?yàn)椋?/p>

• transfer 不會(huì)先把前 3 個(gè)節(jié)點(diǎn)“挪走”并同時(shí)把 tab[i] 指向新的小鏈；實(shí)現(xiàn)是先構(gòu)建好 newTable 對(duì)應(yīng)槽位（通過(guò) new Node(...) 或復(fù)用尾鏈），再原子地把 tab[i] 換成 ForwardingNode。

• 在這整個(gè)過(guò)程中，舊鏈要么仍完好（遷移還沒(méi)替換 ForwardingNode），get 在舊鏈能找到所有節(jié)點(diǎn)；要么遷移完成并安裝了 ForwardingNode，此時(shí) get 會(huì)被引導(dǎo)去新表，而新表中該桶的鏈?zhǔn)峭暾模ê繎?yīng)有節(jié)點(diǎn)）。

• 不會(huì)出現(xiàn)“舊表只剩下 3 個(gè)可遍歷節(jié)點(diǎn)，而新表只有 4 個(gè)、合起來(lái)是 7 個(gè)但分布在兩處且舊串已被破壞從而部分節(jié)點(diǎn)不可達(dá)”的情況。

換言之，遷移對(duì)外的可見(jiàn)性是原子切換：切換前舊數(shù)據(jù)完整可見(jiàn)；切換后新表完整可見(jiàn)——沒(méi)有中間狀態(tài)丟失數(shù)據(jù)。

5) 為什么 get 可以無(wú)鎖且總是安全地讀到最新數(shù)據(jù)？

要點(diǎn)匯總：

1. 遷移構(gòu)建新鏈時(shí)不破壞舊鏈（通常通過(guò) new Node(...) 構(gòu)建新鏈或復(fù)用完整尾鏈）：因此在 ForwardingNode 安裝前，舊鏈完整可遍歷。

2. ForwardingNode 的安裝是一次寫(xiě)入（volatile 寫(xiě) / setTabAt），寫(xiě)入后其它線程看到的是 ForwardingNode，從而被引導(dǎo)到新表；這個(gè)寫(xiě)操作提供了內(nèi)存可見(jiàn)性屏障，保證新表已構(gòu)建的節(jié)點(diǎn)對(duì)讀線程可見(jiàn)。

3. Node 的字段設(shè)計(jì)（final hash/key, volatile val/next） 保證了讀線程看到的一致性（不會(huì)看到半初始化的 key/hash），并且 next 的寫(xiě)入對(duì)其他線程可見(jiàn)。

4. 讀線程的選擇邏輯：若讀到桶頭是普通 Node（hash >=0），直接遍歷舊鏈；若讀到 ForwardingNode（hash <0），轉(zhuǎn)到 nextTable 查找。兩條路徑把舊表和新表在時(shí)間上分隔開(kāi)，互不丟失節(jié)點(diǎn)。

6) 額外說(shuō)明（樹(shù)化 / treebin 情形）

• 對(duì)于高度沖突的桶，JDK8 會(huì)把鏈表轉(zhuǎn)換為 TreeBin（紅黑樹(shù)），transfer 會(huì)把樹(shù)分裂到兩個(gè)新槽位。設(shè)計(jì)同樣遵循“先準(zhǔn)備好新位，再原子替換為 ForwardingNode”的思路，因此同樣不會(huì)丟節(jié)點(diǎn)。

7) 代碼證據(jù)（你可以看真實(shí)實(shí)現(xiàn)）

如果你看 OpenJDK 的 ConcurrentHashMap.transfer(...)（JDK8）實(shí)現(xiàn)，會(huì)看到上述行為的真實(shí)代碼片段：

• 遍歷舊鏈，構(gòu)造 lo 和 hi（通常新 Node），

• 寫(xiě)入 nextTab 對(duì)應(yīng)槽，

• 最后 setTabAt(tab, i, new ForwardingNode<>(nextTab))。

（我這里給出的偽碼已準(zhǔn)確反映實(shí)現(xiàn)思路；如需我可以貼出簡(jiǎn)化的真實(shí)代碼片段并逐行注釋。）

結(jié)論（一句話）

• 擴(kuò)容遷移不會(huì)破壞舊鏈從而導(dǎo)致 get 丟數(shù)據(jù)。遷移要么沒(méi)開(kāi)始（get 在舊表能找到所有節(jié)點(diǎn)），要么遷移完成并原子替換（get 會(huì)被導(dǎo)到新表并在新表找到所有節(jié)點(diǎn)）。因此 get 在擴(kuò)容期間是安全的，不需要加鎖。