Go泛型实战：设计通用双向映射数据结构

本文深入探讨Go语言中的参数化多态（泛型）特性，通过实现一个通用的双向映射数据结构展示泛型在实际编程中的应用。文章详细介绍了API设计、实现细节以及NaN值处理等关键技术点。

Go参数化多态初探：设计通用双向映射

TL;DR 为了熟悉Go类型参数的最新设计草案，我编写了一个双向映射的泛型实现。你可以在这个playground中尝试。编辑（2022-04-03）：现在Go 1.18已经发布，我对这篇文章进行了更新。

Go即将迎来泛型

Go语言对参数化多态（俗称"泛型"）的支持正在积极开发中。上个月，Go团队发布了一篇博客文章，详细介绍了他们在这方面的进展。Johnny Boursiquot和Jaana B. Dogan对这一宣布反应热烈，这促使我阅读了更新的设计草案并亲自尝试了Go泛型！

为什么泛型很重要

在继续阅读本文之前，如果你不知道泛型是什么，或者对它们是否适合Go有疑问，我建议你阅读Ian Lance Taylor 2019年关于这个话题的文章。

撰写本文时（v1.14）的最新版Go不支持泛型。因此，追求最大灵活性的库作者通常别无选择，只能到处使用空接口（interface{}）（例如参见sync.Map）。不幸的是，这种设计选择的后果在客户端代码中会明显感受到。

空接口作为一种不加区分的抽象类型，它不提供关于具体类型可能表现出的行为的编译时保证。库的用户被迫在代码中大量使用类型断言，以操作隐藏在interface{}下面的具体类型。

泛型声称要解决这个问题：它们承诺在不牺牲可用性或类型安全性的情况下提供更灵活的代码。然而，关于向Go添加泛型的一些合理问题仍然存在。它会对编译速度产生不利影响吗？更重要的是，它会显著损害Go的简洁性目标吗？它会极大地复杂化Go代码的编写、阅读和使用吗？找到其中一些问题的答案是我写这篇文章的主要动机。

泛型设计草案的重要变化

我不会在这里深入细节；你可以阅读更新的设计草案以获取完整信息。以下是我从中获得的主要要点。

契约已移除

最重要的是，契约（contracts）已从设计草案中删除。得益于参数化多态专家（和lambda演算超级英雄）Phil Wadler及其合作者的见解，Go团队能够将契约统一到现有的接口概念下。我认为这是朝着正确方向迈出的重要一步，主要有两个原因：

  1. 契约的概念总是与接口的概念混淆地相似，但又不同。我记得这条模糊的界线给我造成了心理障碍：这可能解释了为什么我在最近更新之前没有深入研究泛型设计草案。
  2. 不再需要添加contract关键字，这原本需要在源代码级别破坏与Go 1.0的兼容性。当前的草案提案仍然需要对语言进行更改，但这些更改预计对大多数程序基本上没有影响。

新的comparable接口

另一个显著变化是添加了一个名为comparable的接口类型，作为语言中的预声明名称。你猜对了：comparable表示可以使用==和!=运算符进行比较的类型。

泛型的一个用例：双向映射

在阅读了更新的设计草案后，我在个人笔记中搜索了Go库和程序中泛型的有趣用例，一个通用双向映射的想法出现了。

根据维基百科，双向映射是

一种关联数据结构，其中键值对形成一一对应关系。因此，二元关系在每个方向上都是函数：每个值也可以映射到唯一的键。

换句话说，双向映射是一种类似于常规映射的抽象，但强制执行以下不变量：每个值都与且仅与一个键关联。

在我的一个副项目中，我最近遇到了双向映射的用例（如果你必须知道的话，是一个标签系统）。一个非泛型实现（字符串到字符串）解决了问题，但它让我想知道：

  • 泛型实现会是什么样子？
  • 向语言添加泛型如何改变Go包的API设计？
  • 使用这样的包会感觉多自然？

好奇心太强，我无法抗拒，于是开始设计一个通用双向映射的Go API。

通用双向映射的API设计

首先：在深入探讨可能的实现之前，让我概述一下我想要实现的目标。

bimap包及其导出的Bimap类型

目标是编写一个名为bimap的包，它导出一个（具体）通用双向映射类型，名为Bimap。此类型应接受两个可比较的类型参数，一个用于键，一个用于值。

零值应立即可用

Josh Bloch在API设计中的一个重要教训，它标志着我使用Java的日子，并一直伴随着我，那就是

[…] 不仅应该易于使用好的API，而且应该难以误用好的API。

设计一个类型，使其零值对应于有效状态，是Go中的一个重要原则，因为它有助于使类型的API难以误用。

工厂函数和方法

bimap应该为Bimap提供一个工厂函数；按照惯例，此类函数名为New。以下是Bimap的方法列表：

1
2
3
4
5
6
7

func (bi *Bimap[K, V]) Store(key K, value V)
func (bi *Bimap[K, V]) LoadValue(k K) (V, bool)
func (bi *Bimap[K, V]) LoadKey(v V) (K, bool)
func (bi *Bimap[K, V]) DeleteByKey(k K)
func (bi *Bimap[K, V]) DeleteByValue(v V)
func (bi *Bimap[K, V]) Size() int
func (bi *Bimap[K, V]) String() string

我为其中一些方法名称的冗长道歉，但我希望它们反映数据结构的对称性：键和值的角色确实可以互换而没有后果。请注意，所有这些方法都使用指针接收器：它们大多数需要改变Bimap的内部状态，并且不鼓励在单个类型中混合指针和值接收器。

Store在双向映射中存储一个键值对。可能有几种语义，但一个自然的设计选择是静默删除涉及提供的键或提供的值的预先存在的对。

LoadValue返回存储在双向映射中的键的值和一个布尔值，该布尔值指示是否找到了相关键；LoadKey是LoadValue的对称操作。

DeleteByKey和DeleteByValue分别删除与给定键或值关联的键值对。

Size返回双向映射中键值对的数量。

最后，Keys返回键的切片，Values返回值的切片，顺序不确定。

我的bimap包的API故意保持最小化。特别是，Bimap缺少Range方法；我将其留作练习。然而，为了可视化目的，我将使Bimap成为Stringer，具有简单的String实现。

一种可能的实现

双向映射的一个非常常见的实现涉及维护两个映射，一个从键到值，另一个从值到键；至少对于这种数据结构的参考实现来说，这是一个不错的起点。

因为Bimap将至少持有两个映射，所以其底层类型最自然的选择是结构体。所有这些设计决策引导我们得到Bimap的以下类型声明：

1
2
3
4

type Bimap[K, V comparable] struct {
	forward map[K]V
	inverse map[V]K
}

类型参数K和V被限制为可比较，在类型名称后的方括号中引入。为了封装目的，结构体完全不透明，即没有字段被导出：否则，bimap包的用户将能够直接弄乱Bimap的内部结构并破坏其不变量。

编写bimap包的其余部分相对简单：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62

func (bi *Bimap[K, V]) Store(key K, value V) {
	k, exists := bi.inverse[value]
	if exists { // value已经与k关联
		delete(bi.forward, k)
	}
	v, exists := bi.forward[key]
	if exists { // key已经与v关联
		delete(bi.inverse, v)
	}
	if bi.forward == nil { // bi尚未初始化
		bi.forward = make(map[K]V)
		bi.inverse = make(map[V]K)
	}
	bi.forward[key] = value
	bi.inverse[value] = key
}

func (bi *Bimap[K, V]) LoadValue(k K) (V, bool) {
	v, ok := bi.forward[k]
	return v, ok
}

func (bi *Bimap[K, V]) LoadKey(v V) (K, bool) {
	k, ok := bi.inverse[v]
	return k, ok
}

func (bi *Bimap[K, V]) DeleteByKey(k K) {
	v := bi.forward[k]
	delete(bi.forward, k)
	delete(bi.inverse, v)
}

func (bi *Bimap[K, V]) DeleteByValue(v V) {
	k := bi.inverse[v]
	delete(bi.inverse, v)
	delete(bi.forward, k)
}

func (bi *Bimap[K, V]) Size() int {
	return len(bi.forward)
}

func (bi *Bimap[K, V]) Keys() []K {
	var keys []K
	for k := range bi.forward {
		keys = append(keys, k)
	}
	return keys
}

func (bi *Bimap[K, V]) Values() []V {
	var values []V
	for v := range bi.inverse {
		values = append(values, v)
	}
	return values
}

func (bi *Bimap[K, V]) String() string {
	return fmt.Sprintf("Bi%v", bi.forward)
}

编辑（2020-07-23）：Store包含一个错误；参见附录。

请注意，根据当前的设计草案，泛型接收器必须指定类型所需的所有类型参数，即使其中一些类型参数未在方法体中使用。例如，将Size声明如下是非法的：

1

func (bi *Bimap[_, _]) Size() int

能够在这种情况下使用空白标识符当然很好，但我不知道这是否在计划中。我只是在这里推测，但也许在编译器中实现此功能会使单态化复杂化…

我的bimap包的完整源代码以及测试套件可在我的jub0bs/bimap GitHub仓库中找到。

使用bimap包

一旦为Bimap指定了具体类型（在设计草案中称为实例化的过程），客户端代码的其余部分对我来说感觉就像泛型前的Go代码一样自然：

1
2
3
4
5

bi := bimap.New[int, string]()
bi.Store(0, "Planets&Stars")
bi.Store(1, "Chemistry")
bi.Store(0, "Astronomy")
bi.DeleteByValue("Chemistry")

你觉得怎么样？

结论

双向映射可以说是Go中泛型的一个非常简单的用例，但它让你对泛型代码的样子有所了解，如果设计草案被接受且几乎没有修改的话。

泛型的伟大之处在于，这个bimap包只需要编写一次，并且可以用于键和值的任何（可比较）具体类型组合。作为库作者，我发现这很解放。

此外，我怀疑泛型代码用户所需的额外认知负担是否会令人望而却步。泛型在其他语言中可能被合理担心，但缺乏继承使得Go泛型相对更容易理解。就我而言：Go泛型必胜！

附录（2020/07/23）

不幸的是，正如Martin Möhrmann在Gophers Slack工作区向我指出的那样，NaN（非数字）会带来问题，并揭示了我原始Bimap实现中的一个微妙错误。

Bimap类型使用两个后备映射，而映射对于相等性不是自反的键（即k使得k == k评估为false）表现出相当奇怪的行为。对于NaN以及任何包含NaN的复合类型或定义类型的值，相等性不是自反的。

因为它们的类型是可比较的，所以这些值可以合法地作为键添加到映射中，但它们不能被加载或删除；在这个playground中自己检查一下。

因此，在存储此类值后，我原始Bimap实现的不变量可能会被破坏；在这个playground中查看示例。

乍一看，这个未预见到的困难似乎无法逃避…然而，一个简单的出路，除了改变Bimap的内部表示之外，是禁止存储相等性不是自反的键和值。

我可以定义一个通用谓词来检查其参数的相等性是否是自反的，

1
2
3

func isEqualityReflexive[T comparable](t T) bool {
	return t == t
}

并在将键值对添加到Bimap之前检查传递给Store方法的键和值是否满足此谓词。

与其静默拒绝不允许的值，不如修改Store以返回操作是否成功：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

// Store创建一个键值对并返回操作是否成功。预先存在的键值对（如果有）
// 涉及给定键和/或给定值的键值对将被静默
// 从Bimap中删除。不允许相等性不是自反的键和值。
func (bi *Bimap[K, V]) Store(key K, value V) bool {
	if !isEqualityReflexive(key) || !isEqualityReflexive(value) {
		return false
	}
	k, exists := bi.inverse[value]
	if exists { // value已经与k关联
		delete(bi.forward, k)
	}
	v, exists := bi.forward[key]
	if exists { // key已经与v关联
		delete(bi.inverse, v)
	}
	if bi.forward == nil { // bi尚未初始化
		bi.forward = make(map[K]V)
		bi.inverse = make(map[V]K)
	}
	bi.forward[key] = value
	bi.inverse[value] = key
	return true
}

请注意，只有当键类型或值类型或两者都包含此类不允许的值时，此布尔结果才有用；对于所有其他类型，你可以安全地忽略该结果。

comments powered by Disqus
© 2020 - 2025 qife
使用 Hugo 构建
主题 Stack 由 Jimmy 设计
本站总访问量次 本站访客数人次