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 // 旧存储桶的地址，在扩容时候用
nevacuate uintptr // 记录疏散桶进度 TODO
extra *mapextra // 当 bucket 不含指针时，记录所有溢出桶的地址，加快 gc
}
// runtime/map.go:151
// 一个桶的设计
type bmap struct {
tophash [bucketCnt]uint8 // 高 64 位存储每个 key 的信息
// 后面跟 8 个 key
// 然后跟 8 个 value
// 下一个溢出桶地址
}
初始化
m := make(map[int]string) // 初始化一个empty的 map，所有参数都是 0，用的方法是h := new(hmap) 参考runtime/map.go:294
m2 := make(map[int]string,100) // 初始化一个大小为 128 的 map
m3 := map[int]string{1:"a"} // 初始化 1 个桶的 map
我的golang是 1.21 版本（go version go1.21.1 darwin/arm64）
先分析使用 make 的情况，当 make 的第二个参数不填或者<=8的时候，调用的是 makemap_small(runtime/map.go:294) 函数，但我本地看汇编代码并没有发现 makemap_small 函数，应该是编译器有别的优化，具体可以深入研究一下，其他版本的 golang 还没测。
这里其实进行了很简单的内存分配和随机种子，所以找不到也可以理解
// runtime/map.go:294
func makemap_small() *hmap {
h := new(hmap)
h.hash0 = fastrand() // 随机 hash 种子
return h
}
当第二个参数 >8的时候，会调用 makemap(runtime/map.go:305) 函数，这个从汇编代码可以看到，会进行 bucket 的内存分配
// runtime/map.go:305
func makemap(t *maptype, hint int, h *hmap) *hmap {
mem, overflow := math.MulUintptr(uintptr(hint), t.Bucket.Size_)
if overflow || mem > maxAlloc {
hint = 0
}
// 这块跟 makemap_small是一样的
if h == nil {
h = new(hmap)
}
h.hash0 = fastrand()
// 这块主要是计算桶的数量
B := uint8(0)
for overLoadFactor(hint, B) {
B++
}
h.B = B
// 这块进行 bucket 的初始化
if h.B != 0 {
var nextOverflow *bmap
h.buckets, nextOverflow = makeBucketArray(t, h.B, nil)
if nextOverflow != nil {
h.extra = new(mapextra)
h.extra.nextOverflow = nextOverflow
}
}
return h
}
同时在 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文章来源：https://www.toymoban.com/news/detail-746243.html
参考
深入解析Golang的map设计
逐行拆解 Go map 源码
Go语言基础结构 —— Map(哈希表)
golang map 从源码分析实现原理（go 1.14）
我可能并不会使用golang map
GO语言设计与实现-3.3哈希表
Go 程序员面试笔试宝典-哈希表文章来源地址https://www.toymoban.com/news/detail-746243.html
到了这里，关于golang map的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
