Go 新版泛型使用：80餘行代碼建構一個哈希表

Go 新版泛型使用：80餘行代碼建構一個哈希表

2018 年，我使用 Go 語言實作了一個玩具性質的哈希表 (1)，以便學習 Go 的 map 等資料類型如何工作。這個版本隻支援字元串作為 key 以及 value。

1.https://github.com/mdlayher/misc/blob/master/go/algorithms/hashtable/hashtable.go

兩年後的 2020 年 6 月，Go 團隊釋出了一篇題為《泛型的下一步 (1) 》的文章，提供了一個新版的泛型草案設計，它基于擴充 Go 現有的接口，而不是添加 contract 等新概念來實作。如果你還沒看過，我強烈建議你至少浏覽一下新的設計草案文檔 (2)。我不是專家，隻能以我有限的經驗和時間來談論這個設計。

1.https://blog.golang.org/generics-next-step

2.https://go.googlesource.com/proposal/+/refs/heads/master/design/go2draft-type-parameters.md

這篇文章将分享如何将我的玩具 hashtable 移植到新的泛型設計。如果你想跳過介紹并直接檢視泛型代碼，請随時跳到第二部分 "泛型哈希表" 章節。

我 2018 年開始的初步設計版本，隻支援字元串鍵和值。

Table 類型是這個包的基礎。它内部使用 slice 存儲鍵/值字元串對，其中 slice 内的 hashtable buckets 數量由一個整數 m 決定。

一個較小的 m 意味着較少的桶将被建立，但是每個存儲在 Table 中的鍵有較高的可能性與其他鍵共享一個桶，進而減慢了查找速度

更大的 m 意味着将建立更多的桶，是以存儲在 Table 中的每個鍵與其他鍵共享一個桶的可能性較低，進而加快了查找速度。

kv 類型是一個小幫手，用于簡潔地存儲鍵/值字元串對。

這個哈希表支援兩種操作：

Get: 确定一個鍵是否存在于哈希表中，傳回對應的值（如果找到），以及一個布爾值，表示對象是否存在。

Insert：在哈希表中插入一個新的鍵/值對，覆寫同一鍵的任何先前的值。

這兩個操作都需要一個哈希函數，它可以接受一個輸入字元串，并傳回一個整數，表示鍵值可能存在的桶。

我選擇了 hash/fnv32 作為一個簡單的、非加密的哈希函數，它可以傳回一個整數。然後通過計算模數運算 hash % t.m，我們可以確定得到的整數傳回我們的一個哈希表桶的索引。

下面是 Get 操作對應的代碼。

Table.Get 對輸入的 key 進行哈希處理，以确定存儲鍵的值位于哪個桶。一旦确定了 bucket，它就會周遊該 bucket 中的所有 key/value 對，如果 key 與該 bucket 中的某個 key 比對，則傳回該 bucket 的值和 boolean true。

如果輸入的鍵與該桶中的鍵比對，傳回該桶的值和布爾值 true。

如果沒有比對，傳回一個空字元串和布爾值 false。

接下來，我們來看看 Insert。

Table.Insert 也需要對輸入 key 進行哈希處理，以确定應該使用哪個桶來插入鍵/值對。當疊代一個桶中的鍵/值對時，我們可能會發現一個比對的 key 已經存在。

如果輸入的 key 與該 bucket 中的 key 比對，則用新的值覆寫 key 的值。

如果沒有比對，則在 bucket 的 key/value pair slice 中添加一個新條目。

搞定了！我們已經建立了一個非常基本的哈希表，可以用來處理鍵/值字元串對。

讓我們把現有的這段代碼移植到新的 Go 泛型設計中去。

我們的目标是利用現有的 hashtable 代碼，使其能支援任意鍵/值對類型。但我們有一個限制：我們的 hashable 中的 key 必須與預先聲明的類型限制 comparable 相比對，以便我們可以做等值比較。

編輯：原本這段代碼使用了 type K, V comparable，但這是不是必須的。感謝 Brad Fitzpatrick 和 @nemetroid 指出，type K comparable, V interface{} 就足夠了。

凡是需要泛型的地方，都需要新的類型參數清單，是以這些頂層類型和函數都必須有 K 和 V 的類型參數清單，用于 K 的類型必須是 comparable，任何類型都可以用于 V，如 interface{} 所示。

在寫這段代碼的時候，學會了下面一些神奇的操作。

注意，哈希函數 func(K, int) int 現在是傳遞給 New 的第二個參數。這是必要的，因為我們必須知道如何對任何給定的泛型進行哈希。我本可以用 Hash() int 限制或類似的方式建立一個新的接口，但我希望我的哈希表能與内置的 Go 類型（如 string 和 int）一起工作，而你沒法在這些類型上定義方法。

我花了一點時間來弄清楚建立 Table.table 時 make() 調用的正确括号用法。我最初的嘗試使用了 make([][]kv(K, V))，這對增加的類型參數是行不通的。

是時候實作 Get:

一個定義在泛型上的方法，必須在其接受者中聲明相關的通用類型參數。現在，Get 可以接受任何類型的 K，并傳回任何類型的 V，同時用 bool 表示是否找到了值。

除了修改後的方法接收器和一些 K 和 V 類型之外，這看起來和典型的 Go 代碼差不多。

這裡有一個稍顯棘手的問題是如何處理一個泛型的零值 (1)。連結的問題建議像我們在這裡所做的那樣，通過聲明 var zero V，但也許在未來可以有一個更簡單的選項來做這件事。我個人很希望看到傳回 _、false 或類似的選項，作為泛型和非泛型 Go 的選項。

https://go.googlesource.com/proposal/+/refs/heads/master/design/go2draft-type-parameters.md#the-zero-value

我們繼續說說 Insert。

為了使這段代碼成為泛型代碼，隻需要做很少的修改。

方法接收器現在是 Table(K, V)，而不是 Table。

輸入參數現在是 (key K, value V) 而不是 (key, value string)

kv{} struct 現在必須聲明為 kv(K, V){}。

這就是所有需要做的，我們現在有了一個泛型的哈希表類型，它可以接受任何實作 comparable 類型限制的鍵和值。

為了測試這段代碼，我決定建立兩個并行的哈希表，作為字元串和整數類型之間的索引和反向索引。

在調用泛型構造函數 New 時，我們指定泛型 K 和 V 的類型參數，例如 t1 是 Table(string, int)，意思是 K=string，V=int；t2 則相反：Table(int, string)， 因為 int 和 string 都符合 comparable 類型限制，是以完全沒問題。

為了對泛型進行散列，我們必須提供一個可以對 K 和 t.m 進行操作的散列函數，以産生一個 int 輸出。對于 t1，我們重新使用原始例子中的 hash/fnv 哈希。至于 t2，對于我們的示範來說，一個模數運算似乎就足夠了。

我明白，在大多數情況下，Go 編譯器應該能夠在 hashtable.New 這樣的調用站點推斷出 K 和 V 等泛型的正确類型，但我可能會繼續用顯式的方式寫它們一段時間，以習慣這種設計。

現在我們已經建立了索引和反向索引的哈希表，讓我們來填充它們。

t1 中的每一個鍵/值對都會被鏡像為 t2 中的值/鍵。最後，我們可以疊代已知的字元串和索引（以及一個永遠不會被發現的附加值），以顯示我們的泛型代碼的作用。

我們的示範程式的輸出如下。

寫完收工，我們已經在 Go 語言中實作了一個泛型哈希表。

為了更好地了解新的泛型設計草案，我還有不少實驗要做。如果你喜歡這篇文章并想更多了解泛型，請檢視 Go 官方說明 (1) 和新的泛型設計草案文檔。

https://blog.golang.org/generics-next-step

如果你有問題或評論，請随時在 Twitter 或 Gophers Slack 上通過 @mdlayher 聯系我。我很可能在不久的将來也會在 Twitch 上直播一些 Go 泛型内容。

在實作我的泛型 hashtable 時，我在 Gophers Slack 上與 #performance 的一些網友讨論了如何才能通路内置 Go map 使用的運作時的泛型哈希功能。

Gophers Slack 的 @zeebo 提出了這個有趣的、彪悍的、出色的解決方案。

這段代碼濫用了這樣一個功能，即 Go 接口實際上是一個運作時類型資料的元組和一個類型的指針。通過通路該指針，并使用 unsafe 将其轉換為運作時的 map 表示（它有一個散列函數字段），我們可以建立一個泛型的散列函數，用于我們自己的代碼中。

很酷，對吧？

80餘行代碼的例子見：（可線上運作）

https://go2goplay.golang.org/p/2pcBZTQdh3u

本文英文連結：

https://mdlayher.com/blog/go-generics-draft-design-building-a-hashtable/

哔哩哔哩「會員購」在流量回放上的探索

新項目用 Rust 還是 Go ？

Go語言如何實作stop the world？

為什麼我放棄使用 Kotlin 中的協程？

基準測試表明, Async Python 遠不如同步方式

談談PHP8新特性Attributes

本文由高可用架構翻譯，技術原創及架構實踐文章，歡迎通過公衆号菜單「聯系我們」進行投稿。