这篇文章基于我在日本东京 GoCon Spring 2018 上的演讲讨论了，Go 语言中的 map 是如何实现的。
什么是映射函数
要明白 map 是如何工作的的，我们需要先讨论一下 map 函数。一个 map 函数用以将一个值映射到另一个值。给定一个值，我们叫 key，它就会返回另外一个值，称为 value。
现在，map 还没什么用，除非我们放入一些数据。我们需要一个函数来将数据添加到 map 中
和一个函数从 map 中移除数据
在实现上还有一些有趣的点比如查询某个 key 当前在 map 中是否存在，但这已经超出了我们今天要讨论的范围。相反我们今天只专注于这几个点；插入，删除和如何将 key 映射到 value。
Go 中的 map 是一个 hashmap
Hashmap 是我要讨论的的 map 的一种特定实现，因为这也是 Go runtime 中所采用的实现方式。Hashmap 是一种经典的数据结构，提供了平均 O(1) 的查询时间复杂度，即使在最糟的情况下也有 O(n) 的复杂度。也就是说，正常情况下，执行 map 函数的时间是个常量。
这个常量的大小部分取决于 hashmap 的设计方式，而 map 存取时间从 O(1) 到 O(n) 的变化则取决于它的 hash 函数。
hash 函数
什么是 hash 函数 ？一个 hash 函数用以接收一个未知长度的 key 然后返回一个固定长度的 value。
这个 hash value 大多数情况下都是一个整数，原因我们后边会说到。
Hash 函数和映射函数是相似的。它们都接收一个 key 然后返回一个 value。然而 hash 函数的不同之处在于，它返回的 value 来源于 key，而不是关联于 key。
hash 函数的重要特点
很有必要讨论一下一个好的 hash 函数的特点，因为 hash 函数的质量决定了其 map 函数运行复杂度是否接近于 O(1)。
Hashmap 的使用方面有两个重要的特点。第一个是稳定性。Hash 函数必须是稳定的。给定相同的 key，你的 hash 函数必须返回相同的值。否则你无法查找到你放入 map 中的数据。
第二个特点是良好的分布。给定两个相类似的 key，结果应该是极其不同的。这很重要，因为有两点原因。第一，跟我们稍后会看到的一样，hashmap 中的 value 值应当均匀地分布于 buckets 之间，否则存取的复杂度不会是 O(1)。第二，由于用户一定程度上可以控制 hash 函数的输入，它们也就能控制 hash 函数的输出。这就会导致糟糕的分布，在某些语言中是 DDoS 攻击的一种方式。这项特点也被叫做 碰撞抵抗性（collision resistance）。
hashmap 的数据结构
关于 hashmap 的第二部分来说说数据是如何存储的。
经典的 hashmap 结构是一个 bucket 数组，其中的每项包含一个指针指向一个 key/value entry 数组。在当前例子中我们的 hashmap 中有 8 个 bucket（Go 语言即如此实现），并且每个 bucket 最多持有 8 个 key/value entry（同样也是 Go 语言的实现）。使用 2 的次方便于做位掩码和移位，而不必做昂贵的除法操作。
因为 entry 被添加到 map 中，假定有一个良好分布的 hash 函数，那么 buckets 大致会被均匀地填充。一旦 bucket 中的 entry 数量超过总数的某个百分比，也就是所说的 负载因子（load factor），那么 map 就会翻倍 bucket 的数量并重新分配原先的 entry。
记住这个数据结构。假设我们现在有一个 map 用以存储项目名和对应的 Github star 数目，那么我们要如何往 map 中插入一个 value 呢？