深入理解golang map golang

golang map 版本 go1.14
正确使用

func main() { var m map[int]string // 初始化map // [问题1] make初始化map时指定size和不指定size有什么区别 m = make(map[int]string) m[0] = "hello" m0, ok := m[0] if ok { fmt.Println("get m0:", m0) } m1, ok := m[1] if ok { fmt.Println("get m1:", m1) } for k, v := range m { fmt.Printf("k:%d,v:%s\n", k, v) } }

输出结果：

get m0: hello k:0,v:hello

错误使用

map没有进行初始化进行赋值，会引发panic

func main() { var m map[int]string m[0] = "hello" }

输出结果：

panic: assignment to entry in nil map

在不加锁的情况下，对map进行并发读写

func main() { m := make(map[int]int) // 开启一个协程对map进行写操作 go func() { for i := 0; i < 1000; i++ { m[i] = i } }() // 开启一个协程对map进行读操作 go func() { for i := 0; i < 1000; i++ { fmt.Println(m[i]) } }() time.Sleep(10 * time.Second) }

输出结果：

fatal error: concurrent map read and map write

编程实践

map在使用前必须初始化，即使用make构建map对象。
确保用key读取到map的元素有效。
map是并发不安全的，在并发情况下，使用锁或者sync.Map确保并发安全。
make申请map时，根据预估大小来申请合适内存

map的数据结构【hmap】
src/runtime/map.go

// map结构体 type hmap struct { countint// 元素个数 flagsuint8 Buint8// 表示桶的个数，桶的个数等于2^B个 noverflow uint16 // 溢出桶的数量 hash0uint32 // 32位的hash值bucketsunsafe.Pointer // 桶 oldbuckets unsafe.Pointer // 旧桶的数组，在扩容的时候会用到 nevacuateuintptr// 标识的是搬迁的位置(也可以考虑为搬迁的进度）extra *mapextra // 额外信息 }

【bmap】

// 桶 type bmap struct { tophash [8]uint8 //tophash表示这个桶所存放的key的hash值的top部分，每个桶最多可以表示8个tophash，可以存放8组key-vale。用hash的前8位表示tophash。 }

【mapextra】

// mapextra holds fields that are not present on all maps. // 如果map的key和elem都不是指针类型，就把这个桶标记为不含指针的，从而避免扫描这个此类map。然而，bmap.overflow是一个指针，为了保持overflow存活，将指向所有overflow桶的指针存储在在hmap.extra.overflow和hmap.extra.oldoverflow中。 overflow和oldoverflow只有在map的key和elem都不是指针的时候才会使用。 type mapextra struct { // 包含hmap.Buckets的指针 overflow*[]*bmap // 包含hmap.OldBuckets的指针 oldoverflow *[]*bmap// 指向下一个空闲的桶 nextOverflow *bmap }

初始化【makemap_small && makemap】
src/runtime/map.go

// 当使用make不指定size或size<=8时，使用makemap_small // 初始化一个hmap的结构体，map会分配到堆上 func makemap_small() *hmap { h := new(hmap) h.hash0 = fastrand() return h }// 初始化map，根据hint func makemap(t *maptype, hint int, h *hmap) *hmap { mem, overflow := math.MulUintptr(uintptr(hint), t.bucket.size) if overflow || mem > maxAlloc { hint = 0 } // initialize Hmap if h == nil { h = new(hmap) } h.hash0 = fastrand() // 根据hint确定B的值，桶的数量为2^B个，如果元素的个数除以桶的个数>6.5，那么B会+1 B := uint8(0) for overLoadFactor(hint, B) { B++ } h.B = B // B>0时，分配buckets和nextOverflow if h.B != 0 { var nextOverflow *bmap // todo... h.buckets, nextOverflow = makeBucketArray(t, h.B, nil) if nextOverflow != nil { h.extra = new(mapextra) h.extra.nextOverflow = nextOverflow } } return h }

使用make初始化map时，编译器会根据指定的size决定是调用makemap_small还是makemap.

创建一个hmap
根据指定的元素数量，计算出B的值
当B>0时，调用makeBucketArray去创建桶，并指定下一个桶的位置。

通过key获取map的值【mapaccess1】

func mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer { if raceenabled && h != nil { callerpc := getcallerpc() pc := funcPC(mapaccess1) racereadpc(unsafe.Pointer(h), callerpc, pc) raceReadObjectPC(t.key, key, callerpc, pc) } if msanenabled && h != nil { msanread(key, t.key.size) } // 如果map为nil或者map的元素数量为0，返回零值 if h == nil || h.count == 0 { if t.hashMightPanic() { t.hasher(key, 0) // see issue 23734 } return unsafe.Pointer(&zeroVal[0]) } // 不能同时读写 if h.flags&hashWriting != 0 { throw("concurrent map read and map write") } // 计算出key的hash值 hash := t.hasher(key, uintptr(h.hash0)) // bucketMask返回桶的数量-1，比如B=4,m=15 (1111) m := bucketMask(h.B) // hash&m，将key的hash值跟m按位与计算，得出key所在桶的编号，再乘以每个桶的大小加上初始桶的位置，获取到桶的地址 b := (*bmap)(add(h.buckets, (hash&m)*uintptr(t.bucketsize))) // 旧桶不为空，说明桶正在扩容 if c := h.oldbuckets; c != nil { // 判断是否是同体积扩容 if !h.sameSizeGrow() { // There used to be half as many buckets; mask down one more power of two. m >>= 1 } // 计算出key在oldBuckets中桶的地址 oldb := (*bmap)(add(c, (hash&m)*uintptr(t.bucketsize))) // 判断旧桶是否已经被搬运了 if !evacuated(oldb) { b = oldb } } // 获取hash的高8位，为top值 top := tophash(hash) bucketloop: // 遍历桶的链表 for ; b != nil; b = b.overflow(t) { // 遍历桶中的格子，先比较tophash的值是否一致，如果不一致就跳过 for i := uintptr(0); i < bucketCnt; i++ { if b.tophash[i] != top { if b.tophash[i] == emptyRest { break bucketloop } continue } // 如果tophash一致，则计算出这个格子的key的地址 k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize)) if t.indirectkey() { k = *((*unsafe.Pointer)(k)) } // 比较两个key是否一致，如果一致，则找到对应的值的地址，返回值，否则就继续查找 if t.key.equal(key, k) { e := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize)) if t.indirectelem() { e = *((*unsafe.Pointer)(e)) } return e } } } return unsafe.Pointer(&zeroVal[0]) }

先做一些基础校验
计算出key的hash值m
获取key所在的桶的地址b
计算出key hash值的高8位 top
遍历桶链表，比较桶中的每个格子是否与top一致，如果一致再获取到格子对应的key值是否与要查找的key一致，一致则返回对应的值

向map插入值【maoassign】

func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer { if h == nil { panic(plainError("assignment to entry in nil map")) } if raceenabled { callerpc := getcallerpc() pc := funcPC(mapassign) racewritepc(unsafe.Pointer(h), callerpc, pc) raceReadObjectPC(t.key, key, callerpc, pc) } if msanenabled { msanread(key, t.key.size) } // 检验当前map是否正在进行写操作 if h.flags&hashWriting != 0 { throw("concurrent map writes") } hash := t.hasher(key, uintptr(h.hash0))// 将flags设置为写 h.flags ^= hashWritingif h.buckets == nil { h.buckets = newobject(t.bucket) // newarray(t.bucket, 1) }again: // 确定key所在的桶，如果map正在扩容，需要确保我们正在使用的旧桶已经被搬运到新桶 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)var inserti *uint8 var insertk unsafe.Pointer var elem unsafe.Pointer bucketloop: // 遍历查找桶中key是否存在，并将找到的第一个空格子记录下来（inserti） for { for i := uintptr(0); i < bucketCnt; i++ { if b.tophash[i] != top { if isEmpty(b.tophash[i]) && inserti == nil { inserti = &b.tophash[i] insertk = add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize)) elem = add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize)) } if b.tophash[i] == emptyRest { break bucketloop } continue } k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize)) if t.indirectkey() { k = *((*unsafe.Pointer)(k)) } if !t.key.equal(key, k) { continue } // already have a mapping for key. Update it. // key存在的时候删除 if t.needkeyupdate() { typedmemmove(t.key, k, key) } elem = add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize)) goto done } // 遍历溢出桶 ovf := b.overflow(t) if ovf == nil { break } b = ovf } // 如果key不存在，判断是否需要扩容 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 } // 没有可插入的空位时，需要新增一个溢出桶 if inserti == nil { // all current buckets are full, allocate a new one. newb := h.newoverflow(t, b) inserti = &newb.tophash[0] insertk = add(unsafe.Pointer(newb), dataOffset) elem = add(insertk, bucketCnt*uintptr(t.keysize)) }// store new key/elem at insert position if t.indirectkey() { kmem := newobject(t.key) *(*unsafe.Pointer)(insertk) = kmem insertk = kmem } if t.indirectelem() { vmem := newobject(t.elem) *(*unsafe.Pointer)(elem) = vmem } typedmemmove(t.key, insertk, key) *inserti = top h.count++done: if h.flags&hashWriting == 0 { throw("concurrent map writes") } h.flags &^= hashWriting if t.indirectelem() { elem = *((*unsafe.Pointer)(elem)) } return elem }

计算出要写入key的hash值
计算出key所在的桶，如果map正在扩容，需要保证要使用的旧桶已经被搬运，因为新增的值需要放到新桶中去
遍历桶及其链表，根据tophash查找key是否可能存在，并记录找到的第一个空格子的位置（如果遍历完桶未找到这个key，就会把这个k-v存储在这个空格子）
如果tophash存在，判断完整的key是否一致。
如果key存在，则更新值
如果key不存在，先判断是否需要扩容，如需扩容，先扩容，再重新遍历获取空格子的位置
如果所有格子都满了，那么需要新增溢出桶
保存key对应的值

map桶的扩容 map在make进行初始化的时候会根据元素的数量，分配桶的数量。
在向map中存入key-value时，如果满足以下条件，会对map进行扩容：

桶的装载因子>6.5，装载因子=count/桶的数量
overflow桶太多，当溢出桶的数量>=普通桶的数量，参考tooManyOverflowBuckets。溢出桶太多会导致扫描时间变长
当前状态不是正在扩容的状态

扩容方式：

相同容量扩容，当装载因子<=6.5时，说明是溢出桶太多了，容量不变，仅对桶进行整理。
2倍容量扩容，当装载因子>6.5时，将桶的数量乘以2进行扩容。

map遍历【runtime.mapiterinit】
【runtime.mapiternext】
map遍历主要调用了这两个方法，需要注意的是在mapiterinit方法中有一行代码r := uintptr(fastrand())用来指定从哪个桶开始遍历，这个桶是随机的。
map遍历时是无序的，因为map扩容时会重新整理桶，这样会改变原有的顺序。
map并发安全 map在并发时是不安全的，在mapaccess1和mapassign方法中，也对并发读写的情况进行了判断，如果发生并发读写的情况，就会引发panic。
解决方法有：