GO 中哈希表的实现

什么是哈希表

哈希表是键值对映射的数据结构，可以通过键对数据进行存取，其中实现的关键是哈希函数和哈希冲突。

哈希函数提供了对键的散列编码，可以将存取的数据分散到底层的数据空间中，所以哈希函数的均匀分布可以提高哈希表的读写性能。

哈希冲突的结果可以使用开放寻址法和拉链法来解决。

源码位置：go/map.go

数据结构

哈希表使用 runtime.hmap 表示，其中每个存储桶使用 runtime.bmap 表示。

type hmap struct {
  count     int
  flags     uint8
  B         uint8
  noverflow uint16
  hash0     uint32

  buckets    unsafe.Pointer
  oldbuckets unsafe.Pointer
  nevacuate  uintptr

  extra *mapextra
}

type mapextra struct {
  overflow    *[]*bmap // 当前持有的初始化溢出桶
  oldoverflow *[]*bmap // 扩容前的初始化溢出桶
  nextOverflow *bmap   // 下一个待分配的溢出桶
}

1. count 表示当前哈希表中的元素数量；
2. B 表示当前哈希表持有的 buckets 数量，但是因为哈希表中桶扩容为翻倍扩容，所以该字段会存储对数，也就是 len(buckets) == 2^B；
3. noverflow 用于记录当前哈希表的溢出桶数量。
4. hash0 是哈希的种子，它能为哈希函数的结果引入随机性，这个值在创建哈希表时确定，并在调用哈希函数时作为参数传入；
5. buckets 是当前桶。
6. oldbuckets 是哈希在扩容时用于保存之前 buckets 的字段。
7. nevacuate 表示当前已分流桶的数量。
8. mapextra 用于存储溢出桶的相关数据，溢出桶是用于解决频繁扩容的有效方法。

type bmap struct {
    topbits  [8]uint8
    keys     [8]keytype
    values   [8]valuetype
    pad      uintptr
    overflow uintptr
}

原始的 bmap 只有 topbits 字段，该字段为哈希值的高八位，用于加速键值对的访问。

其他字段在编译时进行推导，该结构为虚拟结构，实际访问则通过计算内存地址的方式访问。

溢出桶

由上面可知，哈希表的底层使用的是桶存储数据，每个桶最多可以存储 8 个键值对，其中根据需要可能会多创建不定数量的溢出桶用来承载桶溢出后的数据，溢出桶会添加到桶的 overflow 字段。

桶数量确定原则：

• 哈希表未指定元素数量是默认为 0，然后根据最大负载因子为 6.5、每个存储桶中 8 个元素来确定最小的 B 大小。

溢出桶创建规则：

• 当桶的数量小于 2**4 时，由于数据较少、使用溢出桶的可能性较低，会省略创建的过程以减少额外开销；
• 当桶的数量多于 2**4 时，会额外创建 2**(B-4) 个溢出桶；

在创建时正常桶和溢出桶处于相邻的地址空间，只有在初始化的溢出桶使用完后才会通过 runtime.newobject 创建新的溢出桶。

数据操作

访问

哈希表的访问步骤如下：

1. 计算哈希值。
2. 获取存储数据的桶。
3. 依次对比 tophash 与哈希值的高八位，如果相同则对比对应的键值，相同即可返回，否则继续向下寻找，如果当前桶内数据查找完后继续查找溢出桶，直到找到键值对或者数据不存在。

因为哈希表的扩容不具备原子性，所以在扩容过程中进行访问的过程在扩容部分介绍。

写入/修改

写入与修改在相同过程中实现，步骤如下：

1. 计算哈希值
2. 获取存储数据的桶
3. 依次对比 tophash 与哈希值的高八位，如果相同则对比对应的键值，相同即可将新数据写入，否则继续向下寻找，如果当前桶内数据查找完后继续查找溢出桶，直到找到键值对或者数据不存在，当数据不存在时会将哈希高八位写入到 tophash 键值对写入对应位置，如果最后的桶已满，则获取新的溢出桶插入到当前桶之后并写入数据。

在扩容期间进行的写入与修改过程将在扩容部分介绍。

删除

删除操作即删除对应的 tophash 和键值对，但并不会整理内存和释放多余的溢出桶，此部分在扩容部分完成。

扩容机制

发生条件

1. 装载因子超过 6.5。
2. 哈希表使用了过多的溢出桶。

扩容分类

1. 等量扩容

   等量扩容的原因是使用了过多的溢出桶，扩容方式是创建一组相同数量的桶，随后将原有的桶数组设置到 oldbuckets 上并将新的空桶设置到 buckets 上，溢出桶也使用了相同的逻辑更新。

2. 翻倍扩容

   翻倍扩容的原因是装载因子已经超过了 6.5，扩容方式是创建一组 2 倍数量的桶和相应的溢出桶，随后将原有的桶数组设置到 oldbuckets 上并将新的空桶设置到 buckets 上，溢出桶也使用了相同的逻辑更新。

增量扩容

在创建新桶后并没有对原有数据进行分流，数据的分流以桶为单位，分流时机为每次写入操作前和删除操作前。

分流方式为从旧桶中依次读取数据，计算哈希值和新桶索引，并将数据写入到新桶中，写入方式和上文相同。之后只保留旧桶的 tophash 用于标记该桶已分流，其他内存则进行回收。如果所有的桶都进行了分流则置 oldbuckets 和nevacuate 为空，以回收 tophash 占用的空间。

在增删改前如果旧桶数据已分流则直接对新桶进行操作，如果旧桶未分流则分流后对新桶进行操作。读操作前如果旧桶未分流则读取旧桶，否则读取新桶。

参考

理解 Golang 哈希表 Map 的原理 | Go 语言设计与实现 (draveness.me)

Go 语言如何进行类型检查 | Go 语言设计与实现 (draveness.me)

Golang 数据结构详解之哈希表 - 知乎 (zhihu.com)