package mainimport ( "fmt")func main(){ mapa:= make(map[string]int, 10) // var mapa map[string]int mapa["zhao"] = 1 mapa["qian"] = 2 fmt.Println(mapa["li"])}复制代码
看上面的例子,我们可能存在的疑问有以下几个:
- 1.make进行map的创建,后面的参数10是干啥的,不同的值,有啥区别?不提供行不行?
- 2.注释掉的var申明的map能不能直接进行赋值操作?
- 3.我获取不存在的key,结果是怎样的?
- 4.最后一个终极问题,分配的底层数组用完之后,啥时候扩容?
等等,或许你还有其他的疑问,我们首先看看上面的几个疑问吧
先看看在make创建map时,参数为10.具体执行的操作
0x0050 00080 (/Users/zhaojunwei/workspace/src/just.for.test/maptest/demo.go:8)PCDATA$2, $10x0050 00080 (/Users/zhaojunwei/workspace/src/just.for.test/maptest/demo.go:8)LEAQtype.map[string]int(SB), AX0x0057 00087 (/Users/zhaojunwei/workspace/src/just.for.test/maptest/demo.go:8)PCDATA$2, $00x0057 00087 (/Users/zhaojunwei/workspace/src/just.for.test/maptest/demo.go:8)MOVQAX, (SP)0x005b 00091 (/Users/zhaojunwei/workspace/src/just.for.test/maptest/demo.go:8)MOVQ$10, 8(SP)0x0064 00100 (/Users/zhaojunwei/workspace/src/just.for.test/maptest/demo.go:8)PCDATA$2, $10x0064 00100 (/Users/zhaojunwei/workspace/src/just.for.test/maptest/demo.go:8)PCDATA$0, $00x0064 00100 (/Users/zhaojunwei/workspace/src/just.for.test/maptest/demo.go:8)LEAQ""..autotmp_2+136(SP), AX0x006c 00108 (/Users/zhaojunwei/workspace/src/just.for.test/maptest/demo.go:8)PCDATA$2, $00x006c 00108 (/Users/zhaojunwei/workspace/src/just.for.test/maptest/demo.go:8)MOVQAX, 16(SP)0x0071 00113 (/Users/zhaojunwei/workspace/src/just.for.test/maptest/demo.go:8)CALLruntime.makemap(SB)0x0076 00118 (/Users/zhaojunwei/workspace/src/just.for.test/maptest/demo.go:8)PCDATA$2, $10x0076 00118 (/Users/zhaojunwei/workspace/src/just.for.test/maptest/demo.go:8)MOVQ24(SP), AX0x007b 00123 (/Users/zhaojunwei/workspace/src/just.for.test/maptest/demo.go:8)PCDATA$0, $20x007b 00123 (/Users/zhaojunwei/workspace/src/just.for.test/maptest/demo.go:8)MOVQAX, "".mapa+56(SP)复制代码
执行的makemap
调用,我们看看这个函数的参数和返回值情况,第一个参数是type.map[string]int(SB)
,第二个参数是10
,第三个参数很有意思
0x0064 00100 (/Users/zhaojunwei/workspace/src/just.for.test/maptest/demo.go:8)PCDATA$0, $00x0064 00100 (/Users/zhaojunwei/workspace/src/just.for.test/maptest/demo.go:8)LEAQ""..autotmp_2+136(SP), AX0x006c 00108 (/Users/zhaojunwei/workspace/src/just.for.test/maptest/demo.go:8)PCDATA$2, $00x006c 00108 (/Users/zhaojunwei/workspace/src/just.for.test/maptest/demo.go:8)MOVQAX, 16(SP)复制代码
暂且不论它是啥,先看看makemap函数的原型
// makemap 实现了Go map的创建,通过make(map[k]v, hint).// 如果编译器确定该映射或第一个存储桶,可以在堆栈上创建,h和/或bucket可以为非nil。// 如果参数h 不为nil,map可以直接在h中创建。// 如果h.buckets 不为nil,bucket指针指向的可以用于作为第一个桶。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 Hmapif h == nil {h = new(hmap)}h.hash0 = fastrand()// Find the size parameter B which will hold the requested # of elements.// For hint < 0 overLoadFactor returns false since hint < bucketCnt.B := uint8(0)for overLoadFactor(hint, B) {B++}h.B = B// allocate initial hash table// if B == 0, the buckets field is allocated lazily later (in mapassign)// If hint is large zeroing this memory could take a while.if h.B != 0 {var nextOverflow *bmaph.buckets, nextOverflow = makeBucketArray(t, h.B, nil)if nextOverflow != nil {h.extra = new(mapextra)h.extra.nextOverflow = nextOverflow}}return h}复制代码
从原型中看,第三个参数是hmap指针,这个东西是啥呢,如果h为nil,还需要new一个?
const ( // 一个桶中可以容纳的最大数据的key/value对bucketCntBits = 3bucketCnt = 1 << bucketCntBits...)// A header for a Go map.type hmap struct {count int // 元素个数,必须位于第一项,调用 len(map) 时,直接返回此值flags uint8B uint8 // B 是 buckets 数组的长度以2为底的对数, (可以容纳 loadFactor * 2^B 个元素)noverflow uint16 // 溢出桶的大概数量hash0 uint32 // 哈希种子buckets unsafe.Pointer // 数据存储桶oldbuckets unsafe.Pointer // 扩容前的桶,只有在扩容的时候非空。nevacuate uintptr // progress counter for evacuation (buckets less than this have been evacuated)extra *mapextra // 可选字段}// 桶的数据结构原型结构体.type bmap struct { // tophash 通常包含桶中每个键的hash值的最高字节(8位)tophash [bucketCnt]uint8 // 8字节长度的数组// 之后是bucketCnt数量的键,然后是bucketCnt数量的值。// 后跟一个溢出指针。}复制代码
overLoadFactor函数的原型为
const (... // 触发增长的存储桶的最大平均负载为6.5。// 表示为loadFactorNum / loadFactDen,以允许整数数学运算。loadFactorNum = 13loadFactorDen = 2...)// bucketShift返回1 << b,已针对代码生成进行了优化。func bucketShift(b uint8) uintptr {if sys.GoarchAmd64|sys.GoarchAmd64p32|sys.Goarch386 != 0 {b &= sys.PtrSize*8 - 1 // help x86 archs remove shift overflow checks}return uintptr(1) << b}// overLoadFactor报告count个项目放在1<<B的桶中,是否超过负载因子func overLoadFactor(count int, B uint8) bool {return count > bucketCnt && uintptr(count) > loadFactorNum*(bucketShift(B)/loadFactorDen)}复制代码
首先判断count是否大于bucketCnt,上述例子中,count就是hint,就是传入的参数10
.bucketCnt
是单个桶能容纳的最大键值对,为8
.条件成立后,继续判断count是否大于6.5*(1<<b)
如果大于返回true
否则返回false
在makemap
函数中,在对h的B值进行赋值之前,进行了一个检测overLoadFactor
循环,最终确定下来的B值为1.而B是 buckets 数组的长度以2为底的对数, (可以容纳 loadFactor * 2^B 个元素).而B不为0,会进行桶数组的分配操作
// makeBucketArray初始化map存储区的底层数组。// 1<<b是要分配桶的最小数据// dirtyalloc 应该是nil或者是一个之前使用的t和b参数已经分配的桶数组// 如果dirtyalloc是nil 表示一个新的桶数组将会分配,// 否则dirtyalloc将被清空并作为桶数组重用func makeBucketArray(t *maptype, b uint8, dirtyalloc unsafe.Pointer) (buckets unsafe.Pointer, nextOverflow *bmap) {base := bucketShift(b)nbuckets := base// 对于小b,溢出桶不太可能出现。避免计算的开销。if b >= 4 {// Add on the estimated number of overflow buckets// required to insert the median number of elements// used with this value of b.nbuckets += bucketShift(b - 4)sz := t.bucket.size * nbucketsup := roundupsize(sz)if up != sz {nbuckets = up / t.bucket.size}}if dirtyalloc == nil {buckets = newarray(t.bucket, int(nbuckets))} else {// dirtyalloc was previously generated by// the above newarray(t.bucket, int(nbuckets))// but may not be empty.buckets = dirtyallocsize := t.bucket.size * nbucketsif t.bucket.kind&kindNoPointers == 0 {memclrHasPointers(buckets, size)} else {memclrNoHeapPointers(buckets, size)}}if base != nbuckets {// We preallocated some overflow buckets.// To keep the overhead of tracking these overflow buckets to a minimum,// we use the convention that if a preallocated overflow bucket's overflow// pointer is nil, then there are more available by bumping the pointer.// We need a safe non-nil pointer for the last overflow bucket; just use buckets.nextOverflow = (*bmap)(add(buckets, base*uintptr(t.bucketsize)))last := (*bmap)(add(buckets, (nbuckets-1)*uintptr(t.bucketsize)))last.setoverflow(t, (*bmap)(buckets))}return buckets, nextOverflow}复制代码
初次调用的时候,dirtyalloc参数是nil,会首次创建一个数组
if dirtyalloc == nil {buckets = newarray(t.bucket, int(nbuckets))}复制代码
后续扩容的时候,其所指的地址为旧桶的地址,回到我们之前的问题,mapa:= make(map[string]int, 10)
type hmap struct {count int // 0flags uint8B uint8 // 1noverflow uint16 // 溢出桶的大概数量hash0 uint32 // 哈希种子buckets unsafe.Pointer // 数据存储桶oldbuckets unsafe.Pointer // 扩容前的桶,只有在扩容的时候非空。nevacuate uintptr extra *mapextra // 可选字段}复制代码
再来看看第一个问题,这个参数10,是用来在分配底层桶数组时,分配几个桶数组,为10时,B的值为1,分配两个桶数组,每个桶数组8个键值对,足够使用了,如果为20,则B的值为2,底层会分配4个桶数组。如果参数为5时,B的值为1,分配两个桶…
当然了如果在make()创建map的时候,不提供第二个参数也是可以的,但是你会发现,在提供的参数小于bucketCnt时,汇编后是看不到makemap的函数调用的。
0x0032 00050 (/Users/zhaojunwei/workspace/src/just.for.test/maptest/demo.go:8)PCDATA$0, $10x0032 00050 (/Users/zhaojunwei/workspace/src/just.for.test/maptest/demo.go:8)XORPSX1, X10x0035 00053 (/Users/zhaojunwei/workspace/src/just.for.test/maptest/demo.go:8)MOVUPSX1, ""..autotmp_3+136(SP)0x003d 00061 (/Users/zhaojunwei/workspace/src/just.for.test/maptest/demo.go:8)XORPSX1, X10x0040 00064 (/Users/zhaojunwei/workspace/src/just.for.test/maptest/demo.go:8)MOVUPSX1, ""..autotmp_3+152(SP)0x0048 00072 (/Users/zhaojunwei/workspace/src/just.for.test/maptest/demo.go:8)XORPSX1, X10x004b 00075 (/Users/zhaojunwei/workspace/src/just.for.test/maptest/demo.go:8)MOVUPSX1, ""..autotmp_3+168(SP)0x0053 00083 (/Users/zhaojunwei/workspace/src/just.for.test/maptest/demo.go:8)PCDATA$2, $10x0053 00083 (/Users/zhaojunwei/workspace/src/just.for.test/maptest/demo.go:8)PCDATA$0, $20x0053 00083 (/Users/zhaojunwei/workspace/src/just.for.test/maptest/demo.go:8)LEAQ""..autotmp_4+184(SP), DI0x005b 00091 (/Users/zhaojunwei/workspace/src/just.for.test/maptest/demo.go:8)XORPSX0, X00x005e 00094 (/Users/zhaojunwei/workspace/src/just.for.test/maptest/demo.go:8)PCDATA$2, $00x005e 00094 (/Users/zhaojunwei/workspace/src/just.for.test/maptest/demo.go:8)LEAQ-48(DI), DI0x0062 00098 (/Users/zhaojunwei/workspace/src/just.for.test/maptest/demo.go:8)DUFFZERO$2390x0075 00117 (/Users/zhaojunwei/workspace/src/just.for.test/maptest/demo.go:8)PCDATA$2, $20x0075 00117 (/Users/zhaojunwei/workspace/src/just.for.test/maptest/demo.go:8)LEAQ""..autotmp_3+136(SP), AX0x007d 00125 (/Users/zhaojunwei/workspace/src/just.for.test/maptest/demo.go:8)PCDATA$2, $00x007d 00125 (/Users/zhaojunwei/workspace/src/just.for.test/maptest/demo.go:8)TESTBAL, (AX)0x007f 00127 (/Users/zhaojunwei/workspace/src/just.for.test/maptest/demo.go:8)PCDATA$2, $20x007f 00127 (/Users/zhaojunwei/workspace/src/just.for.test/maptest/demo.go:8)PCDATA$0, $10x007f 00127 (/Users/zhaojunwei/workspace/src/just.for.test/maptest/demo.go:8)LEAQ""..autotmp_4+184(SP), AX0x0087 00135 (/Users/zhaojunwei/workspace/src/just.for.test/maptest/demo.go:8)PCDATA$2, $00x0087 00135 (/Users/zhaojunwei/workspace/src/just.for.test/maptest/demo.go:8)MOVQAX, ""..autotmp_3+152(SP)0x008f 00143 (/Users/zhaojunwei/workspace/src/just.for.test/maptest/demo.go:8)PCDATA$2, $20x008f 00143 (/Users/zhaojunwei/workspace/src/just.for.test/maptest/demo.go:8)LEAQ""..autotmp_3+136(SP), AX0x0097 00151 (/Users/zhaojunwei/workspace/src/just.for.test/maptest/demo.go:8)PCDATA$2, $00x0097 00151 (/Users/zhaojunwei/workspace/src/just.for.test/maptest/demo.go:8)PCDATA$0, $30x0097 00151 (/Users/zhaojunwei/workspace/src/just.for.test/maptest/demo.go:8)MOVQAX, ""..autotmp_5+88(SP)0x009c 00156 (/Users/zhaojunwei/workspace/src/just.for.test/maptest/demo.go:8)CALLruntime.fastrand(SB)0x00a1 00161 (/Users/zhaojunwei/workspace/src/just.for.test/maptest/demo.go:8)PCDATA$2, $20x00a1 00161 (/Users/zhaojunwei/workspace/src/just.for.test/maptest/demo.go:8)PCDATA$0, $10x00a1 00161 (/Users/zhaojunwei/workspace/src/just.for.test/maptest/demo.go:8)MOVQ""..autotmp_5+88(SP), AX0x00a6 00166 (/Users/zhaojunwei/workspace/src/just.for.test/maptest/demo.go:8)TESTBAL, (AX)0x00a8 00168 (/Users/zhaojunwei/workspace/src/just.for.test/maptest/demo.go:8)MOVL(SP), CX0x00ab 00171 (/Users/zhaojunwei/workspace/src/just.for.test/maptest/demo.go:8)PCDATA$2, $00x00ab 00171 (/Users/zhaojunwei/workspace/src/just.for.test/maptest/demo.go:8)MOVLCX, 12(AX)0x00ae 00174 (/Users/zhaojunwei/workspace/src/just.for.test/maptest/demo.go:8)PCDATA$2, $20x00ae 00174 (/Users/zhaojunwei/workspace/src/just.for.test/maptest/demo.go:8)PCDATA$0, $00x00ae 00174 (/Users/zhaojunwei/workspace/src/just.for.test/maptest/demo.go:8)LEAQ""..autotmp_3+136(SP), AX0x00b6 00182 (/Users/zhaojunwei/workspace/src/just.for.test/maptest/demo.go:8)PCDATA$2, $00x00b6 00182 (/Users/zhaojunwei/workspace/src/just.for.test/maptest/demo.go:8)PCDATA$0, $40x00b6 00182 (/Users/zhaojunwei/workspace/src/just.for.test/maptest/demo.go:8)MOVQAX, "".mapa+56(SP)复制代码
可以看到,直到进行mapa赋值操作,都没有看到makemap的函数调用。唯一的调用可能就是fastrand
.编译器确定 make map 函数的位置在:cmd/compile/internal/gc/walk.go:1199(go version go1.12.1 darwin/amd64):
case OMAKEMAP:t := n.TypehmapType := hmap(t)hint := n.Left// var h *hmapvar h *Nodeif n.Esc == EscNone {// Allocate hmap on stack.// var hv hmaphv := temp(hmapType)zero := nod(OAS, hv, nil)zero = typecheck(zero, ctxStmt)init.Append(zero)// h = &hvh = nod(OADDR, hv, nil)// Allocate one bucket pointed to by hmap.buckets on stack if hint// is not larger than BUCKETSIZE. In case hint is larger than// BUCKETSIZE runtime.makemap will allocate the buckets on the heap.// Maximum key and value size is 128 bytes, larger objects// are stored with an indirection. So max bucket size is 2048+eps.if !Isconst(hint, CTINT) ||hint.Val().U.(*Mpint).CmpInt64(BUCKETSIZE) <= 0 {// var bv bmapbv := temp(bmap(t))zero = nod(OAS, bv, nil)zero = typecheck(zero, ctxStmt)init.Append(zero)// b = &bvb := nod(OADDR, bv, nil)// h.buckets = bbsym := hmapType.Field(5).Sym // hmap.buckets see reflect.go:hmapna := nod(OAS, nodSym(ODOT, h, bsym), b)na = typecheck(na, ctxStmt)init.Append(na)}}if Isconst(hint, CTINT) && hint.Val().U.(*Mpint).CmpInt64(BUCKETSIZE) <= 0 {// Handling make(map[any]any) and// make(map[any]any, hint) where hint <= BUCKETSIZE// special allows for faster map initialization and// improves binary size by using calls with fewer arguments.// For hint <= BUCKETSIZE overLoadFactor(hint, 0) is false// and no buckets will be allocated by makemap. Therefore,// no buckets need to be allocated in this code path.if n.Esc == EscNone {// Only need to initialize h.hash0 since// hmap h has been allocated on the stack already.// h.hash0 = fastrand()rand := mkcall("fastrand", types.Types[TUINT32], init)hashsym := hmapType.Field(4).Sym // hmap.hash0 see reflect.go:hmapa := nod(OAS, nodSym(ODOT, h, hashsym), rand)a = typecheck(a, ctxStmt)a = walkexpr(a, init)init.Append(a)n = convnop(h, t)} else {// Call runtime.makehmap to allocate an// hmap on the heap and initialize hmap's hash0 field.fn := syslook("makemap_small")fn = substArgTypes(fn, t.Key(), t.Elem())n = mkcall1(fn, n.Type, init)}} else {if n.Esc != EscNone {h = nodnil()}// Map initialization with a variable or large hint is// more complicated. We therefore generate a call to// runtime.makemap to intialize hmap and allocate the// map buckets.// When hint fits into int, use makemap instead of// makemap64, which is faster and shorter on 32 bit platforms.fnname := "makemap64"argtype := types.Types[TINT64]// Type checking guarantees that TIDEAL hint is positive and fits in an int.// See checkmake call in TMAP case of OMAKE case in OpSwitch in typecheck1 function.// The case of hint overflow when converting TUINT or TUINTPTR to TINT// will be handled by the negative range checks in makemap during runtime.if hint.Type.IsKind(TIDEAL) || maxintval[hint.Type.Etype].Cmp(maxintval[TUINT]) <= 0 {fnname = "makemap"argtype = types.Types[TINT]}fn := syslook(fnname)fn = substArgTypes(fn, hmapType, t.Key(), t.Elem())n = mkcall1(fn, n.Type, init, typename(n.Type), conv(hint, argtype), h)}复制代码
再来看第二个问题,如果使用var 进行变量声明之后,是否可以直接键值对赋值呢,slice进行声明之后就行啊,是不是map也可以?
var mapa map[string]int mapa["zhao"] = 1复制代码
运行报错:
panic: assignment to entry in nil mapgoroutine 1 [running]:main.main()/Users/zhaojunwei/workspace/src/just.for.test/maptest/demo.go:11 +0x4fexit status 2复制代码
但从错误信息上,我们可以得知,在nil数组上,进行分配操作。
0x002f 00047 (/Users/zhaojunwei/workspace/src/just.for.test/maptest/demo.go:9)MOVQ$0, "".mapa+56(SP)复制代码
var声明的map变量是一个nil map.
0x002f 00047 (/Users/zhaojunwei/workspace/src/just.for.test/maptest/demo.go:9)PCDATA$0, $10x002f 00047 (/Users/zhaojunwei/workspace/src/just.for.test/maptest/demo.go:9)MOVQ$0, "".mapa+56(SP)0x0038 00056 (/Users/zhaojunwei/workspace/src/just.for.test/maptest/demo.go:11)PCDATA$2, $10x0038 00056 (/Users/zhaojunwei/workspace/src/just.for.test/maptest/demo.go:11)LEAQtype.map[string]int(SB), AX0x003f 00063 (/Users/zhaojunwei/workspace/src/just.for.test/maptest/demo.go:11)PCDATA$2, $00x003f 00063 (/Users/zhaojunwei/workspace/src/just.for.test/maptest/demo.go:11)MOVQAX, (SP)0x0043 00067 (/Users/zhaojunwei/workspace/src/just.for.test/maptest/demo.go:11)MOVQ$0, 8(SP)0x004c 00076 (/Users/zhaojunwei/workspace/src/just.for.test/maptest/demo.go:11)PCDATA$2, $10x004c 00076 (/Users/zhaojunwei/workspace/src/just.for.test/maptest/demo.go:11)LEAQgo.string."zhao"(SB), AX0x0053 00083 (/Users/zhaojunwei/workspace/src/just.for.test/maptest/demo.go:11)PCDATA$2, $00x0053 00083 (/Users/zhaojunwei/workspace/src/just.for.test/maptest/demo.go:11)MOVQAX, 16(SP)0x0058 00088 (/Users/zhaojunwei/workspace/src/just.for.test/maptest/demo.go:11)MOVQ$4, 24(SP)0x0061 00097 (/Users/zhaojunwei/workspace/src/just.for.test/maptest/demo.go:11)CALLruntime.mapassign_faststr(SB)复制代码
在进行键值对赋值的操作上,调用的是CALLruntime.mapassign_faststr(SB)
func mapassign_faststr(t *maptype, h *hmap, s string) unsafe.Pointer {if h == nil {panic(plainError("assignment to entry in nil map"))}if raceenabled {callerpc := getcallerpc()racewritepc(unsafe.Pointer(h), callerpc, funcPC(mapassign_faststr))}if h.flags&hashWriting != 0 {throw("concurrent map writes")}// 计算key的hash值key := stringStructOf(&s)hash := t.key.alg.hash(noescape(unsafe.Pointer(&s)), uintptr(h.hash0))// Set hashWriting after calling alg.hash for consistency with mapassign.h.flags ^= hashWriting // 如果桶数组为空,分配长度为1的桶数组。if h.buckets == nil {h.buckets = newobject(t.bucket) // newarray(t.bucket, 1)}again: // 计算低 B 位 hash,根据计算出的 bucketMask 选择对应的 bucket // bucketMask returns 1<<h.B - 1bucket := hash & bucketMask(h.B)if h.growing() {growWork_faststr(t, h, bucket)}// 计算出存储的 bucket 的内存位置 // pos = start + bucketNumber * bucetsizeb := (*bmap)(unsafe.Pointer(uintptr(h.buckets) + bucket*uintptr(t.bucketsize)))// 计算高 8 位 hashtop := tophash(hash)var insertb *bmapvar inserti uintptrvar insertk unsafe.Pointerbucketloop:for {for i := uintptr(0); i < bucketCnt; i++ {if b.tophash[i] != top {if isEmpty(b.tophash[i]) && insertb == nil {insertb = binserti = i}if b.tophash[i] == emptyRest {break bucketloop}continue}k := (*stringStruct)(add(unsafe.Pointer(b), dataOffset+i*2*sys.PtrSize))if k.len != key.len {continue}if k.str != key.str && !memequal(k.str, key.str, uintptr(key.len)) {continue}// already have a mapping for key. Update it.inserti = iinsertb = bgoto done}ovf := b.overflow(t)if ovf == nil {break}b = ovf}// Did not find mapping for key. Allocate new cell & add entry.// If we hit the max load factor or we have too many overflow buckets,// and we're not already in the middle of growing, start growing.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 insertb == nil {// all current buckets are full, allocate a new one.insertb = h.newoverflow(t, b)inserti = 0 // not necessary, but avoids needlessly spilling inserti}insertb.tophash[inserti&(bucketCnt-1)] = top // mask inserti to avoid bounds checksinsertk = add(unsafe.Pointer(insertb), dataOffset+inserti*2*sys.PtrSize)// store new key at insert position*((*stringStruct)(insertk)) = *keyh.count++done:val := add(unsafe.Pointer(insertb), dataOffset+bucketCnt*2*sys.PtrSize+inserti*uintptr(t.valuesize))if h.flags&hashWriting == 0 {throw("concurrent map writes")}h.flags &^= hashWritingreturn val}复制代码
该函数首先判断的就是参数h的值是否为nil.也就是第二个参数,
0x0043 00067 (/Users/zhaojunwei/workspace/src/just.for.test/maptest/demo.go:11) MOVQ$0, 8(SP)复制代码
第三个问题,获取不到的key,如何处理
0x00c8 00200 (/Users/zhaojunwei/workspace/src/just.for.test/maptest/demo.go:26)PCDATA$0, $00x00c8 00200 (/Users/zhaojunwei/workspace/src/just.for.test/maptest/demo.go:26)MOVQ"".mapa+56(SP), AX0x00cd 00205 (/Users/zhaojunwei/workspace/src/just.for.test/maptest/demo.go:26)PCDATA$2, $00x00cd 00205 (/Users/zhaojunwei/workspace/src/just.for.test/maptest/demo.go:26)MOVQAX, 8(SP)0x00d2 00210 (/Users/zhaojunwei/workspace/src/just.for.test/maptest/demo.go:26)PCDATA$2, $10x00d2 00210 (/Users/zhaojunwei/workspace/src/just.for.test/maptest/demo.go:26)LEAQgo.string."li"(SB), AX0x00d9 00217 (/Users/zhaojunwei/workspace/src/just.for.test/maptest/demo.go:26)PCDATA$2, $00x00d9 00217 (/Users/zhaojunwei/workspace/src/just.for.test/maptest/demo.go:26)MOVQAX, 16(SP)0x00de 00222 (/Users/zhaojunwei/workspace/src/just.for.test/maptest/demo.go:26)MOVQ$2, 24(SP)0x00e7 00231 (/Users/zhaojunwei/workspace/src/just.for.test/maptest/demo.go:26)CALLruntime.mapaccess1_faststr(SB)0x00ec 00236 (/Users/zhaojunwei/workspace/src/just.for.test/maptest/demo.go:26)PCDATA$2, $10x00ec 00236 (/Users/zhaojunwei/workspace/src/just.for.test/maptest/demo.go:26)MOVQ32(SP), AX复制代码
获取键值,调用mapaccess1_faststr
函数,该函数第一个参数是type.map[string]int(SB)
,第二个参数就是我们的map变量.
0x00c8 00200 (/Users/zhaojunwei/workspace/src/just.for.test/maptest/demo.go:26)PCDATA$0, $00x00c8 00200 (/Users/zhaojunwei/workspace/src/just.for.test/maptest/demo.go:26)MOVQ"".mapa+56(SP), AX0x00cd 00205 (/Users/zhaojunwei/workspace/src/just.for.test/maptest/demo.go:26)PCDATA$2, $00x00cd 00205 (/Users/zhaojunwei/workspace/src/just.for.test/maptest/demo.go:26)MOVQAX, 8(SP)复制代码
第三个参数是key的string。
0x00d2 00210 (/Users/zhaojunwei/workspace/src/just.for.test/maptest/demo.go:26)PCDATA$2, $10x00d2 00210 (/Users/zhaojunwei/workspace/src/just.for.test/maptest/demo.go:26)LEAQgo.string."li"(SB), AX0x00d9 00217 (/Users/zhaojunwei/workspace/src/just.for.test/maptest/demo.go:26)PCDATA$2, $00x00d9 00217 (/Users/zhaojunwei/workspace/src/just.for.test/maptest/demo.go:26)MOVQAX, 16(SP)0x00de 00222 (/Users/zhaojunwei/workspace/src/just.for.test/maptest/demo.go:26)MOVQ$2, 24(SP)0x00e7 00231 (/Users/zhaojunwei/workspace/src/just.for.test/maptest/demo.go:26)CALLruntime.mapaccess1_faststr(SB)复制代码
调用mapaccess1_faststr
,该函数首先在桶数组中检查每个key,当前桶检查完毕后,继续溢出桶的检查,如果发现都没有这个key ,则返回一个unsafe.Pointer
的零值。
return unsafe.Pointer(&zeroVal[0])复制代码
如果发现了参数key,会返回该参数key对应的value地址。
0x00f6 00246 (/Users/zhaojunwei/workspace/src/just.for.test/maptest/demo.go:11)PCDATA$2, $00x00f6 00246 (/Users/zhaojunwei/workspace/src/just.for.test/maptest/demo.go:11)MOVQ$1, (AX)复制代码
然后把赋的值放到该寄存器中。
放一张曹大的一张关于map的全瞰图,更加明白map的底层结构
┌─────────────┐ │ hmap │ ├─────────────┴──────────────────┐ ┌───────────────┐ ┌─────────┐ ┌─────────┐ │ count int │ │ │ ┌─────────────────▶│ bmap │ ┌───▶│ bmap │ │ │ │ ▼ │ ├─────────┴─────────────────────┐ │ ├─────────┴─────────────────────┐ ├────────────────────────────────┤ │ ────────┬─────┐ │ │ tophash [bucketCnt]uint8 │ │ │ tophash [bucketCnt]uint8 │ │ flags uint8 │ │ ▲ │ 0 │ │ │ │ │ │ │ │ │ │ │ │ │──────────────────┘ ├──────────┬────────────────────┤ │ ├──────────┬────────────────────┤ ├────────────────────────────────┤ │ │ ├─────┤ │ keys │ │ │ │ keys │ │ │ B uint8 │ │ │ │ 1 │ ├───┬───┬──┴┬───┬───┬───┬───┬───┤ │ ├───┬───┬──┴┬───┬───┬───┬───┬───┤ │ │ │ │ │ │──────────────────┐ │ 0 │ 1 │ 2 │ 3 │ 4 │ 5 │ 6 │ 7 │ │ │ 0 │ 1 │ 2 │ 3 │ 4 │ 5 │ 6 │ 7 │ ├────────────────────────────────┤ │ │ ├─────┤ │ ├───┴───┴──┬┴───┴───┴───┴───┴───┤ │ ├───┴───┴──┬┴───┴───┴───┴───┴───┤ │ noverflow uint16 │ │ │ │ 2 │ │ │ values │ │ │ │ values │ │ │ │ │ │ │ │ │ ├───┬───┬──┴┬───┬───┬───┬───┬───┤ │ ├───┬───┬──┴┬───┬───┬───┬───┬───┤ ├────────────────────────────────┤ │ │ ├─────┤ │ │ 0 │ 1 │ 2 │ 3 │ 4 │ 5 │ 6 │ 7 │ │ │ 0 │ 1 │ 2 │ 3 │ 4 │ 5 │ 6 │ 7 │ │ hash0 uint32 │ │ │ │ 3 │ │ ├───┴───┴───┴───┴───┴───┴───┴───┤ │ ├───┴───┴───┴───┴───┴───┴───┴───┤ │ │ │ │ │ │ │ │ overflow *bmap │ │ │ overflow *bmap │ ├────────────────────────────────┤ │ │ ├─────┤ │ │ │────┘ │ │ │ buckets unsafe.Pointer │ │ │ │ 4 │ │ ├─────────┬─────────────────────┘ └───────────────────────────────┘ │ │───────────┘ │ │ │ └─────────────────▶│ bmap │ ├────────────────────────────────┤ ├─────┤ ├─────────┴─────────────────────┐ │ oldbuckets unsafe.Pointer │ │ 5 │ │ tophash [bucketCnt]uint8 │ │ │ │ │ │ │ ├────────────────────────────────┤ size = 2 ^ B ├─────┤ ├──────────┬────────────────────┤ │ nevacuate uintptr │ │ 6 │ │ keys │ │ │ │ │ │ ├───┬───┬──┴┬───┬───┬───┬───┬───┤ ├────────────────────────────────┤ │ ├─────┤ │ 0 │ 1 │ 2 │ 3 │ 4 │ 5 │ 6 │ 7 │ │ extra *mapextra │ │ │ 7 │ ├───┴───┴──┬┴───┴───┴───┴───┴───┤ ┌──│ │ │ │ │ │ values │ │ │ └────────────────────────────────┘ │ └─────┘ ├───┬───┬──┴┬───┬───┬───┬───┬───┤ │ │ .... │ 0 │ 1 │ 2 │ 3 │ 4 │ 5 │ 6 │ 7 │ │ │ ├───┴───┴───┴───┴───┴───┴───┴───┤ │ │ ┌─────┐ │ overflow *bmap │ │ │ │ 61 │ │ │ │ │ │ │ └───────────────────────────────┘ ▼ │ ├─────┤ ............ ┌─────────────┐ │ │ 62 │ ┌─────────┐ ┌─────────┐ ┌─────────┐ │ mapextra │ │ │ │────────────────────────────────────▶│ bmap │ ┌───▶│ bmap │ ┌───▶│ bmap │ ├─────────────┴──────────────┐ │ ├─────┤ ├─────────┴─────────────────────┐ │ ├─────────┴─────────────────────┐ │ ├─────────┴─────────────────────┐│ overflow *[]*bmap │ │ │ 63 │ │ tophash [bucketCnt]uint8 │ │ │ tophash [bucketCnt]uint8 │ │ │ tophash [bucketCnt]uint8 ││ │ ▼ │ │──────────────────┐ │ │ │ │ │ │ │ │├────────────────────────────┤ ────────┴─────┘ │ ├──────────┬────────────────────┤ │ ├──────────┬────────────────────┤ │ ├──────────┬────────────────────┤│ oldoverflow *[]*bmap │ │ │ keys │ │ │ │ keys │ │ │ │ keys │ ││ │ │ ├───┬───┬──┴┬───┬───┬───┬───┬───┤ │ ├───┬───┬──┴┬───┬───┬───┬───┬───┤ │ ├───┬───┬──┴┬───┬───┬───┬───┬───┤├────────────────────────────┤ │ │ 0 │ 1 │ 2 │ 3 │ 4 │ 5 │ 6 │ 7 │ │ │ 0 │ 1 │ 2 │ 3 │ 4 │ 5 │ 6 │ 7 │ │ │ 0 │ 1 │ 2 │ 3 │ 4 │ 5 │ 6 │ 7 ││ nextoverflow *bmap │ │ ├───┴───┴──┬┴───┴───┴───┴───┴───┤ │ ├───┴───┴──┬┴───┴───┴───┴───┴───┤ │ ├───┴───┴──┬┴───┴───┴───┴───┴───┤│ │ │ │ values │ │ │ │ values │ │ │ │ values │ │└────────────────────────────┘ │ ├───┬───┬──┴┬───┬───┬───┬───┬───┤ │ ├───┬───┬──┴┬───┬───┬───┬───┬───┤ │ ├───┬───┬──┴┬───┬───┬───┬───┬───┤ │ │ 0 │ 1 │ 2 │ 3 │ 4 │ 5 │ 6 │ 7 │ │ │ 0 │ 1 │ 2 │ 3 │ 4 │ 5 │ 6 │ 7 │ │ │ 0 │ 1 │ 2 │ 3 │ 4 │ 5 │ 6 │ 7 │ │ ├───┴───┴───┴───┴───┴───┴───┴───┤ │ ├───┴───┴───┴───┴───┴───┴───┴───┤ │ ├───┴───┴───┴───┴───┴───┴───┴───┤ │ │ overflow *bmap │ │ │ overflow *bmap │ │ │ overflow *bmap │ │ │ │────┘ │ │───┘ │ │ │ ├─────────┬─────────────────────┘ └───────────────────────────────┘ └───────────────────────────────┘ └─────────────────▶│ bmap │ ├─────────┴─────────────────────┐ │ tophash [bucketCnt]uint8 │ │ │ ├──────────┬────────────────────┤ │ keys │ │ ├───┬───┬──┴┬───┬───┬───┬───┬───┤ │ 0 │ 1 │ 2 │ 3 │ 4 │ 5 │ 6 │ 7 │ ├───┴───┴──┬┴───┴───┴───┴───┴───┤ │ values │ │ ├───┬───┬──┴┬───┬───┬───┬───┬───┤ │ 0 │ 1 │ 2 │ 3 │ 4 │ 5 │ 6 │ 7 │ ├───┴───┴───┴───┴───┴───┴───┴───┤ │ overflow *bmap │ │ │ └───────────────────────────────┘ 复制代码
最后一个问题,有关数组的扩容问题。我们初始时make(map, 10),其底层的桶数组长度为2。每个桶能容纳的键值对为8个,也就是说,我们的桶数组用完了,也只能存储16个键值对,但是,其触发扩容时机大致在什么时候呢?还要再看看runtime.mapassign_faststr
.
// overLoadFactor reports whether count items placed in 1<<B buckets is over loadFactor.func overLoadFactor(count int, B uint8) bool {return count > bucketCnt && uintptr(count) > loadFactorNum*(bucketShift(B)/loadFactorDen)}// tooManyOverflowBuckets reports whether noverflow buckets is too many for a map with 1<<B buckets.// Note that most of these overflow buckets must be in sparse use;// if use was dense, then we'd have already triggered regular map growth.func tooManyOverflowBuckets(noverflow uint16, B uint8) bool {// If the threshold is too low, we do extraneous work.// If the threshold is too high, maps that grow and shrink can hold on to lots of unused memory.// "too many" means (approximately) as many overflow buckets as regular buckets.// See incrnoverflow for more details.if B > 15 {B = 15}// The compiler doesn't see here that B < 16; mask B to generate shorter shift code.return noverflow >= uint16(1)<<(B&15)}// growing reports whether h is growing. The growth may be to the same size or bigger.func (h *hmap) growing() bool {return h.oldbuckets != nil}func mapassign_faststr(t *maptype, h *hmap, s string) unsafe.Pointer {...// Did not find mapping for key. Allocate new cell & add entry.// If we hit the max load factor or we have too many overflow buckets,// and we're not already in the middle of growing, start growing.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}...}复制代码
如果达到了最大的负载因子,或者我们有太多的溢出桶,同时并没有在扩容,那么就开始扩容。计算过程,len(map)>8 && len(map)>6.5*(1<<B)
就会达到最大负载因子。hmap的noverflow
字段是用来记录溢出桶个数的,当溢出桶个数达到uint16(1)<<(B&15)
本示例中,B=1,如果溢出桶的数量大于等于2,也就认为溢出桶过多,也会触发响应的扩容。
两种情况官方采用了不同的扩容方案:
达到最大负载因子,将 B + 1,进而 hmap 的 bucket 数组扩容一倍;有太多的溢出桶,通过移动 bucket 内容,使其倾向于紧密排列从而提高 bucket 利用率。
最终的哈希表的数据复制是由growWork()
和 evacuate()
来进行的。
当然,有关map的内容,还有很多,越深入越发现其实自己的知识储备还有很大的进步空间,更多详细内容,欢迎去曹大github上学习探究。有任何问题,欢迎留言。。。。
参考文献:
文章来源:智云一二三科技
文章标题:我可能并不会使用golang map
文章地址:https://www.zhihuclub.com/433.shtml