PHP8go技巧_Go 新版泛型运用80余行代码构建一个哈希表

文章目录 [+]

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

两年后的 2020 年 6 月，Go 团队发布了一篇题为《泛型的下一步 (1) 》的文章，供应了一个新版的泛型草案设计，它基于扩展 Go 现有的接口，而不是添加 contract 等新观点来实现。
如果你还没看过，我强烈建议你至少浏览一下新的设计草案文档 (2)。
我不是专家，只能以我有限的履历和韶光来评论辩论这个设计。

PHP8go技巧_Go 新版泛型运用80余行代码构建一个哈希表

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

（图片来自网络侵删）

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 类型是一个小帮手，用于简洁地存储键/值字符串对。

// Package hashtable implements a basic hashtable for string key/value pairs.package hashtable// A Table is a basic hashtable.type Table struct { m int table kv}// A kv stores key/value data in a Table.type kv struct { Key, Value string}// New creates a Table with m internal buckets.func New(m int) Table { return &Table{ m: m, table: make([][]kv, m), }}

这个哈希表支持两种操作：

Get: 确定一个键是否存在于哈希表中，返回对应的值（如果找到），以及一个布尔值，表示工具是否存在。

Insert：在哈希表中插入一个新的键/值对，覆盖同一键的任何先前的值。

这两个操作都须要一个哈希函数，它可以接管一个输入字符串，并返回一个整数，表示键值可能存在的桶。

// hash picks a hashtable index to use to store a string with key s.func (t Table) hash(s string) int { h := fnv.New32 h.Write(byte(s)) return int(h.Sum32) % t.m}

我选择了 hash/fnv32 作为一个大略的、非加密的哈希函数，它可以返回一个整数。
然后通过打算模数运算 hash % t.m，我们可以确保得到的整数返回我们的一个哈希表桶的索引。

下面是 Get 操为难刁难应的代码。

// Get determines if key is present in the hashtable, returning its value and// whether or not the key was found.func (t Table) Get(key string) (string, bool) { // Hash key to determine which bucket this key's value belongs in. i := t.hash(key) for j, kv := range t.table[i] { if key == kv.Key { // Found a match, return it! return t.table[i][j].Value, true } } // No match. return \"大众\"大众, false}

Table.Get 对输入的 key 进行哈希处理，以确定存储键的值位于哪个桶。
一旦确定了 bucket，它就会遍历该 bucket 中的所有 key/value 对，如果 key 与该 bucket 中的某个 key 匹配，则返回该 bucket 的值和 boolean true。

如果输入的键与该桶中的键匹配，返回该桶的值和布尔值 true。

如果没有匹配，返回一个空字符串和布尔值 false。

接下来，我们来看看 Insert。

// Insert inserts a new key/value pair into the Table.func (t Table) Insert(key, value string) { i := t.hash(key) for j, kv := range t.table[i] { if key == kv.Key { // Overwrite previous value for the same key. t.table[i][j].Value = value return } } // Add a new value to the table. t.table[i] = append(t.table[i], kv{ Key: key, Value: value, })}

Table.Insert 也须要对输入 key 进行哈希处理，以确定该当利用哪个桶来插入键/值对。
当迭代一个桶中的键/值对时，我们可能会创造一个匹配的 key 已经存在。

如果输入的 key 与该 bucket 中的 key 匹配，则用新的值覆盖 key 的值。

如果没有匹配，则在 bucket 的 key/value pair slice 中添加一个新条款。

搞定了！
我们已经创建了一个非常基本的哈希表，可以用来处理键/值字符串对。

// 8 buckets ought to be plenty.t := hashtable.New(8)t.Insert(\公众foo\"大众, \公众bar\"大众)t.Insert(\公众baz\公众, \公众qux\公众)v, ok := t.Get(\公众foo\公众)fmt.Printf(\"大众t.Get(%q) = (%q, %t)\公众, \公众foo\"大众, v, ok)// t.Get(\"大众foo\公众) = (\"大众bar\"大众, true)

让我们把现有的这段代码移植到新的 Go 泛型设计中去。

泛型哈希表

我们的目标是利用现有的 hashtable 代码，使其能支持任意键/值对类型。
但我们有一个约束：我们的 hashable 中的 key 必须与预先声明的类型约束 comparable 相匹配，以便我们可以做等值比较。

编辑：原来这段代码利用了 type K, V comparable，但这是不是必须的。
感谢 Brad Fitzpatrick 和 @nemetroid 指出，type K comparable, V interface{} 就足够了。

// Package hashtable implements a basic hashtable for generic key/value pairs.package hashtable// A Table is a basic generic hashtable.type Table(type K comparable, V interface{}) struct { // hash is a function which can hash a key of type K with t.m. hash func(key K, m int) int m int table kv}// A kv stores generic key/value data in a Table.type kv(type K comparable, V interface{}) struct { Key K Value V}// New creates a table with m internal buckets which uses the specified hash// function for an input type K.func New(type K comparable, V interface{})(m int, hash func(K, int) int) Table(K, V) { return &Table(K, V){ hash: hash, m: m, // Note the parentheses around \"大众kv(K, V)\"大众; these are required! table: make((kv(K, V)), m), }}

凡是须要泛型的地方，都须要新的类型参数列表，因此这些顶层类型和函数都必须有 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 determines if key is present in the hashtable, returning its value and// whether or not the key was found.func (t Table(K, V)) Get(key K) (V, bool) { // Hash key to determine which bucket this key's value belongs in. // Pass t.m so t.hash can perform the necessary operation \"大众hash % t.m\"大众. i := t.hash(key, t.m) for j, kv := range t.table[i] { if key == kv.Key { // Found a match, return it! return t.table[i][j].Value, true } } // No match. The easiest way to return the zero-value for a generic type // is to declare a temporary variable as follows. var zero V return zero, false}

一个定义在泛型上的方法，必须在其接管者中声明干系的通用类型参数。
现在，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。

// Insert inserts a new key/value pair into the Table.func (t Table(K, V)) Insert(key K, value V) { i := t.hash(key, t.m) for j, kv := range t.table[i] { if key == kv.Key { // Overwrite previous value for the same key. t.table[i][j].Value = value return } } // Add a new value to the table. t.table[i] = append(t.table[i], kv(K, V){ Key: key, Value: value, })}

为了使这段代码成为泛型代码，只须要做很少的修正。

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

输入参数现在是 (key K, value V) 而不是 (key, value string)

kv{} struct 现在必须声明为 kv(K, V){}。

这便是所有须要做的，我们现在有了一个泛型的哈希表类型，它可以接管任何实现 comparable 类型约束的键和值。

泛型哈希表的用法

为了测试这段代码，我决定创建两个并行的哈希表，作为字符串和整数类型之间的索引和反向索引。

t1 := hashtable.New(string, int)(8, func(key string, m int) int { h := fnv.New32 h.Write(byte(key)) return int(h.Sum32) % m})t2 := hashtable.New(int, string)(8, func(key int, m int) int { // Good enough! return key % m})

在调用泛型布局函数 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 等泛型的精确类型，但我可能会连续用显式的办法写它们一段韶光，以习气这种设计。

现在我们已经创建了索引和反向索引的哈希表，让我们来添补它们。

strs := string{\"大众foo\"大众, \"大众bar\"大众, \"大众baz\公众}for i, s := range strs { t1.Insert(s, i) t2.Insert(i, s)}

t1 中的每一个键/值对都会被镜像为 t2 中的值/键。
末了，我们可以迭代已知的字符串和索引（以及一个永久不会被创造的附加值），以显示我们的泛型代码的浸染。

for i, s := range append(strs, \公众nope!\公众) { v1, ok1 := t1.Get(s) log.Printf(\公众t1.Get(%v) = (%v, %v)\"大众, s, v1, ok1) v2, ok2 := t2.Get(i) log.Printf(\公众t2.Get(%v) = (%v, %v)\n\n\公众, i, v2, ok2)}

我们的演示程序的输出如下。

t1.Get(foo) = (0, true)t2.Get(0) = (foo, true)t1.Get(bar) = (1, true)t2.Get(1) = (bar, true)t1.Get(baz) = (2, true)t2.Get(2) = (baz, true)t1.Get(nope!) = (0, false)t2.Get(3) = (, false)

写完收工，我们已经在 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 提出了这个有趣的、彪悍的、出色的办理方案。

func hash(type A comparable)(a A) uintptr { var m interface{} = make(map[A]struct{}) hf := (mh)((unsafe.Pointer)(unsafe.Pointer(&m))).hf return hf(unsafe.Pointer(&a), 0)}func main { fmt.Println(hash(0)) fmt.Println(hash(false)) fmt.Println(hash(\"大众why hello there\"大众))}////////////////////////////// stolen from runtime //////////////////////////////// mh is an inlined combination of runtime._type and runtime.maptype.type mh struct { _ uintptr _ uintptr _ uint32 _ uint8 _ uint8 _ uint8 _ uint8 _ func(unsafe.Pointer, unsafe.Pointer) bool _ byte _ int32 _ int32 _ unsafe.Pointer _ unsafe.Pointer _ unsafe.Pointer hf func(unsafe.Pointer, uintptr) uintptr}