阅读 987

我可能并不会使用golang map

package main

import (
    "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 	PCDATA	$2, $1
	0x0050 00080 	LEAQ	type.map[string]int(SB), AX
	0x0057 00087 	PCDATA	$2, $0
	0x0057 00087 	MOVQ	AX, (SP)
	0x005b 00091 	MOVQ	$10, 8(SP)
	0x0064 00100 	PCDATA	$2, $1
	0x0064 00100 	PCDATA	$0, $0
	0x0064 00100 	LEAQ	""..autotmp_2+136(SP), AX
	0x006c 00108 	PCDATA	$2, $0
	0x006c 00108 	MOVQ	AX, 16(SP)
	0x0071 00113 	CALL	runtime.makemap(SB)
	0x0076 00118 	PCDATA	$2, $1
	0x0076 00118 	MOVQ	24(SP), AX
	0x007b 00123 	PCDATA	$0, $2
	0x007b 00123 	MOVQ	AX, "".mapa+56(SP)
复制代码

执行的makemap调用,我们看看这个函数的参数和返回值情况,第一个参数是type.map[string]int(SB),第二个参数是10,第三个参数很有意思

0x0064 00100 	PCDATA	$0, $0
	0x0064 00100 	LEAQ	""..autotmp_2+136(SP), AX
	0x006c 00108 	PCDATA	$2, $0
	0x006c 00108 	MOVQ	AX, 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 Hmap
	if 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 *bmap
		h.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 = 3
	bucketCnt     = 1 << bucketCntBits
	...
)
// A header for a Go map.
type hmap struct {
	count     int // 元素个数,必须位于第一项,调用 len(map) 时,直接返回此值
	flags     uint8
	B         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 = 13
	loadFactorDen = 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 * nbuckets
		up := 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 = dirtyalloc
		size := t.bucket.size * nbuckets
		if 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 // 0
	flags     uint8
	B         uint8  // 1
	noverflow 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 	PCDATA	$0, $1
	0x0032 00050 	XORPS	X1, X1
	0x0035 00053 	MOVUPS	X1, ""..autotmp_3+136(SP)
	0x003d 00061 	XORPS	X1, X1
	0x0040 00064 	MOVUPS	X1, ""..autotmp_3+152(SP)
	0x0048 00072 	XORPS	X1, X1
	0x004b 00075 	MOVUPS	X1, ""..autotmp_3+168(SP)
	0x0053 00083 	PCDATA	$2, $1
	0x0053 00083 	PCDATA	$0, $2
	0x0053 00083 	LEAQ	""..autotmp_4+184(SP), DI
	0x005b 00091 	XORPS	X0, X0
	0x005e 00094 	PCDATA	$2, $0
	0x005e 00094 	LEAQ	-48(DI), DI
	0x0062 00098 	DUFFZERO	$239
	0x0075 00117 	PCDATA	$2, $2
	0x0075 00117 	LEAQ	""..autotmp_3+136(SP), AX
	0x007d 00125 	PCDATA	$2, $0
	0x007d 00125 	TESTB	AL, (AX)
	0x007f 00127 	PCDATA	$2, $2
	0x007f 00127 	PCDATA	$0, $1
	0x007f 00127 	LEAQ	""..autotmp_4+184(SP), AX
	0x0087 00135 	PCDATA	$2, $0
	0x0087 00135 	MOVQ	AX, ""..autotmp_3+152(SP)
	0x008f 00143 	PCDATA	$2, $2
	0x008f 00143 	LEAQ	""..autotmp_3+136(SP), AX
	0x0097 00151 	PCDATA	$2, $0
	0x0097 00151 	PCDATA	$0, $3
	0x0097 00151 	MOVQ	AX, ""..autotmp_5+88(SP)
	0x009c 00156 	CALL	runtime.fastrand(SB)
	0x00a1 00161 	PCDATA	$2, $2
	0x00a1 00161 	PCDATA	$0, $1
	0x00a1 00161 	MOVQ	""..autotmp_5+88(SP), AX
	0x00a6 00166 	TESTB	AL, (AX)
	0x00a8 00168 	MOVL	(SP), CX
	0x00ab 00171 	PCDATA	$2, $0
	0x00ab 00171 	MOVL	CX, 12(AX)
	0x00ae 00174 	PCDATA	$2, $2
	0x00ae 00174 	PCDATA	$0, $0
	0x00ae 00174 	LEAQ	""..autotmp_3+136(SP), AX
	0x00b6 00182 	PCDATA	$2, $0
	0x00b6 00182 	PCDATA	$0, $4
	0x00b6 00182 	MOVQ	AX, "".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.Type
		hmapType := hmap(t)
		hint := n.Left

		// var h *hmap
		var h *Node
		if n.Esc == EscNone {
			// Allocate hmap on stack.

			// var hv hmap
			hv := temp(hmapType)
			zero := nod(OAS, hv, nil)
			zero = typecheck(zero, ctxStmt)
			init.Append(zero)
			// h = &hv
			h = 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 bmap
				bv := temp(bmap(t))

				zero = nod(OAS, bv, nil)
				zero = typecheck(zero, ctxStmt)
				init.Append(zero)

				// b = &bv
				b := nod(OADDR, bv, nil)

				// h.buckets = b
				bsym := hmapType.Field(5).Sym // hmap.buckets see reflect.go:hmap
				na := 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:hmap
				a := 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 map

goroutine 1 [running]:
main.main()
	/Users/zhaojunwei/workspace/src/just.for.test/maptest/demo.go:11 +0x4f
exit status 2
复制代码

但从错误信息上,我们可以得知,在nil数组上,进行分配操作。

	0x002f 00047 	MOVQ	$0, "".mapa+56(SP)
复制代码

var声明的map变量是一个nil map.

0x002f 00047 	PCDATA	$0, $1
	0x002f 00047 	MOVQ	$0, "".mapa+56(SP)
	0x0038 00056 	PCDATA	$2, $1
	0x0038 00056 	LEAQ	type.map[string]int(SB), AX
	0x003f 00063 	PCDATA	$2, $0
	0x003f 00063 	MOVQ	AX, (SP)
	0x0043 00067 	MOVQ	$0, 8(SP)
	0x004c 00076 	PCDATA	$2, $1
	0x004c 00076 	LEAQ	go.string."zhao"(SB), AX
	0x0053 00083 	PCDATA	$2, $0
	0x0053 00083 	MOVQ	AX, 16(SP)
	0x0058 00088 	MOVQ	$4, 24(SP)
	0x0061 00097 	CALL	runtime.mapassign_faststr(SB)
复制代码

在进行键值对赋值的操作上,调用的是CALL runtime.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 - 1
	bucket := hash & bucketMask(h.B)
	if h.growing() {
		growWork_faststr(t, h, bucket)
	}
	// 计算出存储的 bucket 的内存位置
    // pos = start + bucketNumber * bucetsize
	b := (*bmap)(unsafe.Pointer(uintptr(h.buckets) + bucket*uintptr(t.bucketsize)))
	// 计算高 8 位 hash
	top := tophash(hash)

	var insertb *bmap
	var inserti uintptr
	var insertk unsafe.Pointer

bucketloop:
	for {
		for i := uintptr(0); i < bucketCnt; i++ {
			if b.tophash[i] != top {
				if isEmpty(b.tophash[i]) && insertb == nil {
					insertb = b
					inserti = 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 = i
			insertb = b
			goto 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 checks

	insertk = add(unsafe.Pointer(insertb), dataOffset+inserti*2*sys.PtrSize)
	// store new key at insert position
	*((*stringStruct)(insertk)) = *key
	h.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 &^= hashWriting
	return val
}
复制代码

该函数首先判断的就是参数h的值是否为nil.也就是第二个参数,

	0x0043 00067  MOVQ	$0, 8(SP)
复制代码

第三个问题,获取不到的key,如何处理

	0x00c8 00200 	PCDATA	$0, $0
	0x00c8 00200 	MOVQ	"".mapa+56(SP), AX
	0x00cd 00205 	PCDATA	$2, $0
	0x00cd 00205 	MOVQ	AX, 8(SP)
	0x00d2 00210 	PCDATA	$2, $1
	0x00d2 00210 	LEAQ	go.string."li"(SB), AX
	0x00d9 00217 	PCDATA	$2, $0
	0x00d9 00217 	MOVQ	AX, 16(SP)
	0x00de 00222 	MOVQ	$2, 24(SP)
	0x00e7 00231 	CALL	runtime.mapaccess1_faststr(SB)
	0x00ec 00236 	PCDATA	$2, $1
	0x00ec 00236 	MOVQ	32(SP), AX
复制代码

获取键值,调用mapaccess1_faststr函数,该函数第一个参数是type.map[string]int(SB),第二个参数就是我们的map变量.

	0x00c8 00200 	PCDATA	$0, $0
	0x00c8 00200 	MOVQ	"".mapa+56(SP), AX
	0x00cd 00205 	PCDATA	$2, $0
	0x00cd 00205 	MOVQ	AX, 8(SP)
复制代码

第三个参数是key的string。

0x00d2 00210 	PCDATA	$2, $1
	0x00d2 00210 	LEAQ	go.string."li"(SB), AX
	0x00d9 00217 	PCDATA	$2, $0
	0x00d9 00217 	MOVQ	AX, 16(SP)
	0x00de 00222 	MOVQ	$2, 24(SP)
	0x00e7 00231 	CALL	runtime.mapaccess1_faststr(SB)
复制代码

调用mapaccess1_faststr,该函数首先在桶数组中检查每个key,当前桶检查完毕后,继续溢出桶的检查,如果发现都没有这个key ,则返回一个unsafe.Pointer的零值。

return unsafe.Pointer(&zeroVal[0])
复制代码

如果发现了参数key,会返回该参数key对应的value地址。

	0x00f6 00246 	PCDATA	$2, $0
	0x00f6 00246 	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上学习探究。有任何问题,欢迎留言。。。。

本系列文章:

有任何问题,欢迎留言

参考文献:

关注下面的标签,发现更多相似文章
评论