golang map
golang 的 map 使用的是 hash map基本结构
下面截取自源码，已翻译
// runtime/map.go:117
// go map 定义,hashmap 缩写
type hmap struct {
count int // map 里文件数
flags uint8 // map 当前是否在写入，一般为 hashWriting= 4 （写入中）或 0 （空闲）
B uint8// 桶的数量，2^B 个
noverflow uint16 // 溢出桶的数量
hash0 uint32 // hash 随机数，从 hmap 创建开始就不变
buckets unsafe.Pointer // 存储桶的指针，存放 2^B 个桶的地址
oldbuckets unsafe.Pointer // 旧存储桶的地址，在扩容时候用
nevacuateuintptr // 记录疏散桶进度 TODO
extra *mapextra // 当 bucket 不含指针时，记录所有溢出桶的地址，加快 gc
}https://img2023.cnblogs.com/blog/1118392/202311/1118392-20231116142317574-85042685.png
// runtime/map.go:151
// 一个桶的设计
type bmap struct {
tophash uint8 // 高 64 位存储每个 key 的信息
// 后面跟 8 个 key
// 然后跟 8 个 value
// 下一个溢出桶地址
}https://img2023.cnblogs.com/blog/1118392/202311/1118392-20231116142327853-417675255.png
初始化
m:= make(mapstring) // 初始化一个empty的 map，所有参数都是 0，用的方法是h := new(hmap) 参考runtime/map.go:294
m2 := make(mapstring,100) // 初始化一个大小为 128 的 map
m3 := mapstring{1:"a"} // 初始化 1 个桶的 map我的golang是 1.21 版本（go version go1.21.1 darwin/arm64）
先分析使用 make 的情况，当 make 的第二个参数不填或者8的时候，会调用 makemap(runtime/map.go:305) 函数，这个从汇编代码可以看到，会进行 bucket 的内存分配
// runtime/map.go:294
func makemap_small() *hmap {
h := new(hmap)
h.hash0 = fastrand() // 随机 hash 种子
return h
}同时在 key 是 32 位，64 位，string 时，都用的同一样的创建 map，但是插入、读取、删除函数有各自的优化，否则就用通用的插入读取删除
插入
先对 key 进行 hash（hash 函数运行时得到，根据处理器有关，一般是 aes），得到 64 位的哈希值
用哈希值的低 B (hmap.B) 位来确定该 key 落入哪个桶内
再用哈希值的高 8 位寻找在 bucket 里的位置
然后依次找到空的位置，将 key，value 写入 bucekt 里的对应位置
如果当前 bucket 满了，会触发溢出桶，新建一个 bucket 的操作
https://img2023.cnblogs.com/blog/1118392/202311/1118392-20231116142343183-247329315.png
读取
读取和插入类似，先对 key 进行 hash 运算得到 64 位 hash 值
然后依次计算低 B 位，高 8 位
然后找到对应的桶，再依次找高八位相同的值，再比较 key，所以能作为 map 的 key 的一定是可比较的类型，也就是支持==操作
如果找不到返回默认值
https://img2023.cnblogs.com/blog/1118392/202311/1118392-20231116142351393-2092471165.png
扩容
map 在元素增加过多或过于稀疏都会发生扩容
[*]当装载因子大于 6.5，会发生扩容
[*]当溢出桶的数量过多，但是装载因子却 < 6.5，说明map 比较稀疏，就需要sameSizeGrow，称作等量扩容
扩容
扩容就是增加一倍的 bucket 数量，把原来的某个 bucket 的元素重新取低B位，然后放到新的桶里
https://img2023.cnblogs.com/blog/1118392/202311/1118392-20231116142401870-687861479.png
等量扩容
等量扩容也是走的扩容流程，只不过B 不+1，只是新建一个 bucket，将原来 bucket 里的数据搬迁到新的 bucket 里，当有多个溢出桶时候可能会压缩成一个，就没有溢出桶了
https://img2023.cnblogs.com/blog/1118392/202311/1118392-20231116142409923-1160509598.png
遍历
首先明确，map 在 range 遍历的时候返回的是值的拷贝，而不是原值，所以对遍历的值的修改对原值不会影响，如果遍历的 value 是指针的话，就相当于拿指针修改，就会有影响，但是 map 里存的值不会变
map 在遍历的时候先随机一个种子，然后从一个随机的 bucket 和随机的位置开始遍历
如果在扩容中，会查看 bucket 是否正在扩容，如果是正在扩容，回去老的 bucket 就是 oldbuckets 那遍历
https://img2023.cnblogs.com/blog/1118392/202311/1118392-20231116142417880-1797314770.png
难点
扩容
map 的主要难点就是扩容相关
并发
map 在写入时会将 flag 置为hashWriting，其他协程有写操作时候，会 panic
参考
深入解析Golang的map设计
逐行拆解 Go map 源码
Go语言基础结构 —— Map(哈希表)
golang map 从源码分析实现原理（go 1.14）
我可能并不会使用golang map
GO语言设计与实现-3.3哈希表
Go 程序员面试笔试宝典-哈希表
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！
页:
[1]