在2024月11月5日的Go compiler and runtime meeting notes^[1]中，我們注意到了一段重要內(nèi)容，如下圖紅框所示：

圖片

這表明，來自字節(jié)的一位工程師在兩年多前提出的“使用Swiss table重新實現(xiàn)Go map^[2]”的建議即將落地，目前該issue已經(jīng)被納入Go 1.24里程碑^[3]。

Swiss Table是由Google工程師于2017年開發(fā)的一種高效哈希表實現(xiàn)，旨在優(yōu)化內(nèi)存使用和提升性能，解決Google內(nèi)部代碼庫中廣泛使用的std::unordered_map所面臨的性能問題。Google工程師Matt Kulukundis在2017年CppCon大會上詳細(xì)介紹了他們在Swiss Table上的工作^[4]：

圖片

目前，Swiss Table已被應(yīng)用于多種編程語言，包括C++ Abseil庫的flat_hash_map(可替換std::unordered_map)^[5]、Rust標(biāo)準(zhǔn)庫Hashmap的默認(rèn)實現(xiàn)^[6]等。

Swiss Table的出色表現(xiàn)是字節(jié)工程師提出這一問題的直接原因。字節(jié)跳動作為國內(nèi)使用Go語言較為廣泛的大廠。據(jù)issue描述，Go map的CPU消耗約占服務(wù)總體開銷的4%。其中，map的插入（mapassign）和訪問（mapaccess）操作的CPU消耗幾乎是1:1。大家可千萬不能小看4%這個數(shù)字，以字節(jié)、Google這樣大廠的體量，減少1%也意味著真金白銀的大幅節(jié)省。

Swiss Table被視為解決這一問題的潛在方案。字節(jié)工程師初版實現(xiàn)的基準(zhǔn)測試結(jié)果顯示，與原實現(xiàn)相比，Swiss Table在查詢、插入和刪除操作上均提升了20%至50%的性能，尤其是在處理大hashmap時表現(xiàn)尤為突出；迭代性能提升了10%；內(nèi)存使用減少了0%至25%，并且不再消耗額外內(nèi)存。

這些顯著的性能提升引起了Go編譯器和運行時團隊的關(guān)注，特別是當(dāng)時負(fù)責(zé)該子團隊的Austin Clements。在經(jīng)過兩年多的實驗和評估后，Go團隊成員Michael Pratt^[7]基于Swiss Table實現(xiàn)的internal/runtime/maps最終成為Go map的底層默認(rèn)實現(xiàn)。

在本文中，我們將簡單介紹Swiss Table這一高效的哈希表實現(xiàn)算法，并提前看一下Go map的Swiss Table實現(xiàn)。

在進(jìn)入swiss table工作原理介紹之前，我們先來回顧一下當(dāng)前Go map的實現(xiàn)(Go 1.23.x)。

1. Go map的當(dāng)前實現(xiàn)

map，也稱為映射，或字典，或哈希表^[8]，是和數(shù)組等一樣的最常見的數(shù)據(jù)結(jié)構(gòu)。實現(xiàn)map有兩個關(guān)鍵的考量，一個是哈希函數(shù)(hash function)，另一個就是碰撞處理(collision handling)。hash函數(shù)是數(shù)學(xué)家的事情，這里不表。對于碰撞處理，在大學(xué)數(shù)據(jù)結(jié)構(gòu)課程中，老師通常會介紹兩種常見的處理方案：

• 開放尋址法(Open Addressing)

在發(fā)生哈希碰撞時，嘗試在哈希表中尋找下一個可用的位置，如下圖所示k3與k1的哈希值發(fā)生碰撞后，算法會嘗試從k1的位置開始向后找到一個空閑的位置：

圖片

• 鏈?zhǔn)焦７?拉鏈法, Chaining)

每個哈希桶(bucket)存儲一個鏈表（或其他數(shù)據(jù)結(jié)構(gòu)），所有哈希值相同的元素(比如k1和k3)都被存儲在該鏈表中。

圖片

Go當(dāng)前的map實現(xiàn)采用的就是鏈?zhǔn)焦?，?dāng)然是經(jīng)過優(yōu)化過的了。要了解Go map的實現(xiàn)，關(guān)鍵把握住下面幾點：

• 編譯器重寫

我們在用戶層代碼中使用的map操作都會被Go編譯器重寫為對應(yīng)的runtime的map操作，就如下面Go團隊成員Keith Randall在GopherCon大會上講解map實現(xiàn)原理^[9]的一個截圖所示：

圖片

• 鏈?zhǔn)焦?/li>

前面提過，Go map當(dāng)前采用的是鏈?zhǔn)焦５膶崿F(xiàn)，一個map在內(nèi)存中的結(jié)構(gòu)大致如下：

圖片

來自Keith Randall的ppt截圖

我們看到，一個map Header代表了一個map類型的實例，map header中存儲了有關(guān)map的元數(shù)據(jù)(圖中字段與當(dāng)前實現(xiàn)可能有少許差異，畢竟那是幾年前的一個片子了)，如：

- len: 當(dāng)前map中鍵值對的數(shù)量。
- bucket array: 存儲數(shù)據(jù)的bucket數(shù)組，可以對比前面的鏈?zhǔn)焦５脑韴D進(jìn)行理解，不過不同的是，Go map中每個bucket本身就可以存儲多個鍵值對，而不是指向一個鍵值對的鏈表。
- hash seed: 用于哈希計算的種子，用于分散數(shù)據(jù)并提高安全性。

通常一個bucket可以存儲8個鍵值對，這些鍵值對是根據(jù)鍵的哈希值分配到對應(yīng)的bucket中。

• 溢出桶(overflow bucket)

每個bucket后面還會有Overflow Bucket。當(dāng)一個bucket中的數(shù)據(jù)超出容量時，會創(chuàng)建overflow bucket來存儲多余的數(shù)據(jù)。這樣可以避免直接擴展bucket數(shù)組，節(jié)省內(nèi)存空間。但如果出現(xiàn)過多的overflow bucket，性能就會下降。

• “螞蟻搬家”式的擴容

當(dāng)map中出現(xiàn)過多overflow bucket而導(dǎo)致性能下降時，我們就要考慮map bucket擴容的事兒了，以始終保證map的操作性能在一個合理的范圍。是否擴容由一個名為load factor的參數(shù)所控制。load factor是元素數(shù)量與bucket數(shù)量的比值，比值越高，map的讀寫性能越差。目前Go map采用了一個經(jīng)驗值來確定是否要擴容，即load factor = 6.5。當(dāng)load factor超過這個值時，就會觸發(fā)擴容。所謂擴容就是增大bucket數(shù)量(當(dāng)前實現(xiàn)為增大一倍數(shù)量)，減少碰撞，讓每個bucket中存放的element數(shù)量降下來。

擴容需要對存量element做rehash，在元素數(shù)量較多的情況下，“一次性”的完成桶的擴容會造成map操作延遲“突增”，無法滿足一些業(yè)務(wù)場景的要求，因此Go map采用“增量”擴容的方式，即在訪問和插入數(shù)據(jù)時，“螞蟻搬家”式的做點搬移元素的操作，直到所有元素完成搬移。

Go map的當(dāng)前實現(xiàn)應(yīng)該可以適合大多數(shù)的場合，但依然有一些性能和延遲敏感的業(yè)務(wù)場景覺得Go map不夠快，另外一個常被詬病的就是當(dāng)前實現(xiàn)的桶擴容后就不再縮容(shrink)了^[11]，這會給內(nèi)存帶來壓力。

下面我們再來看看swiss table的結(jié)構(gòu)和工作原理。

2. Swiss table的工作原理

就像前面提到的，Swiss table并非來自某個大學(xué)或研究機構(gòu)的論文，而是來自Google工程師在工程領(lǐng)域的"最佳實踐"，因此關(guān)于Swiss table的主要資料都來自Google的開源C++ library Abseil^[12]以及開發(fā)者的演講視頻^[13]。在Abseil庫中，它是flat_hash_map、flat_hash_set、node_hash_map以及node_hash_set等數(shù)據(jù)結(jié)構(gòu)的底層實現(xiàn)，并且Swiss table的實現(xiàn)在2018年9月正式開源^[14]。

和Go map當(dāng)前實現(xiàn)不同，Swiss table使用的不是拉鏈法，而是開放尋址，但并非傳統(tǒng)的方案。下面是根據(jù)公開資源畫出的一個Swiss table的邏輯結(jié)構(gòu)圖(注意：并非真實內(nèi)存布局)：

圖片

如果用一個式子來表示Swiss table，我們可以用：

A swiss table = N * (metdata array + slots array)

我們看到：swiss table將所謂的桶（這里叫slot）分為多個group，每個group中有16個slot，這也是swiss table的創(chuàng)新，即將開放尋址方法中的probing(探測key碰撞后下一個可用的位置(slot))放到一個16個slot的group中進(jìn)行，這樣的好處是可以通過一個SIMD指令^[15]并行探測16個slot，這種方法也被稱為Group Probing。

在上圖中，我們看到一個Group由metadata和16個slot組成。metadata中存儲的是元數(shù)據(jù)，而slot中存儲的是元素(key和value)。Group probling主要是基于metadata實現(xiàn)的，Google工程師的演講有對group probing實現(xiàn)的細(xì)節(jié)描述。

當(dāng)我們向swiss table插入一個元素或是查找一個元素時，swiss table會通過hash函數(shù)對key進(jìn)行求值，結(jié)果是一個8字節(jié)(64bit)的數(shù)。和Go map的當(dāng)前實現(xiàn)一樣，這個哈希值的不同bit功用不同，下圖是一個來自abseil官網(wǎng)的示例：

圖片

哈希值的高57bit被稱為H1，低7bit被稱為H2。前者用于標(biāo)識該元素在Group內(nèi)的索引，查找和插入時都需要它。后者將被用于該元素的元數(shù)據(jù)，放在metadata中存儲，用于快速的group probing之用，也被稱為哈希指紋。

每個Group的metadata也是一個16字節(jié)數(shù)組，每個字節(jié)對應(yīng)一個slot，是該slot的控制字節(jié)。這個字節(jié)的8個bit位的組成如下：

圖來自abseil庫官網(wǎng)

metadata中的控制字節(jié)有三個狀態(tài)：

• 最高位為1，其余全零為**空閑狀態(tài)(Empty)**，即對應(yīng)的slot尚未曾被任何element占據(jù)過；
• 最高位為0，后7位為哈希指紋(H2)，為對應(yīng)的slot當(dāng)前已經(jīng)有element占據(jù)的已使用狀態(tài)；
• 最高位為1，其他位為1111110的，為對應(yīng)的slot為已刪除狀態(tài)，后續(xù)可以被繼續(xù)使用。

下面是Abseil開發(fā)者演進(jìn)slide中的一個針對swiss table的迭代邏輯：

圖片

通過這幅圖可以看出H1的作用。不過這里通過pos = pos + 1進(jìn)行probing（探測）顯然是不高效的！metadata之所以設(shè)計為如此，并保存了插入元素的哈希指紋就是為了實現(xiàn)高效的probing，下圖演示了基于key的hash值的H2指紋通過SIMD指令從16個位置中快速得到匹配的pos的過程：

圖片

雖然有兩個匹配項，但這個過程就像“布隆過濾器”一樣，快速排除了不可能的匹配項，減少了不必要的內(nèi)存訪問。

由于metadata僅有16個字節(jié)，它的內(nèi)存局部性更好。16個控制字節(jié)正好填充一個64字節(jié)的緩存行(cache line)，使用SIMD指令一次性加載整組控制字節(jié)，預(yù)取效率高，幾乎沒有cache miss。

由此也可以看到：swiss table的16個條目的分組大小不是隨意選擇的，而是基于現(xiàn)代CPU的緩存行大小(64字節(jié))優(yōu)化的，保證了一個Group的控制字節(jié)能被單次SIMD指令處理。

此外swiss table也是通過load factor來判定是否需要對哈希表進(jìn)行擴容，一旦擴容，swiss table通常是會將group數(shù)量增加一倍，然后重新計算當(dāng)前所有元素在新groups中的新位置(rehash)，這個過程是有一定開銷的。如果不做優(yōu)化，當(dāng)表中元素數(shù)量較多時，這個過程會導(dǎo)致操作延遲增加。

最后，雖然多數(shù)情況是在group內(nèi)做probing，但當(dāng)元素插入時，如果當(dāng)前Group已滿，就必須探測到下一個Group，并將元素插入到下一個Group。這樣，在該元素的查找操作中，probing也會跨group進(jìn)行。

到這里，我們已經(jīng)粗略了解了swiss table的工作原理，那么Go tip對swiss table當(dāng)前的實現(xiàn)又是怎樣的呢？我們下面就來看看。

3. Go tip版本當(dāng)前的實現(xiàn)

Go tip版本基于swiss table的實現(xiàn)在https://github.com/golang/go/blob/master/src/internal/runtime/maps下。

由于Go map是原生類型，且有了第一版實現(xiàn)，考慮到Go1兼容性，新版基于swiss table的實現(xiàn)也要繼承已有的語義約束。同時，也要盡量避免swiss table自身的短板，Go團隊在swiss table之上做了局部改進(jìn)。比如為了將擴容帶來的開銷降到最低，Go引入了多table的設(shè)計，以支持漸進(jìn)式擴容。也就是說一個map實際上是多個swiss table，而不是像上面說的一個map就是一個swiss table。每個table擁有自己的load factor，可以獨立擴容(table的擴容是一次性擴容)，這樣就可以將擴容的開銷從全部數(shù)據(jù)變?yōu)榫植可倭繑?shù)據(jù)，減少擴容帶來的影響。

Go swiss-table based map的邏輯結(jié)構(gòu)大致如下：

圖片

我們可以看出與C++ swisstable的最直觀不同之處除了有多個table外，每個group包含8個slot和一個control word，而不是16個slot。此外，Go使用了二次探測(quadratic probing), 探測序列必須以空slot結(jié)束。

為了實現(xiàn)漸進(jìn)式擴容，數(shù)據(jù)分散在多個table中；單個table容量有上限(maxTableCapacity)，超過上限時分裂成兩個table；使用可擴展哈希(extendible hashing)根據(jù)hash高位選擇table，且每個table可以獨立增長。

Go使用Directory管理多個table，Directory是Table的數(shù)組，大小為2^globalDepth。如果globalDepth=2，那Directory最多有4個表，分為0x00、0x01、0x10、0x11。Go通過key的hash值的前globalDepth個bit來選擇table。這是一種“extendible hashing”，這是一種動態(tài)哈希技術(shù)，其核心特點是通過動態(tài)調(diào)整使用的哈希位數(shù)(比如上面提到的globalDepth)來實現(xiàn)漸進(jìn)式擴容。比如：初始可能只用1位哈希值來區(qū)分，需要時可以擴展到用2位，再需要時可以擴展到用3位，以此類推。

舉個例子，假設(shè)我們用二進(jìn)制表示哈希值的高位，來看一個漸進(jìn)式擴容的過程：

• 初始狀態(tài) (Global Depth = 1):

directory
hash前綴  指向的table
0*** --> table1 (Local Depth = 1)
1*** --> table2 (Local Depth = 1)

• 當(dāng)table1滿了需要分裂時，增加一位哈希值 (Global Depth = 2):

directory
hash前綴  指向的table
00** --> table3 (Local Depth = 2)  // 由table1擴容而成
01** --> table4 (Local Depth = 2)  // 由table1擴容而成
10** --> table2 (Local Depth = 1)
11** --> table2 (Local Depth = 1)  // 復(fù)用table2因為它的Local Depth還是1

• 如果table2也滿了，需要分裂：

directory
hash前綴  指向的table
00** --> table3 (Local Depth = 2)
01** --> table4 (Local Depth = 2)
10** --> table5 (Local Depth = 2) // 由table2擴容而成
11** --> table6 (Local Depth = 2) // 由table2擴容而成

通過extendible hashing實現(xiàn)的漸進(jìn)式擴容，每次只處理一部分?jǐn)?shù)據(jù)，擴容過程對其他操作影響小，空間利用更靈活。

對于新版go map實現(xiàn)而言，單個Table達(dá)到負(fù)載因子閾值時觸發(fā)Table擴容。當(dāng)需要分裂的Table的localDepth等于map的globalDepth時觸發(fā)Directory擴容，這就好理解了。

除此之外，Go版本對small map也有特定優(yōu)化，比如少量元素(<=8)時直接使用單個group，避免或盡量降低swiss table天生在少量元素情況下的性能回退問題。

更多實現(xiàn)細(xì)節(jié)，大家可以自行閱讀https://github.com/golang/go/blob/master/src/internal/runtime/maps/下的Go源碼進(jìn)行理解。

注：目前swiss table版的go map依然還未最終定型，并且后續(xù)還會有各種優(yōu)化加入，這里只是對當(dāng)前的實現(xiàn)(2024.11.10)做概略介紹，不代表以后的map實現(xiàn)與上述思路完全一致。

4. Benchmark

目前gotip版本中GOEXPERIMENT=swissmap默認(rèn)已經(jīng)打開^[16]，我們直接用gotip版本即可體驗基于swiss table實現(xiàn)的map。

字節(jié)工程師zhangyunhao的gomapbench repo^[17]提供了對map的性能基準(zhǔn)測試代碼，不過這個基準(zhǔn)測試太多，我大幅簡化了一下，只使用Int64，并只測試了元素個數(shù)分別為12、256和8192時的情況。

注：我基于Centos 7.9，使用Go 1.23.0和gotip(devel go1.24-84e58c8 linux/amd64)跑的benchmark。

// 在experiments/swiss-table-map/mapbenchmark目錄下
$go test -run='^$' -timeout=10h -bench=. -count=10 > origin-map.txt 
$GOEXPERIMENT=swissmap gotip test -run='^$' -timeout=10h -bench=. -count=10 > swiss-table-map.txt 
$benchstat origin-map.txt swiss-table-map.txt > result.txt

下面是result.txt中的結(jié)果：

goos: linux
goarch: amd64
pkg: demo
cpu: Intel(R) Xeon(R) Platinum
                                  │ origin-map.txt │         swiss-table-map.txt          │
                                  │     sec/op     │    sec/op     vs base                │
MapIter/Int/12-8                      179.7n ± 10%   190.6n ±  4%        ~ (p=0.436 n=10)
MapIter/Int/256-8                     4.328μ ±  5%   3.748μ ±  1%  -13.40% (p=0.000 n=10)
MapIter/Int/8192-8                    137.3μ ±  1%   123.6μ ±  1%   -9.95% (p=0.000 n=10)
MapAccessHit/Int64/12-8               10.12n ±  2%   10.68n ± 14%   +5.64% (p=0.000 n=10)
MapAccessHit/Int64/256-8              10.29n ±  3%   11.29n ±  1%   +9.77% (p=0.000 n=10)
MapAccessHit/Int64/8192-8             25.99n ±  1%   14.93n ±  1%  -42.57% (p=0.000 n=10)
MapAccessMiss/Int64/12-8              12.39n ± 88%   20.99n ± 50%        ~ (p=0.669 n=10)
MapAccessMiss/Int64/256-8             13.12n ±  6%   11.34n ±  7%  -13.56% (p=0.000 n=10)
MapAccessMiss/Int64/8192-8            15.71n ±  1%   14.03n ±  1%  -10.66% (p=0.000 n=10)
MapAssignGrow/Int64/12-8              607.1n ±  2%   622.6n ±  2%   +2.54% (p=0.000 n=10)
MapAssignGrow/Int64/256-8             25.98μ ±  3%   23.22μ ±  1%  -10.64% (p=0.000 n=10)
MapAssignGrow/Int64/8192-8            792.3μ ±  1%   844.1μ ±  1%   +6.54% (p=0.000 n=10)
MapAssignPreAllocate/Int64/12-8       450.2n ±  2%   409.2n ±  1%   -9.11% (p=0.000 n=10)
MapAssignPreAllocate/Int64/256-8     10.412μ ±  1%   6.055μ ±  2%  -41.84% (p=0.000 n=10)
MapAssignPreAllocate/Int64/8192-8     342.4μ ±  1%   232.6μ ±  2%  -32.05% (p=0.000 n=10)
MapAssignReuse/Int64/12-8             374.2n ±  1%   235.4n ±  2%  -37.07% (p=0.000 n=10)
MapAssignReuse/Int64/256-8            8.737μ ±  1%   4.716μ ±  4%  -46.03% (p=0.000 n=10)
MapAssignReuse/Int64/8192-8           296.4μ ±  1%   181.0μ ±  1%  -38.93% (p=0.000 n=10)
geomean                               1.159μ         984.2n        -15.11%

我們看到了除了少數(shù)測試項有不足外(比如MapAssignGrow以及一些元素數(shù)量少的情況下)，大多數(shù)測試項中，新版基于swiss table的map的性能都有大幅提升，有些甚至接近50%！

5. 小結(jié)

本文探討了Go語言中的map實現(xiàn)的重塑，即引入Swiss Table這一高效哈希表結(jié)構(gòu)的背景與優(yōu)勢。Swiss Table由Google工程師開發(fā)，旨在優(yōu)化內(nèi)存使用和提升性能，解決了傳統(tǒng)哈希表在高負(fù)載情況下的性能瓶頸。通過對比現(xiàn)有的鏈?zhǔn)焦崿F(xiàn)，Swiss Table展示了在查詢、插入和刪除操作上顯著提高的性能，尤其是在處理大規(guī)模數(shù)據(jù)時。

經(jīng)過兩年多的實驗與評估，Go團隊決定將Swiss Table作為Go map的底層實現(xiàn)，預(yù)計將在Go 1.24^[19]中正式落地。新的實現(xiàn)不僅承繼了原有的語義約束，還通過引入多表和漸進(jìn)式擴容的設(shè)計，進(jìn)一步優(yōu)化了擴容過程的性能。盡管當(dāng)前實現(xiàn)仍在完善中，但Swiss Table的引入無疑為Go語言的性能提升提供了新的可能性，并為未來進(jìn)一步優(yōu)化奠定了基礎(chǔ)。

對于那些因Go引入自定義iterator^[20]而批評Go團隊的Gopher來說，這個Go map的重塑無疑會很對他們的胃口。

本文涉及的源碼可以在這里^[21]下載。

6. 參考資料

• runtime: use SwissTable^[22] - https://github.com/golang/go/issues/54766
• swiss table benchmark result^[23] - https://gist.github.com/aclements/9fb32ac0a287d2ff360f1bc166cdf4b8
• Swisstable, a Quick and Dirty Description^[24] - https://faultlore.com/blah/hashbrown-tldr/
• Swiss Tables Design Notes^[25] - https://abseil.io/about/design/swisstables
• Designing a Fast, Efficient, Cache-friendly Hash Table, Step by Step^[26] - https://www.youtube.com/watch?v=ncHmEUmJZf4
• Abseil's Open Source Hashtables: 2 Years In^[27] - https://www.youtube.com/watch?v=JZE3_0qvrMg
• Swiss Tables and absl::Hash^[28] - https://abseil.io/blog/20180927-swisstables
• SwissMap: A smaller, faster Golang Hash Table^[29] - https://www.dolthub.com/blog/2023-03-28-swiss-map/
• What is a Hash Map?^[30] - https://www.freecodecamp.org/news/what-is-a-hash-map/
• Inside the Map Implementation^[31] - https://www.youtube.com/watch?v=Tl7mi9QmLns

參考資料

[1] 2024月11月5日的Go compiler and runtime meeting notes: https://github.com/golang/go/issues/43930#issuecomment-2458068992

[2] 使用Swiss table重新實現(xiàn)Go map: https://github.com/golang/go/issues/54766

[3] Go 1.24里程碑: https://github.com/golang/go/milestone/322

[4] Google工程師Matt Kulukundis在2017年CppCon大會上詳細(xì)介紹了他們在Swiss Table上的工作: https://www.youtube.com/watch?v=ncHmEUmJZf4

[5] C++ Abseil庫的flat_hash_map(可替換std::unordered_map): https://abseil.io/about/design/swisstables

[6] Rust標(biāo)準(zhǔn)庫Hashmap的默認(rèn)實現(xiàn): https://github.com/rust-lang/hashbrown

[7] Michael Pratt: https://github.com/prattmic

[8] 哈希表: https://en.wikipedia.org/wiki/Hash_table

[9] map實現(xiàn)原理: https://www.youtube.com/watch?v=Tl7mi9QmLns

[10] 《Go語言第一課》: http://gk.link/a/10AVZ

[11] 不再縮容(shrink)了: https://github.com/golang/go/issues/20135

[12] Google的開源C++ library Abseil: https://abseil.io/

[13] 開發(fā)者的演講視頻: https://www.youtube.com/watch?v=ncHmEUmJZf4

[14] Swiss table的實現(xiàn)在2018年9月正式開源: https://abseil.io/blog/20180927-swisstables

[15] SIMD指令: https://tonybai.com/2024/07/21/simd-in-go

[16] GOEXPERIMENT=swissmap默認(rèn)已經(jīng)打開: https://github.com/golang/go/commit/99d60c24e23d4d97ce51b1ee5660b60a5651693a

[17] gomapbench repo: https://github.com/zhangyunhao116/gomapbench

[18] 《Go語言第一課》: http://gk.link/a/10AVZ

[19] Go 1.24: https://github.com/golang/go/milestone/322

[20] 自定義iterator: https://tonybai.com/2024/06/24/range-over-func-and-package-iter-in-go-1-23/

[21] 這里: https://github.com/bigwhite/experiments/tree/master/swiss-table-map

[22] runtime: use SwissTable: https://github.com/golang/go/issues/54766

[23] swiss table benchmark result: https://gist.github.com/aclements/9fb32ac0a287d2ff360f1bc166cdf4b8

[24] Swisstable, a Quick and Dirty Description: https://faultlore.com/blah/hashbrown-tldr/

[25] Swiss Tables Design Notes: https://abseil.io/about/design/swisstables

[26] Designing a Fast, Efficient, Cache-friendly Hash Table, Step by Step: https://www.youtube.com/watch?v=ncHmEUmJZf4

[27] Abseil's Open Source Hashtables: 2 Years In: https://www.youtube.com/watch?v=JZE3_0qvrMg

[28] Swiss Tables and absl::Hash: https://abseil.io/blog/20180927-swisstables

[29] SwissMap: A smaller, faster Golang Hash Table: https://www.dolthub.com/blog/2023-03-28-swiss-map/

[30] What is a Hash Map?: https://www.freecodecamp.org/news/what-is-a-hash-map/

[31] Inside the Map Implementation: https://www.youtube.com/watch?v=Tl7mi9QmLns