Go 系列数据结构-map

map数据结构

Golang 的 map 使用哈希表作为底层实现，一个哈希表里可以有多个哈希表节点，也即bucket，而每个bucket就保存了map中的一个或一组键值对。

map数据结构由 runtime/map.go/hmap 定义:

type hmap struct { 
  count int // 当前保存的元素个数 
  ... 
  B uint8 // 指示bucket数组的大小 
  ... 
  buckets unsafe.Pointer // bucket数组指针，数组的大小为2^B 
  ... 
}

下图展示一个拥有 4 个 bucket 的 map： map

本例中, hmap.B=2 ，而 hmap.buckets 长度是 2^B为 4. 元素经过哈希运算后会落到某个bucket中进行存储。查找过程类似。

bucket 很多时候被翻译为桶，所谓的哈希桶实际上就是bucket。

bucket数据结构

bucket 数据结构由 runtime/map.go/bmap 定义：

type bmap struct { 
  tophash [8]uint8 //存储哈希值的高8位
  data byte[1] //key value数据:key/key/key/.../value/value/value... 
  overflow *bmap //溢出bucket的地址 
}

每个bucket可以存储8个键值对：

tophash是个长度为8的数组，哈希值相同的键（准确的说是哈希值低位相同的键）存入当前bucket时会将哈希值的高位存储在该数组中，以方便后续匹配。
data 区存放的是 key-value 数据，存放顺序是 key/key/key/…value/value/value，如此存放是为了节省字节对齐带来的空间浪费。
overflow 指针指向的是下一个 bucket，据此将所有冲突的键连接起来。

注意：上述中 data 和 overflow 并不是在结构体中显示定义的，而是直接通过指针运算进行访问的。

下图展示 bucket 存放 8 个 key-value 对： map

哈希冲突

当有两个或以上数量的键被哈希到了同一个bucket时，我们称这些键发生了冲突。Go使用链地址法来解决键冲突。由于每个bucket可以存放8个键值对，所以同一个bucket存放超过8个键值对时就会再创建一个键值对，用类似链表的方式将bucket连接起来。

下图展示产生冲突后的map： map bucket数据结构指示下一个bucket的指针称为overflow bucket，意为当前bucket盛不下而溢出的部分。事实上哈希冲突并不是好事情，它降低了存取效率，好的哈希算法可以保证哈希值的随机性，但冲突过多也是要控制的，后面会再详细介绍。

负载因子

负载因子用于衡量一个哈希表冲突情况，公式为：

负载因子 = 键数量/bucket数量

例如，对于一个 bucket 数量为 4，包含 4 个键值对的哈希表来说，这个哈希表的负载因子为 1.

哈希表需要将负载因子控制在合适的大小，超过其阀值需要进行 rehash，也即键值对重新组织：

哈希因子过小，说明空间利用率低
哈希因子过大，说明冲突严重，存取效率低

每个哈希表的实现对负载因子容忍程度不同，比如 Redis 实现中负载因子大于 1 时就会触发 rehash，而 Go 则在在负载因子达到 6.5 时才会触发 rehash，因为 Redis 的每个 bucket 只能存 1 个键值对，而 Go 的 bucket 可能存 8 个键值对，所以 Go 可以容忍更高的负载因子。

渐进式扩容

扩容的前提条件

为了保证访问效率，当新元素将要添加进map时，都会检查是否需要扩容，扩容实际上是以空间换时间的手段。触发扩容的条件有二个：

负载因子 > 6.5 时，也即平均每个 bucket 存储的键值对达到 6.5 个。
overflow数量 > 2^15 时，也即 overflow 数量超过 32768 时。

增量扩容

当负载因子过大时，就新建一个 bucket，新的 bucket 长度是原来的 2 倍，然后旧 bucket 数据搬迁到新的 bucket。考虑到如果 map 存储了数以亿计的 key-value，一次性搬迁将会造成比较大的延时，Go 采用逐步搬迁策略，即每次访问 map 时都会触发一次搬迁，每次搬迁 2 个键值对。

下图展示了包含一个 bucket 满载的 map(为了描述方便，图中 bucket 省略了 value 区域):

等量扩容

所谓等量扩容，实际上并不是扩大容量，buckets数量不变，重新做一遍类似增量扩容的搬迁动作，把松散的键值对重新排列一次，以使bucket的使用率更高，进而保证更快的存取。在极端场景下，比如不断的增删，而键值对正好集中在一小部分的bucket，这样会造成overflow的bucket数量增多，但负载因子又不高，从而无法执行增量搬迁的情况，如下图所示：上图可见，overflow 的 buckt 中大部分是空的，访问效率会很差。此时进行一次等量扩容，即 buckets 数量不变，经过重新组织后 overflow 的bucket 数量会减少，即节省了空间又会提高访问效率。

查找过程

查找过程如下：

跟据key值算出哈希值。
取哈希值低位与 hmpa.B 取模确定 bucket 位置。
取哈希值高位在tophash数组中查询。
如果tophash[i]中存储值也哈希值相等，则去找到该bucket中的key值进行比较。
当前bucket没有找到，则继续从下个overflow的bucket中查找。
如果当前处于搬迁过程，则优先从oldbuckets查找。

注：如果查找不到，也不会返回空值，而是返回相应类型的0值。

插入过程

新员素插入过程如下：

跟据key值算出哈希值
取哈希值低位与hmap.B取模确定bucket位置
查找该key是否已经存在，如果存在则直接更新值
如果没找到将key，将key插入。