数据结构

初始化

1
2
3
4
5

mp := map[string]int{
    "111": 1,
    "222": 2,
    "333": 3,
}

当哈希表中的元素数量少于或者等于 25 个时，编译器会将字面量初始化的结构体转换成以下的代码，将所有的键值对一次加入到哈希表中：

1
2
3
4

hash := make(map[string]int, 3)
hash["1"] = 2
hash["3"] = 4
hash["5"] = 6

一旦哈希表中元素的数量超过了 25 个，编译器会创建两个数组分别存储键和值，这些键值对会通过如下所示的 for 循环加入哈希：

1
2
3
4
5
6

hash := make(map[string]int, 26)
vstatk := []string{"1", "2", "3", ... ， "26"}
vstatv := []int{1, 2, 3, ... , 26}
for i := 0; i < len(vstak); i++ {
    hash[vstatk[i]] = vstatv[i]
}

makemap: 这个函数会按照下面的步骤执行：

计算哈希占用的内存是否溢出或者超出能分配的最大值；
调用 runtime.fastrand 获取一个随机的哈希种子；
根据传入的 hint 计算出需要的最小需要的桶的数量；
使用 runtime.makeBucketArray 创建用于保存桶的数组；

runtime.makeBucketArray 会根据传入的 B 计算出的需要创建的桶数量并在内存中分配一片连续的空间用于存储数据, 根据该函数的代码，我们能确定在正常情况下，正常桶和溢出桶在内存中的存储空间是连续的，只是被 runtime.hmap 中的不同字段引用，当溢出桶数量较多时会通过 runtime.newobject 创建新的溢出桶。

访问

写

扩容

runtime.mapassign 函数会在以下两种情况发生时触发哈希的扩容：

装载因子已经超过 6.5；
哈希使用了太多溢出桶；

哈希在扩容的过程中会通过 runtime.makeBucketArray 创建一组新桶和预创建的溢出桶，随后将原有的桶数组设置到 oldbuckets 上并将新的空桶设置到 buckets 上，溢出桶也使用了相同的逻辑更新

等量扩容 和 双倍扩容

分流

访问：oldbucket中还存这所有旧的值

我们在 runtime.mapassign 函数中也省略了一段逻辑，当哈希表正在处于扩容状态时，每次向哈希表写入值时都会触发 runtime.growWork 增量拷贝哈希表中的内容

当然除了写入操作之外，删除操作也会在哈希表扩容期间触发 runtime.growWork，触发的方式和代码与这里的逻辑几乎完全相同，都是计算当前值所在的桶，然后拷贝桶中的元素。

简单总结一下哈希表扩容的设计和原理，哈希在存储元素过多时会触发扩容操作，每次都会将桶的数量翻倍，扩容过程不是原子的，而是通过 runtime.growWork 增量触发的，在扩容期间访问哈希表时会使用旧桶，向哈希表写入数据时会触发旧桶元素的分流。除了这种正常的扩容之外，为了解决大量写入、删除造成的内存泄漏问题，哈希引入了 sameSizeGrow 这一机制，在出现较多溢出桶时会整理哈希的内存减少空间的占用。

删除

哈希表的删除逻辑与写入逻辑很相似，只是触发哈希的删除需要使用关键字，如果在删除期间遇到了哈希表的扩容，就会分流桶中的元素，分流结束之后会找到桶中的目标元素完成键值对的删除工作。

访问： 根据创建时生成的hash种子和哈希函数，求出本次查找key的哈希值

取模得到key在hmap数组中的下标，访问该下标获得链表头，遍历链表，遍历的过程中

写： 遍历类似，先找到位置，然后写入。涉及当前桶使用完毕，使用溢出桶。

写设计overflow