Go Generics草稿设计：构建哈希表·Matt Layher

2018年，我在Goas中实现了一个玩具哈希表，快速刷新了Go地图等数据类型的工作原理，该实现专门使用映射到字符串值的字符串键。

两年后，也就是2020年6月，Go团队发布了一篇题为“泛型的下一步”(The Next Step For Generics)的博客文章，提供了一个基于扩展Go现有接口的更新的泛型设计草案，而不是添加新的概念，如“合同”。如果您还没有，我强烈建议您至少浏览一下新的设计草案文档。我不是专家，只能根据我有限的设计经验和时间发言。

这个博客将描述我将我的玩具哈希表移植到新的泛型草案设计中所学到的课程。如果您想跳过介绍并查看泛型代码，请随意跳到“泛型哈希表”。

表类型是包的基础。它使用切片在内部存储键/值字符串对，其中切片内的散列表桶数由整数m决定：

m越小意味着创建的存储桶越少，但是表中存储的每个键必须与其他键共享存储桶的可能性更高，从而降低了查找速度。

m越大意味着将创建更多的存储桶，因此表中存储的每个键必须与其他键共享存储桶的可能性较低，从而加快了查找速度。

//包哈希表实现了字符串键/值对的基本哈希表。包哈希表//表是一个基本的哈希表。type Table struct{m int table[][]kv}//KV将键/值数据存储在表中。类型KV struct{key，value string}//New创建一个包含m个内部存储桶的表。Func New(M Int)*Table{return&；table{m：m，table：make([][]KV，m)，}}。

GET：确定哈希表中是否存在键，返回值(如果找到)和一个布尔值，该布尔值指示值是否存在

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

这两个操作都需要散列函数，该函数可以接受输入字符串并返回一个整数，指示键值可能位于的存储桶。

//hash选择用于存储带有键的字符串的哈希表索引。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确定哈希表中是否存在key，返回其值和//是否找到key。func(t*Table)get(Key String)(string，bool){//哈希键确定此键的值属于哪个存储桶。i：=t.hash(Key)for j，kv：=range t.table[i]{if key==kv.Key{//找到匹配项，返回！return t.table[i][j].value，true}}//不匹配。返回"；"；，false}。

Table.Get的实现对输入键进行散列处理，以确定哪个存储桶用于存储键的值。一旦确定了存储桶，它就会迭代该存储桶中的所有键/值对：

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

//Insert将新的键/值对插入到表中。func(t*Table)INSERT(key，value string){i：=t.hash(Key)for j，kv：=range t.table[i]{if key==kv.Key{//覆盖相同键的先前值。t.table[i][j].value=值返回}}//将新值添加到表中。t.table[i]=append(t.table[i]，KV{key：key，value：value，})}

Insert还必须对输入键进行散列处理，以确定应该使用哪个存储桶来插入键/值对。当迭代存储桶中的键/值对时，我们可能会发现匹配的键已经存在：

如果输入键与该存储桶中的键匹配，则用输入值覆盖键的值。

如果不匹配，则将新条目附加到存储桶的键/值对切片。

就这样!。我们已经创建了一个非常基本的哈希表，可用于处理键/值字符串对。

//8桶应该足够了。t：=hashtable.New(8)t.Insert("；foo"；，"；bar"；)t.Insert("；baz"；，"；qux"；)v，ok：=t.Get("；foo"；)fmt.Printf("；t.Get(%q)=(%q，%t)"；，"；Fot。，v，OK)//t.Get("；foo"；)=("；bar"；，true)。

我们的目标是利用现有的哈希表代码，并使其与任意键/值对类型一起工作。但是我们有一个约束：我们的哈希表中的键必须与预先声明的类型约束COMPARIBLE匹配，这样我们就可以检查是否相等。

在我的设计中，我决定强制键和值类型都是可比较的，这样我就可以使用两个哈希表作为索引并使用翻转的键/值类型进行反向索引来构建一个简单的演示。

//包哈希表实现了泛型键/值对的基本哈希表。包哈希表//表是基本的泛型哈希表。type Table(类型K，V可比)struct{//hash是一个函数，它可以用T.m散列类型K的键。hash func(key K，m int)int m int table[][]KV}//A KV将通用键/值数据存储在表中。type KV(type K，V可比较)struct{key K value V}//New创建一个具有m个内部存储桶的表，该表使用指定的散列函数//用于输入类型K。func New(type K，V比较)(m int，hash func(K，int)int)*Table(K，V){return&；Table(K，V){hash：hash，m：m，//请注意"；KV(K，V)"；周围的圆括号；这些是必需的！表：make([][](KV(K，V))，m)，}}

任何需要泛型类型的地方都需要新的类型参数列表，因此这些顶级类型和函数中的每一个都必须具有K和V的类型参数列表，这两个类型和函数也必须具有可比性。

注意，散列函数func(K，int)int现在是传递给New的第二个参数。这是必要的，因为我们必须知道如何散列任何给定的泛型类型。我本可以使用Hash()intConstraint或类似的方法创建一个新接口，但是我希望我的哈希表可以使用内置的Gotype，如string和int，您不能在这些类型上定义方法。

在创建Table.table时，我花了一些时间才弄清楚make()调用的正确括号用法。我最初尝试使用make([][]KV(K，V))，它不能使用添加的类型参数。

//GET确定哈希表中是否存在key，返回其值和//是否找到key。func(t*Table(K，V))get(Key K)(V，bool){//哈希键确定此键的值属于哪个存储桶。//传递t.m以便t.hash可以执行必要的操作"；hash%T.m"；。i：=t.hash(key，T.m)for j，kv：=range t.table[i]{如果key==kv.Key{//找到匹配项，返回！return t.table[i][j].value，true}}//不匹配。为泛型类型//返回零值的最简单方法是声明一个临时变量，如下所示。var零V返回零，FALSE}。

泛型类型上定义的方法还必须在其接收器中声明关联的泛型TypeParameters。GET现在可以接受任何类型K，并返回任何类型V和bool，以指示是否找到该值。

除了修改过的方法接收器和一些K和V类型之外，这个看起来很像典型的围棋代码，这是很棒的！

这里的一个稍微棘手的问题是处理泛型类型的零值。链接的问题建议像我们在这里所做的那样，声明var 0V，但也许将来会有一个更容易的选择来实现这一点。我个人希望看到return_、false或similar作为泛型GO和非泛型GO的选项。

//Insert将新的键/值对插入到表中。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{//覆盖相同键的先前值。t.table[i][j].value=值返回}}//将新值添加到表中。t.table[i]=append(t.table[i]，KV(K，V){key：key，value：value，})}

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

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

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{//足够好！返回密钥%m})。

在调用泛型构造函数New时，我们为泛型类型K和V指定类型参数。例如，T1是一个表示K=String和V=int的Table(String，int)。t2正好相反：table(int，string)，因为int和string都符合类型约束COMPARLISE，所以它可以很好地工作。

为了散列我们的泛型类型，我们必须提供一个散列函数，该函数可以对K和T.m进行操作以产生int输出。对于T1，我们重用原始示例中的散列/FNV散列。对于T2，模运算对于我们的演示似乎足够了。

我知道在大多数情况下，Go编译器应该能够在hashtable.New这样的调用点推断出K和V等泛型类型的正确类型，但我可能会继续以显式的方式编写它们一段时间，以适应设计。

现在我们已经创建了索引和反向索引哈希表，让我们填充它们：

字符串：=[]string{"；foo"；，"；bar"；，"；baz"；}for i，s：=range str{t1.插入(s，i)t2.插入(i，s)}

T1中的每个键/值对将被镜像为T2中的值/键。最后，我们可以迭代已知的字符串和索引(以及一个永远找不到的附加值)，以实际显示我们的泛型代码：

对于i，s：=range append(str，"；noope！"；){v1，ok1：=t1Get(S)log.Printf("；t1.Get(%v)=(%v，%v)"；，s，v1，OK1)v2，ok2：=t2Get(I)log.Printf("；t2Get(%v)=(%v，%v。

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博客和新的泛型设计草案文档。

如果你有问题或意见，请随时在Twitteror@mdlayher上联系地鼠Slack。我很可能在不久的将来也会在Twitch上直播一些围棋通用内容！

在实现我的通用散列表时，我在#Performance on Gophers Slake中与一些人讨论了如何才能访问内置Go地图使用的运行时“通用”散列功能。

函数散列(类型A可比)(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("；为什么你好"；)}/mh是运行时._type和runtime.maptype的内联组合。键入mh struct{_uintptr_uintptr_uint32_uint8_func(unsafe.Pointer，unsafe.Pointer)bool_*byte_int32_int32_unsafe.Pointer_unsafe.Pointer_unSafe.Pointer HF函数(unsafe.Pointer，uintptr)uintptr}。

这段代码滥用了Go接口实际上是运行类型数据的元组和指向类型的指针这一事实。通过访问该指针并使用unsafe将其转换为映射的运行时表示形式(它有一个hashingfunction字段)，我们可以创建一个在我们自己的代码中使用的泛型散列函数！