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

本文是三篇系列文章中的第一篇。每篇文章都将涵盖 map 的不同部分。我建议你按顺序阅读。

Go 提供的内置类型 map 是使用哈希表^[1] 实现的。在本文中，我们将探讨这个哈希表的不同部分的具体实现：桶（存储键值对的数据结构），哈希（键值对的索引），负载因子（判断 map 是否应该扩容的指标）。

本文是 Go语言中文网组织的 GCTT 翻译，发布在 Go语言中文网公众号，转载请联系我们授权。

桶

Go 将键值对存储在桶的列表中，每个桶容纳 8 个键值对，当 map 的容量耗尽，哈希桶的数量将会翻倍。下面是持有 4 个桶的 map 的粗略示图：

在下一篇文章中，我们将看到这些键值对是如何在桶里存储的。如果 map 再一次扩容，桶的数量将会翻倍，依次增加到 8，16，等等。

当一个键值对存入 map，它将根据键计算出的哈希值，被分配到一个桶里。

哈希

当一个键值对被存放到 map 中，Go 会根据它的键生成哈希值。

让我们以键值对 "foo" = 1 的插入作为例子。生成的哈希值可能是 15491954468309821754。该值将应用于位操作，掩码对应于桶的数量减 1。在我们的 4 个桶的例子中，掩码是 3，位操作如下：

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

多亏了桶内部被称为 top hash 的表，Go 可以在数据访问期间使用它们与请求键的哈希值进行比较。

根据我们在程序中对 map 的使用，Go 需要对 map 进行扩容，以便管理更多的键值对。

Map 扩容

在存储键值对时，桶会将它存储在 8 个可用的插槽中。如果这些插槽全部不可用，Go 会创建一个溢出桶，并与当前桶连接。

这个 overflow 属性表明了桶的内部结构。然而，增加溢出桶会降低 map 的性能。作为弥补，Go 将会分配新的桶（当前桶的数量的两倍），保存一个旧桶和新桶之间的连接，逐步将旧桶迁移到新桶中。实际上，在这次新的分配之后，每个参与过写操作的桶，如果操作还未完成，都将被迁移。被迁移的桶中的所有键值对都将被重新分配到新桶中，这意味着，先前同一个桶中存储在一起的键值对，现在可能被分配到不同的桶中。

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

负载因子

Go 在 map 中使用 6.5 作为负载因子。你可以在代码中看到与负载因子相关的研究：

// Picking loadFactor: too large and we have lots of overflow
// buckets, too small and we waste a lot of space. I wrote
// a simple program to check some stats for different loads:
// (64-bit, 8 byte keys and values)
//  loadFactor    %overflow  bytes/entry     hitprobe    missprobe
//        4.00         2.13        20.77         3.00         4.00
//        4.50         4.05        17.30         3.25         4.50
//        5.00         6.85        14.77         3.50         5.00
//        5.50        10.55        12.94         3.75         5.50
//        6.00        15.27        11.67         4.00         6.00
//        6.50        20.90        10.79         4.25         6.50
//        7.00        27.14        10.15         4.50         7.00
//        7.50        34.03         9.73         4.75         7.50
//        8.00        41.10         9.40         5.00         8.00
//
// %overflow   = percentage of buckets which have an overflow bucket
// bytes/entry = overhead bytes used per key/value pair
// hitprobe    = # of entries to check when looking up a present key
// missprobe   = # of entries to check when looking up an absent key

如果桶中键值对的平均容量超过 6.5，map 将会扩容。考虑到基于键的哈希值的分配并不均匀，正如我们在以上研究中看到的，使用 8 作为负载因子会导致大量的溢出桶。

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

via: https://medium.com/@blanchon.vincent/go-map-design-by-example-part-i-3f78a064a352

作者：blanchon.vincent^[2]译者：DoubleLuck^[3]校对：polaris1119^[4]

本文由 GCTT^[5] 原创编译，Go 中文网^[6] 荣誉推出，发布在 Go语言中文网公众号，转载请联系我们授权。

参考资料