雜湊表是計算機科學中的一種核心資料結構，它實現了許多語言中 Map（對映）型別的底層機制，Go 也不例外。

雜湊表的概念由 Hans Peter Luhn 於 1953 年首次在 IBM 的一篇內部備忘錄中 提出。他建議透過將專案放入“桶”（buckets）中，並在桶已滿時使用連結串列處理溢位，來加速搜尋。今天，我們稱之為“鏈式雜湊表”。

1954 年，Gene M. Amdahl、Elaine M. McGraw 和 Arthur L. Samuel 在編寫 IBM 701 的程式時，首次使用了“開放定址”方案。當一個桶已滿時，新專案被放置在下一個空桶中。這個想法在 1957 年由 W. Wesley Peterson 在其論文 “Addressing for Random-Access Storage” 中進行了形式化和發表。今天，我們稱之為“線性探測開放定址雜湊表”。

對於存在如此悠久歷史的資料結構，人們很容易認為它們已經“完成”，即我們已經瞭解了關於它們的一切，並且無法再進行改進。事實並非如此！計算機科學研究在基礎演算法方面不斷取得進步，這體現在演算法複雜度的提升以及對現代 CPU 硬體的利用上。例如，Go 1.19 將 sort 包從傳統的快速排序切換到了 Orson R. L. Peters 在 2015 年首次提出的新穎排序演算法——模式對抗快速排序。

與排序演算法類似，雜湊表資料結構也在不斷改進。2017 年，Google 的 Sam Benzaquen、Alkis Evlogimenos、Matt Kulukundis 和 Roman Perepelitsa 提出了一種新的 C++ 雜湊表設計，稱為“Swiss Tables”。2018 年，他們的實現被開源到 Abseil C++ 庫中。

Go 1.24 包含了對內建 Map 型別的一個全新實現，該實現基於 Swiss Table 設計。在這篇博文中，我們將探討 Swiss Tables 如何改進傳統的雜湊表，以及將 Swiss Table 設計引入 Go Map 時所面臨的一些獨特挑戰。

開放定址雜湊表

Swiss Tables 是一種開放定址雜湊表。讓我們快速回顧一下基本開放定址雜湊表的工作原理。

在開放定址雜湊表中，所有條目都儲存在一個單獨的底層陣列中。我們將陣列中的每個位置稱為一個槽（slot）。一個鍵所屬的槽主要由雜湊函式 `hash(key)` 決定。雜湊函式將每個鍵對映到一個整數，同一個鍵總是對映到同一個整數，而不同的鍵理想情況下會遵循均勻的隨機整數分佈。開放定址雜湊表的關鍵特性是，它透過將鍵儲存在底層陣列的其他位置來解決衝突。因此，如果槽已滿（發生衝突），則會使用探測序列（probe sequence）來檢查其他槽，直到找到一個空槽。讓我們透過一個示例雜湊表來看看這是如何工作的。

示例

下面是一個 16 個槽的雜湊表底層陣列，以及每個槽中儲存的鍵（如果有）。值未顯示，因為它們與本示例無關。

要插入新鍵，我們使用雜湊函式選擇一個槽。由於只有 16 個槽，我們需要將鍵限制在此範圍內，因此我們將使用 `hash(key) % 16` 作為目標槽。假設我們要插入鍵 `98`，且 `hash(98) % 16 = 7`。槽 7 是空的，所以我們直接將 98 插入此處。另一方面，假設我們要插入鍵 `25`，且 `hash(25) % 16 = 3`。槽 3 發生了衝突，因為它已經包含鍵 56。因此，我們不能在此插入。

我們使用探測序列來查詢另一個槽。有許多著名的探測序列。最初且最直接的探測序列是線性探測，它按順序嘗試連續的槽。

因此，在 `hash(25) % 16 = 3` 的示例中，由於槽 3 已在使用中，我們將接下來檢查槽 4，它也已在使用中。槽 5 也是如此。最後，我們將找到空槽 6，並將鍵 25 儲存在此處。

查詢遵循相同的過程。查詢鍵 25 將從槽 3 開始，檢查它是否包含鍵 25（不包含），然後繼續線性探測，直到在槽 6 中找到鍵 25。

此示例使用了具有 16 個槽的底層陣列。如果我們插入超過 16 個元素會怎樣？如果雜湊表空間不足，它會增長，通常會使底層陣列的大小加倍。所有現有條目都會重新插入到新的底層陣列中。

開放定址雜湊表實際上不會等到底層陣列完全填滿時才增長，因為隨著陣列越來越滿，每個探測序列的平均長度會增加。在上面使用鍵 25 的示例中，我們必須探測 4 個不同的槽才能找到一個空槽。如果陣列只有一個空槽，最壞情況下的探測長度將是 O(n)。也就是說，您可能需要掃描整個陣列。已使用槽的比例稱為負載因子（load factor），並且大多數雜湊表會定義一個最大負載因子（maximum load factor）（通常為 70-90%），達到該值時會增長，以避免非常滿的雜湊表產生極長的探測序列。

Swiss Table

Swiss Table 的設計也是一種開放定址雜湊表。讓我們看看它如何改進傳統的開放定址雜湊表。我們仍然有一個單獨的底層陣列用於儲存，但我們將陣列分成邏輯的組（groups），每組 8 個槽。（也可以使用更大的組大小。更多內容將在下面討論。）

此外，每個組都有一個 64 位控制字（control word）用於儲存元資料。控制字中的每個位元組對應組中的一個槽。每個位元組的值表示該槽是空、已刪除還是在使用中。如果正在使用，則該位元組包含該槽鍵的雜湊值的最低 7 位（稱為 `h2`）。

插入過程如下：

1. 計算 `hash(key)` 並將其分成兩部分：高 57 位（稱為 `h1`）和低 7 位（稱為 `h2`）。
2. 高位（`h1`）用於選擇要考慮的第一個組：在本例中為 `h1 % 2`，因為只有 2 個組。
3. 在一個組內，所有槽都有可能容納該鍵。我們必須首先確定是否有槽已包含此鍵，在這種情況下，這是一個更新而不是新的插入。
4. 如果沒有槽包含該鍵，那麼我們尋找一個空槽來放置該鍵。
5. 如果沒有空槽，則繼續探測序列，搜尋下一個組。

查詢遵循相同的基本過程。如果在步驟 4 中找到一個空槽，那麼我們就知道插入會使用該槽，並可以停止搜尋。

步驟 3 是 Swiss Table 的神奇之處。我們需要檢查組中的任何槽是否包含所需的鍵。樸素的做法是進行線性掃描並比較所有 8 個鍵。但是，控制字使我們能夠更有效地做到這一點。每個位元組包含該槽的雜湊值（`h2`）的最低 7 位。如果我們確定控制字中的哪些位元組包含我們正在尋找的 `h2`，我們將得到一組候選匹配項。

換句話說，我們想要在控制字內進行逐位元組的相等性比較。例如，如果我們正在查詢鍵 32，其中 `h2 = 89`，我們想要的操作如下所示。

這是SIMD硬體支援的操作，其中單個指令對較大值（向量）內的獨立值執行並行操作。在這種情況下，當沒有特殊 SIMD 硬體可用時，我們可以使用一組標準的算術和位運算來實現此操作。

結果是一組候選槽。`h2` 不匹配的槽不包含匹配的鍵，因此可以跳過。`h2` 匹配的槽是潛在匹配，但我們仍然必須檢查整個鍵，因為存在衝突的可能性（使用 7 位雜湊，衝突的機率為 1/128，仍然很低）。

這項操作非常強大，因為我們實際上同時並行地執行了探測序列的 8 個步驟。這透過減少我們需要執行的平均比較次數來加速查詢和插入。這種對探測行為的改進使得 Abseil 和 Go 的實現都能提高 Swiss Table Map 相對於之前 Map 的最大負載因子，從而降低了平均記憶體佔用。

Go 的挑戰

Go 的內建 Map 型別有一些不尋常的特性，給採用新的 Map 設計帶來了額外的挑戰。其中有兩個特別棘手。

增量式增長

當雜湊表達到其最大負載因子時，它需要增長底層陣列。通常這意味著下一次插入會將陣列大小加倍，並將所有條目複製到新陣列。想象一下插入一個包含 1GB 條目的 Map。大多數插入都非常快，但需要將 Map 從 1GB 增長到 2GB 的那次插入將需要複製 1GB 的條目，這將花費很長時間。

Go 經常用於對延遲敏感的伺服器，因此我們不希望內建型別的操作對尾部延遲產生任意大的影響。相反，Go Map 是增量式增長的，這樣每次插入的增長工作都有一個上限。這限制了單次 Map 插入的延遲影響。

不幸的是，Abseil (C++) Swiss Table 設計假定一次性增長，並且探測序列依賴於總組數，這使得拆分變得困難。

Go 的內建 Map 透過增加另一層間接性來解決此問題，將每個 Map 分成多個 Swiss Tables。每個 Map 由一個或多個獨立表組成，這些表覆蓋鍵空間的一部分，而不是由一個 Swiss Table 實現整個 Map。單個表最多儲存 1024 個條目。雜湊中可變數量的高位用於選擇鍵所屬的表。這是一種可擴充套件雜湊的形式，其中使用的位數會隨著區分表總數的需求而增加。

在插入過程中，如果單個表需要增長，它將一次性完成，但其他表不受影響。因此，單次插入的上限是增長一個 1024 個條目的表到兩個 1024 個條目的表的延遲，複製 1024 個條目。

迭代期間的修改

許多雜湊表設計，包括 Abseil 的 Swiss Tables，都禁止在迭代期間修改 Map。Go 語言規範明確允許在迭代期間進行修改，並具有以下語義：

• 如果在到達條目之前刪除該條目，則不會生成該條目。
• 如果在到達條目之前更新該條目，則會生成更新後的值。
• 如果添加了新條目，則可能生成也可能不生成。

雜湊表迭代的一種典型方法是簡單地遍歷底層陣列，並按照它們在記憶體中的佈局順序生成值。這種方法不符合上述語義，最明顯的原因是插入可能會導致 Map 增長，從而打亂記憶體佈局。

透過讓迭代器保持對其當前正在迭代的表的引用，我們可以避免增長期間的記憶體佈局混亂的影響。如果該表在迭代期間增長，我們將繼續使用舊版本的表，從而繼續按照舊的記憶體佈局順序傳遞鍵。

這與上述語義是否相容？增長後新增的新條目將完全被忽略，因為它們僅新增到增長後的表中，而不是舊錶中。沒關係，因為語義允許不生成新條目。但是，更新和刪除會帶來問題：使用舊錶可能會生成過時或已刪除的條目。

此邊緣情況透過僅使用舊錶來確定迭代順序來解決。在實際返回條目之前，我們會查詢增長後的表，以確定條目是否仍然存在，並獲取最新值。

這涵蓋了所有核心語義，儘管這裡還遺漏了更多小的邊緣情況。最終，Go Map 在迭代方面的靈活性使得迭代成為 Go Map 實現中最複雜的部分。

未來工作

在微基準測試中，Map 操作比 Go 1.23 快了高達 60%。確切的效能提升因 Map 操作和使用方式的廣泛差異而異，並且某些邊緣情況相對於 Go 1.23 存在效能回退。總體而言，在完整的應用程式基準測試中，我們發現 CPU 時間的幾何平均改進約為 1.5%。

我們希望在未來的 Go 版本中進一步改進 Map。例如，我們可能會提高不在 CPU 快取中的 Map 操作的區域性性。

我們還可以進一步改進控制字比較。如上所述，我們有一個使用標準算術和位運算的可移植實現。但是，某些架構具有直接執行此類比較的 SIMD 指令。Go 1.24 已經在 amd64 上使用了 8 位元組 SIMD 指令，但我們可以將其支援擴充套件到其他架構。更重要的是，雖然標準指令處理多達 8 位元組的字，但 SIMD 指令幾乎總是支援至少 16 位元組的字。這意味著我們可以將組大小增加到 16 個槽，並並行執行 16 次雜湊比較，而不是 8 次。這將進一步減少查詢所需的平均探測次數。

致謝

基於 Swiss Table 的 Go Map 實現已經醞釀了很長時間，並且涉及許多貢獻者。我想感謝 YunHao Zhang（@zhangyunhao116）、PJ Malloy（@thepudds）和@andy-wm-arthur 構建了 Go Swiss Table 實現的初步版本。Peter Mattis（@petermattis）將這些想法與上述 Go 挑戰的解決方案相結合，構建了符合 Go 規範的 Swiss Table 實現：github.com/cockroachdb/swiss。Go 1.24 的內建 Map 實現很大程度上基於 Peter 的工作。感謝社群所有做出貢獻的人！