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 // 旧存储桶的地址，在扩容时候用
	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 在元素增加过多或过于稀疏都会发生扩容

1. 当装载因子大于 6.5，会发生扩容
2. 当溢出桶的数量过多，但是装载因子却 < 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 程序员面试笔试宝典-哈希表