关于golang:遍历Map源码分析-GO1162

49次阅读

共计 15735 个字符,预计需要花费 40 分钟才能阅读完成。

代码

func MapTest() {var aMap = map[int64]int64{
        1: 10,
        2: 20,
        3: 30,
    }
    for k, v := range aMap {fmt.Println(k, v)
    }
}

编译

go tool compile -N -l -S ./test_map.go >  ./test_map.s

汇编后果

"".MapTest STEXT size=912 args=0x0 locals=0x208 funcid=0x0
    0x0000 00000 (./test_map.go:13)    TEXT    "".MapTest(SB), ABIInternal, $520-0
    0x0000 00000 (./test_map.go:13)    MOVQ    (TLS), CX
    0x0009 00009 (./test_map.go:13)    LEAQ    -392(SP), AX
    0x0011 00017 (./test_map.go:13)    CMPQ    AX, 16(CX)
    0x0015 00021 (./test_map.go:13)    PCDATA    $0, $-2
    0x0015 00021 (./test_map.go:13)    JLS    902
    0x001b 00027 (./test_map.go:13)    PCDATA    $0, $-1
    0x001b 00027 (./test_map.go:13)    SUBQ    $520, SP
    0x0022 00034 (./test_map.go:13)    MOVQ    BP, 512(SP)
    0x002a 00042 (./test_map.go:13)    LEAQ    512(SP), BP
    0x0032 00050 (./test_map.go:13)    FUNCDATA    $0, gclocals·3e27b3aa6b89137cce48b3379a2a6610(SB)
    0x0032 00050 (./test_map.go:13)    FUNCDATA    $1, gclocals·4b48a54b979a44c0a517bad5b8d15a09(SB)
    0x0032 00050 (./test_map.go:13)    FUNCDATA    $2, "".MapTest.stkobj(SB)
    0x0032 00050 (./test_map.go:14)    MOVQ    $0, "".b+224(SP)
    0x003e 00062 (./test_map.go:15)    XORPS    X1, X1
    0x0041 00065 (./test_map.go:15)    MOVUPS    X1, ""..autotmp_7+368(SP)
    0x0049 00073 (./test_map.go:15)    MOVUPS    X1, ""..autotmp_7+384(SP)
    0x0051 00081 (./test_map.go:15)    MOVUPS    X1, ""..autotmp_7+400(SP)
    0x0059 00089 (./test_map.go:15)    LEAQ    ""..autotmp_8+80(SP), DI
    0x005e 00094 (./test_map.go:15)    XORPS    X0, X0
    0x0061 00097 (./test_map.go:15)    PCDATA    $0, $-2
    0x0061 00097 (./test_map.go:15)    LEAQ    -48(DI), DI
    0x0065 00101 (./test_map.go:15)    DUFFZERO    $258
    0x0078 00120 (./test_map.go:15)    PCDATA    $0, $-1
    0x0078 00120 (./test_map.go:15)    LEAQ    ""..autotmp_7+368(SP), AX
    0x0080 00128 (./test_map.go:15)    MOVQ    AX, ""..autotmp_9+240(SP)
    0x0088 00136 (./test_map.go:15)    TESTB    AL, (AX)
    0x008a 00138 (./test_map.go:15)    LEAQ    ""..autotmp_8+80(SP), AX
    0x008f 00143 (./test_map.go:15)    MOVQ    AX, ""..autotmp_7+384(SP)
    0x0097 00151 (./test_map.go:15)    LEAQ    ""..autotmp_7+368(SP), AX
    0x009f 00159 (./test_map.go:15)    MOVQ    AX, ""..autotmp_10+304(SP)
    0x00a7 00167 (./test_map.go:15)    PCDATA    $1, $1
    0x00a7 00167 (./test_map.go:15)    CALL    runtime.fastrand(SB)
    0x00ac 00172 (./test_map.go:15)    MOVQ    ""..autotmp_10+304(SP), AX
    0x00b4 00180 (./test_map.go:15)    TESTB    AL, (AX)
    0x00b6 00182 (./test_map.go:15)    MOVL    (SP), CX
    0x00b9 00185 (./test_map.go:15)    MOVL    CX, 12(AX)
    0x00bc 00188 (./test_map.go:15)    LEAQ    ""..autotmp_7+368(SP), AX
    0x00c4 00196 (./test_map.go:15)    MOVQ    AX, "".aMap+232(SP)
    0x00cc 00204 (./test_map.go:16)    MOVQ    $1, ""..autotmp_11+72(SP)
    0x00d5 00213 (./test_map.go:16)    MOVQ    $10, ""..autotmp_12+64(SP)
    0x00de 00222 (./test_map.go:16)    MOVQ    ""..autotmp_11+72(SP), AX
    0x00e3 00227 (./test_map.go:16)    MOVQ    "".aMap+232(SP), CX
    0x00eb 00235 (./test_map.go:16)    LEAQ    type.map[int64]int64(SB), DX
    0x00f2 00242 (./test_map.go:16)    MOVQ    DX, (SP)
    0x00f6 00246 (./test_map.go:16)    MOVQ    CX, 8(SP)
    0x00fb 00251 (./test_map.go:16)    MOVQ    AX, 16(SP)
    0x0100 00256 (./test_map.go:16)    PCDATA    $1, $2
    0x0100 00256 (./test_map.go:16)    CALL    runtime.mapassign_fast64(SB)
    0x0105 00261 (./test_map.go:16)    MOVQ    24(SP), AX
    0x010a 00266 (./test_map.go:16)    MOVQ    AX, ""..autotmp_13+296(SP)
    0x0112 00274 (./test_map.go:16)    TESTB    AL, (AX)
    0x0114 00276 (./test_map.go:16)    MOVQ    ""..autotmp_12+64(SP), CX
    0x0119 00281 (./test_map.go:16)    MOVQ    CX, (AX)
    0x011c 00284 (./test_map.go:17)    MOVQ    $2, ""..autotmp_11+72(SP)
    0x0125 00293 (./test_map.go:17)    MOVQ    $20, ""..autotmp_12+64(SP)
    0x012e 00302 (./test_map.go:17)    MOVQ    ""..autotmp_11+72(SP), AX
    0x0133 00307 (./test_map.go:17)    MOVQ    "".aMap+232(SP), CX
    0x013b 00315 (./test_map.go:17)    LEAQ    type.map[int64]int64(SB), DX
    0x0142 00322 (./test_map.go:17)    MOVQ    DX, (SP)
    0x0146 00326 (./test_map.go:17)    MOVQ    CX, 8(SP)
    0x014b 00331 (./test_map.go:17)    MOVQ    AX, 16(SP)
    0x0150 00336 (./test_map.go:17)    CALL    runtime.mapassign_fast64(SB)
    0x0155 00341 (./test_map.go:17)    MOVQ    24(SP), AX
    0x015a 00346 (./test_map.go:17)    MOVQ    AX, ""..autotmp_14+288(SP)
    0x0162 00354 (./test_map.go:17)    TESTB    AL, (AX)
    0x0164 00356 (./test_map.go:17)    MOVQ    ""..autotmp_12+64(SP), CX
    0x0169 00361 (./test_map.go:17)    MOVQ    CX, (AX)
    0x016c 00364 (./test_map.go:18)    MOVQ    $3, ""..autotmp_11+72(SP)
    0x0175 00373 (./test_map.go:18)    MOVQ    $30, ""..autotmp_12+64(SP)
    0x017e 00382 (./test_map.go:18)    MOVQ    ""..autotmp_11+72(SP), AX
    0x0183 00387 (./test_map.go:18)    MOVQ    "".aMap+232(SP), CX
    0x018b 00395 (./test_map.go:18)    LEAQ    type.map[int64]int64(SB), DX
    0x0192 00402 (./test_map.go:18)    MOVQ    DX, (SP)
    0x0196 00406 (./test_map.go:18)    MOVQ    CX, 8(SP)
    0x019b 00411 (./test_map.go:18)    MOVQ    AX, 16(SP)
    0x01a0 00416 (./test_map.go:18)    CALL    runtime.mapassign_fast64(SB)
    0x01a5 00421 (./test_map.go:18)    MOVQ    24(SP), AX
    0x01aa 00426 (./test_map.go:18)    MOVQ    AX, ""..autotmp_15+280(SP)
    0x01b2 00434 (./test_map.go:18)    TESTB    AL, (AX)
    0x01b4 00436 (./test_map.go:18)    MOVQ    ""..autotmp_12+64(SP), CX
    0x01b9 00441 (./test_map.go:18)    MOVQ    CX, (AX)
    0x01bc 00444 (./test_map.go:20)    MOVQ    "".aMap+232(SP), AX
    0x01c4 00452 (./test_map.go:20)    MOVQ    AX, ""..autotmp_4+248(SP)
    0x01cc 00460 (./test_map.go:20)    LEAQ    ""..autotmp_5+416(SP), DI
    0x01d4 00468 (./test_map.go:20)    XORPS    X0, X0
    0x01d7 00471 (./test_map.go:20)    PCDATA    $0, $-2
    0x01d7 00471 (./test_map.go:20)    LEAQ    -32(DI), DI
    0x01db 00475 (./test_map.go:20)    NOP
    0x01e0 00480 (./test_map.go:20)    DUFFZERO    $273
    0x01f3 00499 (./test_map.go:20)    PCDATA    $0, $-1
    0x01f3 00499 (./test_map.go:20)    MOVQ    ""..autotmp_4+248(SP), AX
    0x01fb 00507 (./test_map.go:20)    LEAQ    type.map[int64]int64(SB), CX
    0x0202 00514 (./test_map.go:20)    MOVQ    CX, (SP)
    0x0206 00518 (./test_map.go:20)    MOVQ    AX, 8(SP)
    0x020b 00523 (./test_map.go:20)    LEAQ    ""..autotmp_5+416(SP), AX
    0x0213 00531 (./test_map.go:20)    MOVQ    AX, 16(SP)
    0x0218 00536 (./test_map.go:20)    PCDATA    $1, $3
    0x0218 00536 (./test_map.go:20)    CALL    runtime.mapiterinit(SB)
    0x021d 00541 (./test_map.go:20)    JMP    543
    0x021f 00543 (./test_map.go:20)    CMPQ    ""..autotmp_5+416(SP), $0
    0x0228 00552 (./test_map.go:20)    JNE    559
    0x022a 00554 (./test_map.go:20)    JMP    886
    0x022f 00559 (./test_map.go:20)    MOVQ    ""..autotmp_5+416(SP), AX
    0x0237 00567 (./test_map.go:20)    TESTB    AL, (AX)
    0x0239 00569 (./test_map.go:20)    MOVQ    (AX), AX
    0x023c 00572 (./test_map.go:20)    MOVQ    AX, "".k+56(SP)
    0x0241 00577 (./test_map.go:20)    MOVQ    ""..autotmp_5+424(SP), AX
    0x0249 00585 (./test_map.go:20)    TESTB    AL, (AX)
    0x024b 00587 (./test_map.go:20)    MOVQ    (AX), AX
    0x024e 00590 (./test_map.go:20)    MOVQ    AX, "".v+48(SP)
    0x0253 00595 (./test_map.go:21)    XORPS    X0, X0
    0x0256 00598 (./test_map.go:21)    MOVUPS    X0, ""..autotmp_6+336(SP)
    0x025e 00606 (./test_map.go:21)    MOVUPS    X0, ""..autotmp_6+352(SP)
    0x0266 00614 (./test_map.go:21)    LEAQ    ""..autotmp_6+336(SP), AX
    0x026e 00622 (./test_map.go:21)    MOVQ    AX, ""..autotmp_17+272(SP)
    0x0276 00630 (./test_map.go:21)    MOVQ    "".k+56(SP), AX
    0x027b 00635 (./test_map.go:21)    MOVQ    AX, (SP)
    0x027f 00639 (./test_map.go:21)    PCDATA    $1, $4
    0x027f 00639 (./test_map.go:21)    NOP
    0x0280 00640 (./test_map.go:21)    CALL    runtime.convT64(SB)
    0x0285 00645 (./test_map.go:21)    MOVQ    8(SP), AX
    0x028a 00650 (./test_map.go:21)    MOVQ    AX, ""..autotmp_18+264(SP)
    0x0292 00658 (./test_map.go:21)    MOVQ    ""..autotmp_17+272(SP), CX
    0x029a 00666 (./test_map.go:21)    TESTB    AL, (CX)
    0x029c 00668 (./test_map.go:21)    LEAQ    type.int64(SB), DX
    0x02a3 00675 (./test_map.go:21)    MOVQ    DX, (CX)
    0x02a6 00678 (./test_map.go:21)    LEAQ    8(CX), DI
    0x02aa 00682 (./test_map.go:21)    PCDATA    $0, $-2
    0x02aa 00682 (./test_map.go:21)    CMPL    runtime.writeBarrier(SB), $0
    0x02b1 00689 (./test_map.go:21)    JEQ    696
    0x02b3 00691 (./test_map.go:21)    JMP    876
    0x02b8 00696 (./test_map.go:21)    MOVQ    AX, 8(CX)
    0x02bc 00700 (./test_map.go:21)    JMP    702
    0x02be 00702 (./test_map.go:21)    PCDATA    $0, $-1
    0x02be 00702 (./test_map.go:21)    MOVQ    "".v+48(SP), AX
    0x02c3 00707 (./test_map.go:21)    MOVQ    AX, (SP)
    0x02c7 00711 (./test_map.go:21)    CALL    runtime.convT64(SB)
    0x02cc 00716 (./test_map.go:21)    MOVQ    8(SP), AX
    0x02d1 00721 (./test_map.go:21)    MOVQ    AX, ""..autotmp_19+256(SP)
    0x02d9 00729 (./test_map.go:21)    MOVQ    ""..autotmp_17+272(SP), CX
    0x02e1 00737 (./test_map.go:21)    TESTB    AL, (CX)
    0x02e3 00739 (./test_map.go:21)    LEAQ    type.int64(SB), DX
    0x02ea 00746 (./test_map.go:21)    MOVQ    DX, 16(CX)
    0x02ee 00750 (./test_map.go:21)    LEAQ    24(CX), DI
    0x02f2 00754 (./test_map.go:21)    PCDATA    $0, $-2
    0x02f2 00754 (./test_map.go:21)    CMPL    runtime.writeBarrier(SB), $0
    0x02f9 00761 (./test_map.go:21)    JEQ    765
    0x02fb 00763 (./test_map.go:21)    JMP    869
    0x02fd 00765 (./test_map.go:21)    MOVQ    AX, 24(CX)
    0x0301 00769 (./test_map.go:21)    JMP    771
    0x0303 00771 (./test_map.go:21)    PCDATA    $0, $-1
    0x0303 00771 (./test_map.go:21)    MOVQ    ""..autotmp_17+272(SP), AX
    0x030b 00779 (./test_map.go:21)    TESTB    AL, (AX)
    0x030d 00781 (./test_map.go:21)    JMP    783
    0x030f 00783 (./test_map.go:21)    MOVQ    AX, ""..autotmp_16+312(SP)
    0x0317 00791 (./test_map.go:21)    MOVQ    $2, ""..autotmp_16+320(SP)
    0x0323 00803 (./test_map.go:21)    MOVQ    $2, ""..autotmp_16+328(SP)
    0x032f 00815 (./test_map.go:21)    MOVQ    AX, (SP)
    0x0333 00819 (./test_map.go:21)    MOVQ    $2, 8(SP)
    0x033c 00828 (./test_map.go:21)    MOVQ    $2, 16(SP)
    0x0345 00837 (./test_map.go:21)    PCDATA    $1, $3
    0x0345 00837 (./test_map.go:21)    CALL    fmt.Println(SB)
    0x034a 00842 (./test_map.go:21)    JMP    844
    0x034c 00844 (./test_map.go:20)    LEAQ    ""..autotmp_5+416(SP), AX
    0x0354 00852 (./test_map.go:20)    MOVQ    AX, (SP)
    0x0358 00856 (./test_map.go:20)    CALL    runtime.mapiternext(SB)
    0x035d 00861 (./test_map.go:20)    NOP
    0x0360 00864 (./test_map.go:20)    JMP    543
    0x0365 00869 (./test_map.go:21)    PCDATA    $0, $-2
    0x0365 00869 (./test_map.go:21)    CALL    runtime.gcWriteBarrier(SB)
    0x036a 00874 (./test_map.go:21)    JMP    771
    0x036c 00876 (./test_map.go:21)    CALL    runtime.gcWriteBarrier(SB)
    0x0371 00881 (./test_map.go:21)    JMP    702
    0x0376 00886 (./test_map.go:24)    PCDATA    $0, $-1
    0x0376 00886 (./test_map.go:24)    PCDATA    $1, $-1
    0x0376 00886 (./test_map.go:24)    MOVQ    512(SP), BP
    0x037e 00894 (./test_map.go:24)    ADDQ    $520, SP
    0x0385 00901 (./test_map.go:24)    RET
    0x0386 00902 (./test_map.go:24)    NOP
    0x0386 00902 (./test_map.go:13)    PCDATA    $1, $-1
    0x0386 00902 (./test_map.go:13)    PCDATA    $0, $-2
    0x0386 00902 (./test_map.go:13)    CALL    runtime.morestack_noctxt(SB)
    0x038b 00907 (./test_map.go:13)    PCDATA    $0, $-1
    0x038b 00907 (./test_map.go:13)    JMP    0

上面会对这段代码进行精简分段剖析

创立空字典 b

0x0032 00050 (./test_map.go:14)    MOVQ    $0, "".b+224(SP)

只有一行,间接指向 0 指针

创立非空字典 aMap

0x003e 00062 (./test_map.go:15)    XORPS    X1, X1                                 // X1                        = (int128)0
0x0041 00065 (./test_map.go:15)    MOVUPS    X1, ""..autotmp_7+368(SP)              // autotmp_7(hmap).count     = (int)0
                                                                               // autotmp_7(hmap).flags     = (uint8)0
                                                                               // autotmp_7(hmap).B         = (uint8)0
                                                                               // autotmp_7(hmap).noverflow = (uint16)0
                                                                               // autotmp_7(hmap).hash0     = (uint32)0
0x0049 00073 (./test_map.go:15)    MOVUPS    X1, ""..autotmp_7+384(SP)              // autotmp_7(hmap).buckets   = (unsafe.Pointer)0
                                                                               // autotmp_7(hmap).oldbuckets= (unsafe.Pointer)0
0x0051 00081 (./test_map.go:15)    MOVUPS    X1, ""..autotmp_7+400(SP)              // autotmp_7(hmap).nevacuate = (uintptr)0
                                                                               // autotmp_7(hmap).extra     = (*mapextra)0
0x0059 00089 (./test_map.go:15)    LEAQ    ""..autotmp_8+80(SP), DI
0x005e 00094 (./test_map.go:15)    XORPS    X0, X0
0x0061 00097 (./test_map.go:15)    PCDATA    $0, $-2
0x0061 00097 (./test_map.go:15)    LEAQ    -48(DI), DI
0x0065 00101 (./test_map.go:15)    DUFFZERO    $258
0x0078 00120 (./test_map.go:15)    PCDATA    $0, $-1
0x0078 00120 (./test_map.go:15)    LEAQ    ""..autotmp_7+368(SP), AX              // AX                        = (*hmap)&autotmp_7
0x0080 00128 (./test_map.go:15)    MOVQ    AX, ""..autotmp_9+240(SP)              // autotmp_9                 = AX = (*hmap)&autotmp_7
0x0088 00136 (./test_map.go:15)    TESTB    AL, (AX)
0x008a 00138 (./test_map.go:15)    LEAQ    ""..autotmp_8+80(SP), AX               // AX                        = &autotmp_8
0x008f 00143 (./test_map.go:15)    MOVQ    AX, ""..autotmp_7+384(SP)              // autotmp_7(hmap).buckets   = AX = &autotmp_8
0x0097 00151 (./test_map.go:15)    LEAQ    ""..autotmp_7+368(SP), AX              // AX                        = &autotmp_7(hmap)
0x009f 00159 (./test_map.go:15)    MOVQ    AX, ""..autotmp_10+304(SP)             // autotmp_10                = AX = &autotmp_7(hmap)
0x00a7 00167 (./test_map.go:15)    PCDATA    $1, $1
0x00a7 00167 (./test_map.go:15)    CALL    runtime.fastrand(SB)
0x00ac 00172 (./test_map.go:15)    MOVQ    ""..autotmp_10+304(SP), AX             // AX = autotmp_10 = (*hmap)&autotmp_7
0x00b4 00180 (./test_map.go:15)    TESTB    AL, (AX)
0x00b6 00182 (./test_map.go:15)    MOVL    (SP), CX                               // CX = (int32)runtime.fastrand(SB)
0x00b9 00185 (./test_map.go:15)    MOVL    CX, 12(AX)                             // autotmp_7(hmap).hash0 = CX = runtime.fastrand(SB)
0x00bc 00188 (./test_map.go:15)    LEAQ    ""..autotmp_7+368(SP), AX              // AX = (*hmap)&autotmp_7
0x00c4 00196 (./test_map.go:15)    MOVQ    AX, "".aMap+232(SP)                    // aMap = AX = (*hmap)&autotmp_7

失去一个指针变量 aMap 指向 *hmap

type hmap struct {
    // Note: the format of the hmap is also encoded in cmd/compile/internal/gc/reflect.go.
    // Make sure this stays in sync with the compiler's definition.
    count     int // # live cells == size of map.  Must be first (used by len() builtin)
    flags     uint8
    B         uint8  // log_2 of # of buckets (can hold up to loadFactor * 2^B items)
    noverflow uint16 // approximate number of overflow buckets; see incrnoverflow for details
    hash0     uint32 // hash seed

    buckets    unsafe.Pointer // array of 2^B Buckets. may be nil if count==0.
    oldbuckets unsafe.Pointer // previous bucket array of half the size, non-nil only when growing
    nevacuate  uintptr        // progress counter for evacuation (buckets less than this have been evacuated)

    extra *mapextra // optional fields
}
其中
hmap.buckets = &autotmp_8
hmap.hash0   = (int32)runtime.fastrand(SB)
其余变量都等于 0 

赋值

var aMap = map[int64]int64{
    1: 10,
    2: 20,
    3: 30,
}

有三个值别离赋值,都是一样的,这里只讲 aMap[1] = 10

截取汇编:

0x00cc 00204 (./test_map.go:16)    MOVQ    $1, ""..autotmp_11+72(SP)             // autotmp_11 = 1
0x00d5 00213 (./test_map.go:16)    MOVQ    $10, ""..autotmp_12+64(SP)            // autotmp_12 = 10
0x00de 00222 (./test_map.go:16)    MOVQ    ""..autotmp_11+72(SP), AX             // AX = autotmp_11 = 1
0x00e3 00227 (./test_map.go:16)    MOVQ    "".aMap+232(SP), CX                   // CX = aMap
0x00eb 00235 (./test_map.go:16)    LEAQ    type.map[int64]int64(SB), DX          // DX = type.map[int64]int64(SB)
0x00f2 00242 (./test_map.go:16)    MOVQ    DX, (SP)
0x00f6 00246 (./test_map.go:16)    MOVQ    CX, 8(SP)
0x00fb 00251 (./test_map.go:16)    MOVQ    AX, 16(SP)
0x0100 00256 (./test_map.go:16)    PCDATA    $1, $2
0x0100 00256 (./test_map.go:16)    CALL    runtime.mapassign_fast64(SB)         // runtime.mapassign_fast64(type.map[int64]int64(SB), aMap, AX)
0x0105 00261 (./test_map.go:16)    MOVQ    24(SP), AX                           // AX = runtime.mapassign_fast64
0x010a 00266 (./test_map.go:16)    MOVQ    AX, ""..autotmp_13+296(SP)           // autotmp_13 = runtime.mapassign_fast64
0x0112 00274 (./test_map.go:16)    TESTB    AL, (AX)
0x0114 00276 (./test_map.go:16)    MOVQ    ""..autotmp_12+64(SP), CX            // CX = autotmp_12 = 2
0x0119 00281 (./test_map.go:16)    MOVQ    CX, (AX)                             // *AX = CX = 2

其中

func mapassign_fast64(t *maptype, h *hmap, key uint64) unsafe.Pointer {
    if h == nil {                                                // 空字典报错
        panic(plainError("assignment to entry in nil map"))
    }
    if h.flags&hashWriting != 0 {                                // 写入状态
        throw("concurrent map writes")
    }
    hash := t.hasher(noescape(unsafe.Pointer(&key)), uintptr(h.hash0))        // 生成哈希值

    // Set hashWriting after calling t.hasher for consistency with mapassign.
    h.flags ^= hashWriting                                        // 设置写入状态

    if h.buckets == nil {                                        // 生成 buckets
        h.buckets = newobject(t.bucket) // newarray(t.bucket, 1)
    }

again:
    bucket := hash & bucketMask(h.B)                           // 判断去那个桶
    if h.growing() {                                           // 如果在扩大桶
        growWork_fast64(t, h, bucket)
    }
    b := (*bmap)(add(h.buckets, bucket*uintptr(t.bucketsize)))  // 定位到相应的桶

    var insertb *bmap                                             // 最终插入到哪个桶
    var inserti uintptr                                         // 插入到桶的哪个坑(一共 bucketCnt(8)个)var insertk unsafe.Pointer                                  // 由下面计算失去的 key 的地位

bucketloop:
    for {for i := uintptr(0); i < bucketCnt; i++ {if isEmpty(b.tophash[i]) {
                if insertb == nil {
                    insertb = b
                    inserti = i
                }
                if b.tophash[i] == emptyRest {                       // 找到最初一个空格子,跳出进行插入
                    break bucketloop
                }
                continue                                            // 找到空格子然而不是最初一个,疏忽找下一个
            }
            k := *((*uint64)(add(unsafe.Pointer(b), dataOffset+i*8)))
            if k != key {                                            // 不为空,就判断下 key 会不会相等
                continue
            }
            insertb = b
            inserti = i
            goto done                                               // key 相等,不必插入 key 了,间接去 done,找到值插入进好了
        }
        // 桶外面没找到
        ovf := b.overflow(t)                                        // 看看有没有溢出桶桶
        if ovf == nil {                                             // 没有,退出
            break
        }
        b = ovf                                                    // 有的话,下一个桶持续找
    }

    // Did not find mapping for key. Allocate new cell & add entry.

    // 如果超过装载因子,或者溢出桶数量超过最大值,则扩大桶
    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 {
        // 以后的桶和溢出桶都满了,则新建一个桶
        insertb = h.newoverflow(t, b)
        inserti = 0 // not necessary, but avoids needlessly spilling inserti
    }
    //  胜利到找到了插入地位
    //  插入 tophash
    insertb.tophash[inserti&(bucketCnt-1)] = tophash(hash) // mask inserti to avoid bounds checks
    // 插入 key
    insertk = add(unsafe.Pointer(insertb), dataOffset+inserti*8)
    // store new key at insert position
    *(*uint64)(insertk) = key

    h.count++

done:
    // 获取字典的值地位
    elem := add(unsafe.Pointer(insertb), dataOffset+bucketCnt*8+inserti*uintptr(t.elemsize))
    // 设置和查看 flags
    if h.flags&hashWriting == 0 {throw("concurrent map writes")
    }
    h.flags &^= hashWriting
    return elem
}

每种字典的 bmap 的 key 和 value 都不一样,上面是本例子的 mapint64

const bucketCnt = 8
type bmap struct {tophash [bucketCnt]uint8
    key     [bucketCnt]int64       // int64 就是 map 的 key 的类型
    elem    [bucketCnt]int64       // int64 就是 map 的 value 的类型
    overflow *bmap                 // 下一个溢出 bmap
}

遍历

func mapiterinit(t *maptype, h *hmap, it *hiter) {if unsafe.Sizeof(hiter{})/sys.PtrSize != 12 {throw("hash_iter size incorrect") // see cmd/compile/internal/gc/reflect.go
    }
    it.t = t
    it.h = h

    // grab snapshot of bucket state
    it.B = h.B
    it.buckets = h.buckets
    if t.bucket.ptrdata == 0 {
        // Allocate the current slice and remember pointers to both current and old.
        // This preserves all relevant overflow buckets alive even if
        // the table grows and/or overflow buckets are added to the table
        // while we are iterating.
        h.createOverflow()
        it.overflow = h.extra.overflow
        it.oldoverflow = h.extra.oldoverflow
    }

    // decide where to start
    r := uintptr(fastrand())
    if h.B > 31-bucketCntBits {r += uintptr(fastrand()) << 31
    }
    it.startBucket = r & bucketMask(h.B)
    it.offset = uint8(r >> h.B & (bucketCnt - 1))

    // iterator state
    it.bucket = it.startBucket

    // Remember we have an iterator.
    // Can run concurrently with another mapiterinit().
    if old := h.flags; old&(iterator|oldIterator) != iterator|oldIterator {atomic.Or8(&h.flags, iterator|oldIterator)
    }

    mapiternext(it)
}

正文完
 0