Go 部落格
使用 Swiss Tables 讓 Go maps 更快
雜湊表是計算機科學中的一個核心資料結構，它為包括 Go 在內的許多語言中的 map 型別提供了實現。
雜湊表的概念於 1953 年由 Hans Peter Luhn 在 IBM 的一份內部備忘錄中首次提出，該備忘錄建議透過將專案放入“桶”中並在桶已包含專案時使用連結串列處理溢位來加快搜索。如今我們稱之為使用鏈式法的雜湊表。
1954 年，Gene M. Amdahl、Elaine M. McGraw 和 Arthur L. Samuel 在程式設計 IBM 701 時首次使用了“開放定址”方案。當桶已包含專案時，新專案被放置在下一個空桶中。W. Wesley Peterson 在 1957 年的《隨機存取儲存器的定址》中將這一想法正式化並發表。如今我們稱之為使用線性探測的開放定址雜湊表。
對於已經存在這麼長時間的資料結構，人們很容易認為它們已經“完成”了；認為我們已經瞭解了關於它們的一切，並且無法再改進了。這不是真的！計算機科學研究在基礎演算法方面不斷取得進展，無論是在演算法複雜度方面還是在利用現代 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 包含了一個基於 Swiss Table 設計的內建 map 型別全新實現。在這篇部落格文章中，我們將探討 Swiss Tables 相較於傳統雜湊表的改進之處，以及將 Swiss Table 設計引入 Go maps 所面臨的一些獨特挑戰。
開放定址雜湊表
Swiss Tables 是一種開放定址雜湊表，所以讓我們快速回顧一下基本的開放定址雜湊表是如何工作的。
在開放定址雜湊表中，所有專案都儲存在單個支援陣列中。我們將陣列中的每個位置稱為一個槽位（slot）。鍵所屬的槽位主要由雜湊函式（hash function） hash(key) 決定。雜湊函式將每個鍵對映到一個整數，相同的鍵總是對映到相同的整數，而不同的鍵理想情況下遵循均勻隨機的整數分佈。開放定址雜湊表的決定性特徵是它們透過將鍵儲存在支援陣列中的其他位置來解決衝突。因此，如果槽位已經滿了（發生衝突（collision）），則使用探測序列（probe sequence）來考慮其他槽位，直到找到一個空槽位。讓我們來看一個雜湊表示例，看看它是如何工作的。
示例
您可以在下面看到一個 16 個槽位的雜湊表支援陣列，以及儲存在每個槽位中的鍵（如果有）。此處不顯示值，因為它們與此示例無關。
| 槽位 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 鍵 | 56 | 32 | 21 | 78 |
要插入新鍵，我們使用雜湊函式選擇一個槽位。由於只有 16 個槽位，我們需要限制在此範圍內，因此我們將使用 hash(key) % 16 作為目標槽位。假設我們要插入鍵 98，並且 hash(98) % 16 = 7。槽位 7 是空的，所以我們直接將 98 插入那裡。另一方面，假設我們要插入鍵 25，並且 hash(25) % 16 = 3。槽位 3 發生衝突，因為它已經包含鍵 56。因此我們無法在此處插入。
我們使用探測序列來尋找另一個槽位。有多種眾所周知的探測序列。最初且最直接的探測序列是線性探測（linear probing），它只是按順序嘗試連續的槽位。
因此，在 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 設計也是一種開放定址雜湊表。讓我們看看它如何改進傳統的開放定址雜湊表。我們仍然使用單個支援陣列進行儲存，但我們將把陣列劃分為每個包含 8 個槽位的邏輯組（group）。（也可以使用更大的組大小。更多內容見下文。）
此外，每個組都有一個 64 位的控制字（control word）用於元資料。控制字中的每個位元組對應於組中的一個槽位。每個位元組的值表示該槽位是空的、已刪除的還是正在使用的。如果正在使用，該位元組包含該槽位鍵的雜湊值的低 7 位（稱為 h2）。
| 組 0 | 組 1 | |||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 槽位 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| 鍵 | 56 | 32 | 21 | 78 | ||||||||||||
| 64 位控制字 0 | 64 位控制字 1 | |||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 槽位 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| h2 | 23 | 89 | 50 | 47 | ||||||||||||
插入過程如下
- 計算
hash(key)並將雜湊值分成兩部分：高 57 位（稱為h1）和低 7 位（稱為h2）。 - 高位（
h1）用於選擇第一個要考慮的組：在本例中為h1 % 2，因為只有 2 個組。 - 在一個組內，所有槽位都可以同樣用於儲存鍵。我們首先必須確定是否有任何槽位已經包含此鍵，如果包含，則這是更新而非新的插入。
- 如果沒有槽位包含該鍵，則我們尋找一個空槽位來放置此鍵。
- 如果所有槽位都不為空，則我們透過搜尋下一個組來繼續探測序列。
查詢遵循相同的基本過程。如果在步驟 4 中找到一個空槽位，那麼我們就知道插入操作會使用這個槽位，可以停止搜尋了。
步驟 3 是 Swiss Table 魔法發生的地方。我們需要檢查組中的任何槽位是否包含所需的鍵。簡單來說，我們可以直接進行線性掃描並比較所有 8 個鍵。然而，控制字使我們能夠更高效地完成此操作。每個位元組包含該槽位雜湊值的低 7 位（h2）。如果我們確定控制字的哪些位元組包含我們正在尋找的 h2，我們將得到一組候選匹配項。
換句話說，我們希望在控制字內進行逐位元組的相等性比較。例如，如果我們要查詢鍵 32，其中 h2 = 89，我們想要的操作如下所示。
| 測試字 | 89 | 89 | 89 | 89 | 89 | 89 | 89 | 89 |
| 比較 | == | == | == | == | == | == | == | == |
| 控制字 | 23 | 89 | 50 | - | - | - | - | - |
| 結果 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 |
這是一個由 SIMD 硬體支援的操作，其中一條指令對較大值（向量（vector））中的獨立值執行並行操作。在這種情況下，當沒有特殊的 SIMD 硬體時，我們可以使用一組標準的算術和位操作來實現此操作。
結果是一組候選槽位。h2 不匹配的槽位不包含匹配的鍵，因此可以跳過。h2 匹配的槽位是潛在的匹配項，但我們仍然必須檢查完整的鍵，因為存在衝突的可能性（使用 7 位雜湊，衝突機率為 1/128，仍然相當低）。
此操作非常強大，因為我們有效地一次並行執行了探測序列的 8 個步驟。這透過減少我們需要執行的平均比較次數來加快查詢和插入的速度。這種對探測行為的改進使得 Abseil 和 Go 的實現都能提高 Swiss Table maps 的最大負載因子，相較於之前的 map，從而降低了平均記憶體佔用。
Go 面臨的挑戰
Go 的內建 map 型別具有一些不尋常的特性，這對採用新的 map 設計帶來了額外的挑戰。其中有兩個特別棘手。
增量增長
當雜湊表達到其最大負載因子時，它需要增長支援陣列。通常這意味著下一次插入會將陣列大小加倍，並將所有條目複製到新陣列中。想象一下向一個擁有 1GB 條目的 map 中插入。大多數插入操作都非常快，但需要將 map 從 1GB 增長到 2GB 的那次插入需要複製 1GB 的條目，這將花費很長時間。
Go 經常用於對延遲敏感的伺服器，因此我們不希望內建型別的操作對尾部延遲產生任意大的影響。相反，Go maps 增量增長，這樣每次插入都有其必須執行的增長工作量的上限。這限制了單個 map 插入的延遲影響。
不幸的是，Abseil (C++) Swiss Table 設計假設一次性增長，並且探測序列取決於總組數，這使得將其分解變得困難。
Go 的內建 map 透過將每個 map 分割成多個 Swiss Tables 來解決這個問題，增加了另一層間接性。每個 map 不是由單個 Swiss Table 實現整個 map，而是由一個或多個獨立的表組成，每個表覆蓋鍵空間的一個子集。單個表最多儲存 1024 個條目。雜湊值中可變數量的高位用於選擇鍵屬於哪個表。這是一種可擴充套件雜湊（extendible hashing）的形式，其中使用的位數根據需要增加，以區分總表的數量。
在插入過程中，如果單個表需要增長，它會一次性完成，但其他表不受影響。因此，單次插入的上限是將一個 1024 條目表增長為兩個 1024 條目表所需的延遲，即複製 1024 個條目。
迭代期間的修改
許多雜湊表設計，包括 Abseil 的 Swiss Tables，禁止在迭代期間修改 map。Go 語言規範明確允許在迭代期間進行修改，並具有以下語義
- 如果在到達某個條目之前將其刪除，該條目將不會被產生。
- 如果在到達某個條目之前對其進行更新，將產生更新後的值。
- 如果添加了新條目，則可能會或可能不會被產生。
雜湊表迭代的一種典型方法是簡單地遍歷支援陣列並按照它們在記憶體中的佈局順序產生值。這種方法與上述語義相悖，最顯著的原因是插入可能會導致 map 增長，從而打亂記憶體佈局。
我們可以透過讓迭代器保持對其當前正在迭代的表的引用來避免增長期間打亂佈局的影響。如果在迭代期間該表發生增長，我們將繼續使用表的舊版本，因此繼續按照舊記憶體佈局的順序提供鍵。
這與上述語義相容嗎？增長後新增的新條目將完全丟失，因為它們僅被新增到增長後的表，而不是舊錶。這沒問題，因為語義允許不產生新條目。然而，更新和刪除是一個問題：使用舊錶可能會產生過時或已刪除的條目。
透過僅使用舊錶來確定迭代順序來解決這個邊緣情況。在實際返回條目之前，我們會查閱增長後的表，以確定條目是否仍然存在，並檢索最新值。
這涵蓋了所有核心語義，儘管還有更多未在此處討論的細小邊緣情況。最終，Go maps 對迭代的寬鬆性導致迭代成為 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 挑戰的方案相結合，構建了 github.com/cockroachdb/swiss，一個符合 Go 規範的 Swiss Table 實現。Go 1.24 內建 map 實現很大程度上基於 Peter 的工作。感謝所有社群貢獻者！