Go: 通过例子学习 Map 的设计 — Part I

ℹ️ 本文是三篇系列文章中的第一篇。每篇文章讲涵盖map中的不同部分。建议您按顺序阅读。

Go提供的内置类型实现了一个哈希表。 在本文中,我们将探讨此哈希表不同部分的实现:桶(存储键/值对的结构),哈希(这些键/值对的索引)和负载因子(判断 map 是否应该扩容的指标)。

Go将键/值对存储在桶列表中,其中每个桶将容纳8对,而当map容量不足时,哈希桶的数量将翻倍。 这是具有4个桶的map的粗略示意图:

我们将在下一篇文章中看到桶中的键/值对是如何存储的。 如果map再次增长,则桶数将翻倍至8,然后是16,依此类推。

当一个键/值对进入map时,它将根据从键计算出的哈希值将其分配到桶中。

哈希

当一个键/值对被分配给map时,Go将基于这个键生成一个哈希值。

让我们举一个插入键/值对的示例。生成的哈希值可能是。此值将应用于位操作,掩码相较于桶数减1。在我们使用4个桶的示例中,掩码3,位操作如下:

哈希值不仅用于桶中值的分配,还参与其他的操作。每个桶都将其哈希值的首字节存储在一个内部数组中,这使得 Go 可以对键进行索引,并跟踪桶中的空槽。让我们看一下哈希在二进制表示下例子:

由于桶中有一个名为top hash的内部表,Go将能够在数据访问期间使用它们,并将其与请求的键的哈希值进行比较。
根据我们在程序中对 map 的使用,Go 需要对 map 进行扩容,以便管理更多的键/值对。

Map 扩容

如果桶收到要存储的键/值对,它将存储在桶中的8个可用插槽中。 如果它们都不可用,那么将创建一个溢出桶并将其链接到当前桶:

这里溢出属性表明了桶的内部结构。然而增加溢出桶会降低map的性能。为了解决这个问题,Go将会分配新桶(当前桶数的两倍),在新旧桶之间保持链接,并逐步迁移桶。实际上,在进行了新分配后,每个参与过写操作的桶,如果操作还未完成,都将被迁移。被迁移的桶中的所有键/值对都将被重新分配到新桶中,这意味着,先前同一个桶中存储在一起的键/值对,现在可能被分配到不同的桶中。

Go 使用负载因子来判断何时开始分配新桶并迁移旧桶。

Loading factor

Go选择6.5作为map的负载因子。你可以在代码中发现负载因子的相关研究:

如果每个桶中的值的平均数量超过6.5,则map将增长。 正如我们在研究中看到的那样,由于基于键的哈希值的分布无法平均分布,因此选择接近8的值可能会导致大量的溢出桶。

⏭  这个系列的下一篇文章,将会讲解 map 的内部实现。

编译自https://medium.com/a-journey-with-go/go-map-design-by-example-part-i-3f78a064a352


欢迎订阅我的公众号,文章更新早知道
张贴在Go标签:

版权声明: 本文为【陈思敏捷】的原创文章。
原文链接:【https://www.chenjie.info/2511】。原文标题:【Go: 通过例子学习 Map 的设计 — Part I】。文章转载请联系作者。


发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据