泛型

Go泛型

案例：使用泛型实现Hash表

我们的目标是采用现有的哈希表代码，并使它与任意键/值对类型一起使用。但是我们确实有一个约束：哈希表中的键必须匹配可比较的预先声明的类型约束，因此我们可以检查是否相等。

// 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的类型必须具有可比性，并且可以使用任何类型对于V，如 interface{} 所示。在编写此代码时，我学到了一些棘手的东西：

请注意，哈希函数func(K，int)int现在是传递给New的第二个参数。这是必需的，因为我们必须知道如何哈希任何给定的泛型类型。我本可以使用Hash() int约束或类似约束创建一个新接口，但是我希望我的哈希表可以与内置Go类型（例如string和int）一起使用，而不能在上面定义方法。
在创建Table.table时，花了一些时间弄清楚make()调用的正确括号用法。我最初的尝试是使用 make（[] [] kv（K，V）），但无法使用添加的类型参数。

// 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和布尔值以指示是否找到了该值。除了修改后的方法接收器和一些K和V类型之外，这看起来很像典型的Go代码，这太棒了！这里一个棘手的问题是处理通用类型的零值。关联的问题建议通过声明var零V来像我们在此处所做的那样进行操作，但是也许将来会有更简便的选择。我个人希望将 return \_, false 或类似值作为通用和非通用Go的选项。

// 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 {}结构文字声明为kv（K，V）{}

这就是全部！现在，我们有了一个通用的哈希表类型，它可以接受实现可比较类型约束的任何键和值。

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 is aTable(string, int)意思是 K = string 以及V = int.t2是相反的:Table(int, string).因为两者 int 以及 string 匹配类型约束comparable,这很好。为了哈希我们的泛型类型，我们必须提供可以在 K 以及 t.m 产生一个intoutput. Fort1,我们重复使用 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)
}

// Outputs
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)

最近更新于0001-01-01