golang map的实现源码在文件 runtime/map.go中，map的底层数据结构是hash表。
hash函数：通过指定的函数，将输入值重新生成得到一个散列值
hash表：散列值会确定其键应该映射到哪一个桶。而一个好的哈希函数，应当尽量少的出现哈希冲突，以此保证操作哈希表的时间复杂度
接下来从下面三个方面讲解：
- map数据结构
- map查找实现
- map插入实现
1. map的数据结构定义
type hmap struct {
count int //map存储数据的个数，len(map)使用
flags uint8 //flags会标识当前map，比如hashWriting=4第4位表示有goroutine正在往map写入
B uint8 // map有 2^B 个buckets
hash0 uint32 // hash算法的seed
buckets unsafe.Pointer // 2^B 个Buckets的数组
oldbuckets unsafe.Pointer // 正在扩容期间，oldbuckets中有值，map是增量扩容，不是一次性完成。扩容主要是插入和删除操作会触发
......
}
map数据结构图
map bucket的数据结构
一个bmap最多存储8个key/value对, 如果多于8个，那么会申请一个新的bucket，并将它与之前的bucket链起来。
tophash数组存储的key hash算法之后的高8位值
type bmap struct {
// bucketCnt = 8
tophash [bucketCnt]uint8
}
对于map的操作，主要用到的是 查找，插入
查找流程
- 根据key hash之后的值kHash
- 根据kHash低八位计算确定 bucket 的内存地址
- 遍历该bucket的tophash数组，找到tophash[i]等于kHash高8位的i值
- 找到bucket的第i个的key与所给的key相等。如果相等，则返回其对应的value。
- 遍历完bucket没找到，在overflow buckets中按照上述方法继续寻找。
查找源码
func mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
//如果有goroutine正在写入map，则不允许读。所以map是非线程安全的
if h.flags&hashWriting != 0 {
throw("concurrent map read and map write")
}
......
//确定key所在的bucket内存地址
m := bucketMask(h.B)
b := (*bmap)(add(h.buckets, (hash&m)*uintptr(t.bucketsize)))
//如果oldbuckets里面有值，从oldbuckets取值
if c := h.oldbuckets; c != nil {
oldb := (*bmap)(add(c, (hash&m)*uintptr(t.bucketsize)))
if !evacuated(oldb) {
b = oldb
}
}
//获取key hash算法之后的高8位
top := tophash(hash)
bucketloop:
for ; b != nil; b = b.overflow(t) {
//bucketCnt = 8，遍历tophash数组，tophash[i]等于kHash高8位的i值 并且 bucket的第i个的key与所给的key相等的value值
for i := uintptr(0); i < bucketCnt; i++ {
if b.tophash[i] != top {
continue
}
//对比 bucket的第i个的key与所给的key是否相等，相等就取对应的value值
k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
if alg.equal(key, k) {
v := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.valuesize))
return v
}
}
}
return unsafe.Pointer(&zeroVal[0])
}
插入流程
返回写入value值的内存地址
插入流程跟查找类似，
- 置位flags hashWriting位为1
- 根据key hash之后的值kHash
- 根据kHash低八位计算确定 bucket 的内存地址
- 判断是否正在扩容，若正在扩容中则先迁移再接着处理
- 遍历bucket和overbucket的bmap，记录第一个空槽，并把该位置标识为可插入 tophash 位置，这里就是第一个可以插入数据的地方。如果找到匹配的key值k，则返回该k对应的value值地址
- 如果bucket已经full，则申请新的bucket作为overbucket，插入key/value键值对。
- map没有正在扩容 && 触发最大 LoadFactor && 有过多溢出桶 overflow buckets，则会触发扩容
map插入的源码mapassign，返回写入value值的地址
func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
.....
again:
//根据hash值，确定bucket
bucket := hash & bucketMask(h.B)
if h.growing() {
//是否正在扩容，若正在扩容中则先迁移再接着处理
growWork(t, h, bucket)
}
b := (*bmap)(unsafe.Pointer(uintptr(h.buckets) + bucket*uintptr(t.bucketsize)))
top := tophash(hash)
bucketloop:
for {
//遍历bucket的bitmap
for i := uintptr(0); i < bucketCnt; i++ {
if b.tophash[i] != top {
//tophash 第i位没有赋值，并且是空槽，则记录下来，这是可以插入新key/value值的地址
if isEmpty(b.tophash[i]) && inserti == nil {
inserti = &b.tophash[i]
insertk = add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
val = add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.valuesize))
}
if b.tophash[i] == emptyRest {
break bucketloop
}
continue
}
//tophash第i位等于key hash值的高8位，
k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
//key和k不匹配，继续遍历下一个k
if !alg.equal(key, k) {
continue
}
// map中已经存在key，value值
val = add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.valuesize))
goto done
}
//bucket不符合条件，开始遍历overbucket
ovf := b.overflow(t)
b = ovf
}
//map没有正在扩容 && 触发最大 LoadFactor && 有过多溢出桶 overflow buckets，则会触发扩容
if !h.growing() && (overLoadFactor(h.count+1, h.B) || tooManyOverflowBuckets(h.noverflow, h.B)) {
hashGrow(t, h)
goto again // Growing the table invalidates everything, so try again
}
有疑问加站长微信联系（非本文作者）
