hash 表在 go 语言中的实现

哈希表，是根据 key 值直接进行数据访问的数据结构。即通过一个 hash 函数，将 key 转换成换成数组的索引值，然后将 value 存储在该数组的索引位置。如下图：

在 hash 表的结构设计中一般有 3 个关键问题需要解决：

• hash 冲突。即不同的 key 通过 hash 函数，会生成相同的 hash 值，即映射到相同的数组索引中。
• 空间浪费。即如果两个 key 值，hash 之后，生成的索引值差距较大，就会对数组空间产生浪费。
• 扩容问题。即当现有的数组空间被填充满时，如何存储更多的键值。

hash 冲突的解决一般采用拉链法（当然还有开放地址法等）。即当有两个不同的 key，经过 hash 函数，被 hash 到同一个位置的时候，不直接存储在该索引下，而是将该值加到链表中，以免覆盖第一个具有相同 hash 的 key 值。如下图，假设 a 和 b 的 hash 值相同。

对于第二个问题，在 go 中是通过位操作来解决的。即将 key 转换成 hash 值后，并不直接用 hash 作为索引，而是用 hash 和一个掩码值（一般是和底层数组个数或其相关的一个值）进行取模或位操作后得到对应数组的索引值。

第三个问题是涉及到空间增长和数据迁移，即重新分配更大的空间，将原有的 key 重新 hash 到新的空间的索引位置上。

本文主要介绍在 go 中实现 hash 表的底层数据结构以及 hash 冲突的解决。

map在Go中的数据结构

首先，整体来看下 go 中整体 map 的数据结构。如下图：

如上图，我们得知在 map 的数据结构中主要包含 hmap，bmap 两个结构体。

hmap 结构体

在 go 中，我们初始化或创建一个 map 时，实际上是创建了一个 hmap 结构体。hmap 的完整数据结构如下：

type hmap struct {
  count      int //map中的元素个数
  flags      uint8
  B          uint8 //log_2的对数，即buckets的个数为2^B次方  
  noverflow  uint16 
  hash0      uint32 //hash种子
  buckets    unsafe.Pointer //bucket数组指针
  oldbuckets unsafe.Pointer //
  nevacuate  uintptr
  extra      *mapextra //溢出的buckets
}

例如我们用如下语句创建一个 map 变量：

//创建一个容量为10的map
m := make(map[string]int, 16)

创建的 hmap 结构如下：

在 hmap 结构中，有以下几个重要的字段：

• B ：log_2 的对数，即 bucket 的个数=2^B 次方
• hash0：随机数的种子。Go 运行时环境避免 hash 冲突使用。
• buckets：底层的 buckets 数组。
• extra：溢出的 buckets 数组。

数据结构中的 B 字段及其作用

根据上面的数据结构，我们可知，bucket 的个数=2^B 次方。那我们为什么需要这个 B 值呢？*因为我们需要用 B 值和 hash 值经过一定的运算后，得到 bucket 数组范围内的索引 index *。

我们在用 map 的时候，key 是一个字符串，经过 hash 函数后转换成数组的索引。但这个哈希后的数字不一定在 buckets 的数组范围内。比如，我们的 buckets 数组个数是 8 个，一个 key 经过哈希函数转换成的哈希值是 1378，那这个哈希值就不能直接作为 buckets 数组的索引来存储该 value。而且，我们也不能直接扩展该数组的空间来存储该值，这样将会浪费太多的空间。

所以，我们需要 B 和 hash 进行按位与操作，以此将 hash 值落到 bucket 数组的范围之内。在 go 中代码实现如下：

index := hash & (1 << B - 1)

buckets

buckets 是 map 结构中的底层存储结构，buckets 本质上一个 bmap 类型的数组，即每个 bucket 指向一个 bmap 结构体。数组大小由 B 字段值决定。

type bmap struct {
  tophash [8]uint8 //容量为8的数组，存储hash值的高位
  keys [8]keyType //该字段是在运行时阶段自动加入的，在源码中并没有。
  values [8]valueType //该字段是在运行时阶段自动加入的，在源码中并没有。
}

在 bmap 结构体中，tophash 是一个固定容量的数组。值得注意的是 keys 和 values 的存储结构。key-value 的存储并不是我们常见的 key-value/key-value 存储，而是以 key0/key1/key2/.../key7/value0/value1/.../value7 格式存储的。即先存 8 个 key，再存 8 个 value。这主要是考虑在内存对齐方面，可以避免浪费内存。

赋值操作

map 的赋值操作如下：

m['apple'] = 'mac'

赋值操作的目标，是将 apple 经过 hash 之后，找到对应的 bucket，并存储到 bmap 结构体中。

计算步骤如下：1、根据 key 生成 hash 值 2、根据 hash 和 B 计算 bucket 的索引 3、根据 bucket 索引和 bucketsize 计算得到 buckets 数组的起始地址 4、计算 hash 的高位值 top 5、在 tophash 数组中依次该 tophash 值是否存在，如果存在，并且 key 和存储的 key 相等，则更新该 key/value。如果不存在，则从 tophash 数组查找第一个空位置，保存该 tophash 和 key/value

场景一：tophash 数组未满，且 k 值不存在时，则查找空闲空间，直接赋值

场景二：tophash 数组未满，且 k 值已经存在，则更新该 k

场景三：tophash 数组已满，且 k 值不在当前的 bucket 的 tophash 中，则从 bmap 结构体中的 buoverflowt 中查找，并做更新或新增

hash 冲突

由上面的赋值操作可知，当遇到 hash 冲突的时候，go 的解决方法是先在 tophash 的数组中查找空闲的位置，如果有空闲的位置则存入。如果没有空闲位置，则在 bmap 的 bucket 指针的 tophash 中继续查，依次循环，直到找不等于该 key 的空闲位置，依次循环，直到从 tophash 中找到一个空闲位置为止。

小结

1、Go中map的底层实现是hash表，主要由两个数据结构实现：hmap和bmap。

2、hmap中B的作用主要用来计算buckets数组的个数的。

3、buckets数组每个元素存储的bmap的结构体。在bmap结构中，每个bmap中至多存储8个key-value对。为了提高内存的利用率，key-value的存储格式是key0/key1/...key8/value0/value1/.../value8格式，而非key0/value0/key2/value2形式。

4、Go中的hash冲突采用拉链式方案解决。