golang map

golang 的 map 使用的是 hash map
基本结构

下面截取自源码，已翻译

1. // runtime/map.go:117
3. // go map 定义,hashmap 缩写
4. type hmap struct {
5.         count     int // map 里文件数
6.         flags     uint8 // map 当前是否在写入，一般为 hashWriting  = 4 （写入中）或 0 （空闲）
7.         B         uint8  // 桶的数量，2^B 个
8.         noverflow uint16 // 溢出桶的数量
9.         hash0     uint32 // hash 随机数，从 hmap 创建开始就不变
11.         buckets    unsafe.Pointer // 存储桶的指针，存放 2^B 个桶的地址
12.         oldbuckets unsafe.Pointer // 旧存储桶的地址，在扩容时候用
13.         nevacuate  uintptr        // 记录疏散桶进度 TODO
15.         extra *mapextra // 当 bucket 不含指针时，记录所有溢出桶的地址，加快 gc
16. }

复制代码

1. // runtime/map.go:151
3. // 一个桶的设计
4. type bmap struct {
5.         tophash [bucketCnt]uint8 // 高 64 位存储每个 key 的信息
6.         // 后面跟 8 个 key
7.         // 然后跟 8 个 value
8.         // 下一个溢出桶地址
9. }

复制代码

初始化

1. m  := make(map[int]string) // 初始化一个empty的 map，所有参数都是 0，用的方法是h := new(hmap) 参考runtime/map.go:294
2. m2 := make(map[int]string,100) // 初始化一个大小为 128 的 map
3. m3 := map[int]string{1:"a"} // 初始化 1 个桶的 map

复制代码

我的golang是 1.21 版本（go version go1.21.1 darwin/arm64）
先分析使用 make 的情况，当 make 的第二个参数不填或者8的时候，会调用 makemap(runtime/map.go:305) 函数，这个从汇编代码可以看到，会进行 bucket 的内存分配

1. // runtime/map.go:294
3. func makemap_small() *hmap {
4.         h := new(hmap)
5.         h.hash0 = fastrand() // 随机 hash 种子
6.         return h
7. }

复制代码

同时在 key 是 32 位，64 位，string 时，都用的同一样的创建 map，但是插入、读取、删除函数有各自的优化，否则就用通用的插入读取删除
插入

先对 key 进行 hash（hash 函数运行时得到，根据处理器有关，一般是 aes），得到 64 位的哈希值
用哈希值的低 B (hmap.B) 位来确定该 key 落入哪个桶内
再用哈希值的高 8 位寻找在 bucket 里的位置
然后依次找到空的位置，将 key，value 写入 bucekt 里的对应位置
如果当前 bucket 满了，会触发溢出桶，新建一个 bucket 的操作

读取

读取和插入类似，先对 key 进行 hash 运算得到 64 位 hash 值
然后依次计算低 B 位，高 8 位
然后找到对应的桶，再依次找高八位相同的值，再比较 key，所以能作为 map 的 key 的一定是可比较的类型，也就是支持==操作
如果找不到返回默认值

扩容

map 在元素增加过多或过于稀疏都会发生扩容

• 当装载因子大于 6.5，会发生扩容
  
• 当溢出桶的数量过多，但是装载因子却 < 6.5，说明map 比较稀疏，就需要sameSizeGrow，称作等量扩容
  

扩容

扩容就是增加一倍的 bucket 数量，把原来的某个 bucket 的元素重新取低B位，然后放到新的桶里

等量扩容

等量扩容也是走的扩容流程，只不过B 不+1，只是新建一个 bucket，将原来 bucket 里的数据搬迁到新的 bucket 里，当有多个溢出桶时候可能会压缩成一个，就没有溢出桶了

遍历

首先明确，map 在 range 遍历的时候返回的是值的拷贝，而不是原值，所以对遍历的值的修改对原值不会影响，如果遍历的 value 是指针的话，就相当于拿指针修改，就会有影响，但是 map 里存的值不会变
map 在遍历的时候先随机一个种子，然后从一个随机的 bucket 和随机的位置开始遍历
如果在扩容中，会查看 bucket 是否正在扩容，如果是正在扩容，回去老的 bucket 就是 oldbuckets 那遍历

难点

扩容

map 的主要难点就是扩容相关
并发

map 在写入时会将 flag 置为hashWriting，其他协程有写操作时候，会 panic
参考

深入解析Golang的map设计
逐行拆解 Go map 源码
Go语言基础结构 —— Map(哈希表)
golang map 从源码分析实现原理（go 1.14）
我可能并不会使用golang map
GO语言设计与实现-3.3哈希表
Go 程序员面试笔试宝典-哈希表

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！