map数据结构

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

runtime/map.go:hmap
type hmap struct{
	count int //当前保存的数据元素
	...
	B uint8 // buckets 的对数 
	...
	buckets unsafe.pointer //bucket 数组指针，数组的大小为2^B
	...
}

下图展示一个4个bucket的map案例

bucket哈希桶

bucket 数据结构

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

键值对存储（key, value）

哈希表通常会有一堆桶来存储键值对，一个个键值对来了必然要选择一个桶，先通过hash函数将“键”处理一下，得到一个hash值，利用hash值从m的个中选择一个，桶编号区间为[0,m-1]

如何从m个桶中选择：

第一种:

  • 取模法（hash%m）

第二种：

  • 与运算法（hash & (m-1)）

若想确保运算结果落在区间[0,m-1]而不会出现空桶，就要限制桶的个数m必须是2的整数幂，这样m的二进制数肯定只含一个1（比如：m = 4 二进制表示:0000 0100，m-1 二进制表示:0000 0011）,如果桶的数目不是2的整数次幂，就会出现有些桶不会被选中，如果后来又有新的键值对选择这个桶，就会发生hash冲突,后续将介绍到.

与运算法拉链法

基本过程如下（与运算法）
假设当前 B=4 即桶数量为2^B=16个，要从map中获取k4对应的value

  1. 根据key值算出哈希值
  2. 取哈希值低位B 位与m-1（m表示桶的数量）与运算确定bucket位置
  3. 查找该key是否已经存在，如果存在则直接更新值
  4. 如果没找到将key，将key插入
  5. 如果当前桶元素已满，会通过overflow链接创建一个新的桶，来存储数据。

查找过程

  • 根据key值算出哈希值
  • 取哈希值低位 B 位与m-1（m表示桶的数量）与运算确定bucket位置
  • 取哈希值高位（10101010）在tophash数组中查询
  • 如果tophash[i]中存储值也与哈希值相等，则去找到该bucket中的key值进行比较
  • 当前bucket没有找到，则继续从下个overflow的bucket中查找。
  • 如果当前处于搬迁过程，则优先从oldbuckets查找

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

hash冲突

当有两个或以上数量的键被哈希到了同一个bucket时，我们称这些键发生了冲突。

解决hash冲突的方法有两种,第一种开放地址法 , 第二种: 链地址法 , Go语言使用链地址法也叫拉链法来解决冲突键

拉链法:

hsah

下图为冲突后的map

bucket数据结构指示下一个bucket的指针称为overflow bucket，意为当前bucket盛不下而溢出的部分。哈希冲突并不是好事情，它降低了存取效率

负载因子

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

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

  1. 哈希表需要将负载因子控制在合适的大小，超过其阀值需要进行rehash，也即键值对重新组织：
  • 哈希因子过小，说明空间利用率低
  • 哈希因子过大，说明冲突严重，存取效率低

扩容

扩容的条件

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

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

增量扩容

当负载因子过大时，就新建一个bucket，新的bucket长度是原来的2倍，然后旧bucket数据搬迁到新的bucket。

考虑到如果map存储了数以亿计的key-value，一次性搬迁将会造成比较大的延时，Go采用逐步搬迁策略，即每次访问map时都会触发一次搬迁，每次搬迁2个键值对。

下图展示了包含一个bucket满载的map

当map种存储了7个键值对,只有一个bucket.此负载因子为7.再次插入数据时发生扩容操作,扩容之后将新插入键写入bucket.

当第8个键值对插入时,触发扩容,扩容示意图如下:

hmap数据结构中oldbuckets成员指身原bucket，而buckets指向了新申请的bucket。新的键值对被插入新的bucket中。

后续对map的访问操作会触发迁移，将oldbuckets中的键值对逐步的搬迁过来。当oldbuckets中的键值对全部搬迁完毕后，删除oldbuckets。

还有等量扩容,本文没写