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"])
}
Copy the codeLooking at the above examples, we may have the following questions:
- 1. Create a map using the make parameter 10. How about not providing it?
- 2. Can the map declared by the commented var be directly assigned?
- 3. What happens if I get a nonexistent key?
- 4. The last final question: when should I expand the array after I run out of the underlying array?
Wait, maybe you have some other questions, but let’s start with a few of them
Let’s look at what happens when make creates a map with the parameter 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)Copy the codeMap [string]int(SB). The second parameter is 10. The third parameter is interesting
0x0064 00100 PCDATA $0, $0 0x0064 00100 LEAQ "".. autotmp_2+136(SP), AX 0x006c 00108 PCDATA $2, $0 0x006c 00108 MOVQ AX, 16(SP)Copy the codeWhatever it is, let’s take a look at the prototype of the Makemap function
// If the compiler determines the map or the first bucket, it can be created on the stack, and h and/or bucket can be non-nil. // If h is not nil, the map can be created directly in h. // If h.buckets is not nil, the bucket pointer can be used as the first 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 }Copy the codeFrom the prototype, the third argument is an Hmap pointer, what is this thing, if h is nil, you need a new one?
BucketCntBits = 3 bucketCnt = 1 << bucketCntBits... // A header for A Go map. type hmap struct {count int (1) Uint8 B uint8 // B is the logarithm base 2 of buckets (Can contain loadFactor * 2^B elements) Noverflow Uint16 // The number of buckets that overflow hash0 uint32 // Buckets unsafe.Pointer // Data storage buckets oldbuckets Unsafe.Pointer // The bucket before expansion is not empty only during expansion. nevacuate uintptr // progress counter for evacuation (buckets less than this have been evacuated) extra *mapextra // Type bmap struct {// TopHash usually contains the highest byte (8 bits) of the hash value for each key in the bucket topHash [bucketCnt]uint8 // 8-byte long array // And then the key for the number of bucketCnTs, and then the value for the number of bucketCnTs. // Followed by an overflow pointer. }Copy the codeThe overLoadFactor function is prototyped as
const ( ... // The maximum average load of the buckets that trigger growth is 6.5. // represents loadFactorNum/loadFactDen to allow integer math. loadFactorNum = 13 loadFactorDen = 2 ... ) // bucketShift returns 1 << b, optimized for code generation. 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 reports count items placed in bucket 1<<B, Func overLoadFactor(count int, B uint8) bool { return count > bucketCnt && uintptr(count) > loadFactorNum*(bucketShift(B)/loadFactorDen) }Copy the codeCheck whether count is greater than bucketCnt. In this example, count is the hint, which is the parameter passed in. BucketCnt is the maximum key-value pair that a bucket can hold, which is 8. If the condition is true, continue to check if count is greater than 6.5*(1<
In the Makemap function, an overLoadFactor loop is performed before assigning the B value of h, and the final B value is determined to be 1. B is the logarithm base 2 of the buckets array (loadFactor * 2^B). If B is not 0, the bucket array will be allocated
// makeBucketArray initializes the underlying array of the map store. // if dirtyalloc is nil, a new bucket array will be allocated. If dirtyalloc is nil, a new bucket array will be allocated. Func makeBucketArray(t * mapType, b uint8, dirtyalloc unsafe.Pointer) (buckets unsafe.Pointer, NextOverflow *bmap) {base := bucketShift(b) nbuckets := base // For little B, overflow buckets are unlikely. Avoid computational overhead. 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 }Copy the codeWhen it’s first called, the dirtyalloc argument is nil, it creates an array for the first time
if dirtyalloc == nil {
buckets = newarray(t.bucket, int(nbuckets))
}
Copy the codeMapa := make(map[string]int, 10) make(map[string]int, 10)
Type hmap struct {count int // 0 flags uint8 B uint8 // 1 noverflow uint16 Unsafe.Pointer // Data storage bucket oldbuckets unsafe.Pointer // The bucket before expansion is not empty only during expansion. Nevacuate uintptr extra * mapEXTRACopy the codeIf it’s 10, then B is 1, and two buckets are allocated, and each bucket has eight pairs, which is enough. If it’s 20, then B is 2, and the bottom bucket is allocated four buckets. If the parameter is 5 and the value of B is 1, allocate two buckets…
Of course, if make() creates the map without providing the second parameter, you will notice that makemap’s function call will not be seen after assembly if the parameter is smaller than bucketCnt.
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)Copy the codeAs you can see, the makemap function call is not visible until the MAPA assignment operation. May be the only call fastrand. Compiler determine the make the location of the map function: 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) }Copy the codeIf we use var to declare variables, can we assign values to each other directly? If we use slice to declare variables, can we assign values to each other directly?
var mapa map[string]int
mapa["zhao"] = 1
Copy the codeOperation error:
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
Copy the codeBut we know from the error message that we’re doing allocation on a nil array.
0x002f 00047 MOVQ $0, "".mapa+56(SP)
Copy the codeVar declares a map variable as a 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)
Copy the codeCALL 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 := 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 // If the bucket array is empty, allocate a bucket array of length 1. if h.buckets == nil { h.buckets = newobject(t.bucket) // newarray(t.bucket, 1) } again: // Compute the low b-bit hash, // bucketMask returns 1<< H.b-1 bucket := Hash & bucketMask(h.B) if H.g rowing() {// bucketMask returns 1<< H.b-1 bucket := hash & bucketMask(h.B) if H.g rowing() { growWork_faststr(t, h, Pos = start + bucketNumber * bucetSize b := (*bmap)(unsafe.pointer (uintptr(h.buckkets) + bucket*uintptr(t.bucksize))) // Calculate high 8-bit 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 }Copy the codeThe first thing this function checks is if the value of h is nil. The second argument,
0x0043 00067 MOVQ $0, 8(SP)
Copy the codeThe third question is, how to deal with keys that cannot be obtained
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
Copy the codeMap [string]int(SB). The second argument is our map variable.
0x00c8 00200 PCDATA $0, $0
0x00c8 00200 MOVQ "".mapa+56(SP), AX
0x00cd 00205 PCDATA $2, $0
0x00cd 00205 MOVQ AX, 8(SP)
Copy the codeThe third argument is the string of the key.
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)
Copy the codeCalling mapAccess1_faststr, this function checks each key in the bucket array. After checking the current bucket, it checks the overflow bucket. If no key is found, it returns a zero value of unsafe.Pointer.
return unsafe.Pointer(&zeroVal[0])
Copy the codeIf the key parameter is found, the value address corresponding to the key parameter is returned.
0x00f6 00246 PCDATA $2, $0
0x00f6 00246 MOVQ $1, (AX)
Copy the codeThe assigned value is then placed in the register.
Put a full view of map by Cao Da to better understand the underlying structure of map
┌ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┐ │ hmap │ ├ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┴ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┐ ┌ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┐ ┌ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┐ ┌ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┐ │ count int │ │ │ ┌ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ▶ │ bmap │ ┌ ─ ─ ─ ▶ │ bmap │ │ │ │ ▼ │ ├ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┴ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┐ │ ├ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┴ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┐ ├ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┤ │ ─ ─ ─ ─ ─ ─ ─ ─ ┬ ─ ─ ─ ─ ─ ┐ │ │ tophash [bucketCnt] uint8 │ │ │ tophash [bucketCnt] uint8 │ │ flags uint8 │ │ bring │ 0 │ │ │ │ │ │ │ │ │ │ │ │ │ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┘ ├ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┬ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┤ │ ├ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┬ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┤ ├ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┤ │ │ ├ ─ ─ ─ ─ ─ ┤ │ Keys │ │ │ │ keys │ │ │ B uint8 │ │ │ │ │ 1 ├ ─ ─ ─ ┬ ─ ─ ─ ┬ ─ ─ ┴ ┬ ─ ─ ─ ┬ ─ ─ ─ ┬ ─ ─ ─ ┬ ─ ─ ─ ┬ ─ ─ ─ ┤ │ ├ ─ ─ ─ ┬ ─ ─ ─ ┬ ─ ─ ┴ ┬ ─ ─ ─ ┬ ─ ─ ─ ┬ ─ ─ ─ ┬ ─ ─ ─ ┬ ─ ─ ─ ┤ │ │ │ │ │ │ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┐ │ │ │ │ 0 1 2 3 4 5 6 7 │ │ │ │ │ │ │ │ │ │ 0 1 2 3 4 5 6 7 │ │ │ │ │ ├ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┤ │ │ ├ ─ ─ ─ ─ ─ ┤ │ ├ ─ ─ ─ ┴ ─ ─ ─ ┴ ─ ─ ┬ ┴ ─ ─ ─ ┴ ─ ─ ─ ┴ ─ ─ ─ ┴ ─ ─ ─ ┴ ─ ─ ─ ┤ │ ├ ─ ─ ─ ┴ ─ ─ ─ ┴ ─ ─ ┬ ┴ ─ ─ ─ ┴ ─ ─ ─ ┴ ─ ─ ─ ┴ ─ ─ ─ ┴ ─ ─ ─ ┤ │ 2 noverflow uint16 │ │ │ │ │ │ │ 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. The Pointer │ │ │ │ 4 │ │ ├ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┬ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┘ └ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┘ │ │ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┘ │ │ │ └ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ▶ │ bmap │ ├ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┤ ├ ─ ─ ─ ─ ─ ┤ ├ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┴ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┐ │ oldbuckets unsafe. The 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 │ │ │ │ │ │ │ │ │ │ │ 3 2 1 0 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 │ │ │ └ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┘Copy the codeThe last question is about expanding arrays. We start with make(map, 10), whose underlying bucket array is of length 2. Each bucket can hold 8 key-value pairs. That is to say, when our bucket array is used up, we can only store 16 key-value pairs. However, when will the capacity expansion be triggered? Also look at 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 } ... }Copy the codeIf the maximum load factor is reached, or if we have too many overflowing buckets and are not expanding, start expanding. Len (map)>8 && Len (map)>6.5*(1<
In the two cases, different expansion schemes were adopted:
To reach the maximum load factor, double the bucket array of B + 1 and then HMAP; There are too many overflowing buckets, and bucket utilization can be improved by moving bucket contents so that they tend to be packed together.
The final data replication of the hash table is done by growWork() and evacuate().
Built-in functions for map:
- 1, delete
// The delete function deletes the map element with the specified key. Func delete(m map[Type]Type1, key Type) func delete(m map[Type]Type1, key Type)Copy the code- 2.len
// The len built-in function returns the length of v, according to its type: // Array: the number of elements in v. // Pointer to array: the number of elements in *v (even if v is nil). // Slice, or map: The number of elements in v; If v is nil, len(v) returns 0. // String: The number of bytes in v. // Channel: the number of elements queued (unread) in the channel buffer; // if v is nil, len(v) is zero. // For some arguments, such as a string literal or a simple array expression, the // result can be a constant. See the Go language specification's "Length and // capacity" section for details. func len(v Type) intCopy the code- 3.make
// The make built-in function allocates and initializes an object of type // slice, map, or chan (only). Like new, the first argument is a type, not a // value. Unlike new, make's return type is the same as the type of its // argument, not a pointer to it. The specification of the result depends on // the type: // Slice: The size specifies the length. The capacity of the slice is // equal to its length. A second integer argument may be provided to // specify a different capacity; it must be no smaller than the // length. For example, make([]int, 0, 10) allocates an underlying array // of size 10 and returns a slice of length 0 and capacity 10 that is // backed by // Map: Allocates an empty Map that can hold a specified number of elements. Size can be omitted. When omitted, allocate a map // Channel that minimizes size: The channel's buffer is initialized with the specified // buffer capacity. If zero, or the size is omitted, the channel is // unbuffered. func make(t Type, size ... IntegerType) TypeCopy the codeOf course, there is still a lot of content about MAP. The more I go into it, the more I find that there is still a lot of room for improvement in my knowledge reserve. For more details, please go to Github of Cao University to study and explore. Any questions, please leave a comment…
Articles in this series:
- I probably wouldn’t use Golang slice
- I probably wouldn’t use Golang’s map
- I probably wouldn’t use Golang’s channel
- I probably wouldn’t use Golang’s Goroutines
If you have any questions, please leave a comment
References:
- Golang notes by Cao Da