1
2
3

if h.flags&hashWriting == 0 {
    throw("concurrent map writes")
}

1

h.flags |= hashWriting

1

make(map[key-type]value-type, hint int) 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

B := uint8(0)
for overLoadFactor(hint, B) {
     B++
}
h.B = B   

// 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)
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

// 声明的基本语法
var 变量名称 map[键类型]值类型 
// golang中 map的类型可以是bool、数组、string、指针、channel、接口、结构体、map

// 直接声明map
var a map[string]string
var m map[string]map[string]string  // map也可以以map作为key-value, 第二个map作为第一个map的value存在
a = make(map[string]string, 10)     // 需要先给map声明一块内存空间才能使用，和切片一样使用make
                                    // 10 是map的空间大小，如果不写默认是1
// 直接调用make创建map， 
cities := make(map[string]string) //这样不设置元素大小，是可以自增长的

// 直接写入数据创建map， 底层调用 maplit 函数初始化函数实现
heroes := map[string]string{    // 直接在定义的时候赋值，就可以不需要make了，并且自增长
    "hero1": "松江",
    "hero2": "黄河",
    "hero3": "长江",            // 这里结尾也是要有逗号的
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

// 声明 并使用 make 创建map
var a map[string]string
a = make(map[string]string,10)

// map增加 和 更新
a["no1"] = "松江"   // 增加
a["no0"] = "吴用"
a["no3"] = "武松"

a["no1"] = "武松"   // 如果key不存在就会增加，如果存在则覆盖

// Go 语言中读取 map 有两种语法：
// 1. 带 comma。当要查询的 key 不在 map 里，带 comma 的用法会返回一个 bool 型变量提示 key 是否在 map 中；
// 2. 不带 comma 的语句则会返回一个 value 类型的零值。如果 map 中存储的 k-v对 有 v=0 的，则应该使用带comma的查询；

// 带 comma 的 map查询
value, ok :=a["no1"]  //如果a这个map中存在"no1"的key,那么value会获取值, 而findRes会根据是否存在值，返回true或false
if ok {  // 判断是否存在该值去输出
    fmt.Println("Find key=no1, value=", value)
}else{
    fmt.Println("Not find no1.")
}
// 带 comma 的 map查询
value1 := a["no4"]
fmt.Println("Find key=no4, value=", value) // 输出： Find key=no4, value=

// 遍历map: map 的遍历使用for-range，不能使用for循环
for k := range a{
    fmt.Printf("k=%v v=%v\n",k, a[k])
}
for k, v := range a{
    fmt.Printf("k=%v v=%v\n",k,v)
}

// map删除key
delete(a,"no1")     // 通过delete(map,key名称)进行删除

// Golang中没有一个专门的方法一次删除map的所有key
// 如果要删除map的所有key，只能遍历map 一个一个删除 key 或者 map = make(...)  make一个新的空间，让原来的变为垃圾，被gc回收

//直接make一个新的空间即可
a = make(map[string]string)
for k := range a{
    delete(a, k)
}

// 统计map的key-values数量
mapSize = len(a) // 用len统计map有多少对key-value

// 排序: go 中map 默认是无序的，并且没有针对map key的排序
var keys []string            // 定义一个切片
for k, _ := range a{   // 将map的key 循环出来存放到切片中
    keys = append(keys,k)
}


sort.Ints(keys)    // 通过sort模块的Ints对整数进行排序
fmt.Println(keys)


for _, k :=range keys{    //按照切片中key的顺序去取map的值
    fmt.Printf("map[%v]=%v\n",k ,a[k])

}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

// ${GPROOT}/src//cmd/compile/internal/types/type.go
// Map contains Type fields specific(特定于) to maps.
type Map struct {
    Key  *Type // Key type
    Elem *Type // Val (elem) type

    Bucket *Type // internal struct type representing a hash bucket
    Hmap   *Type // internal struct type representing the Hmap (map header object)
    Hiter  *Type // internal struct type representing hash iterator state
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86

const {
    ...
    //  bucket
    bucketCntBits = 3
    bucketCnt     = 1 << bucketCntBits  // 一个桶最多8个位置

    ...

    // flags
    iterator     = 1    // there may be an iterator using buckets
                        // 可能有迭代器(遍历)在使用buckets

    oldIterator  = 2    // there may be an iterator using oldbuckets
                        // 可能有迭代器(遍历)在使用oldbuckets，用于扩容期间

    hashWriting  = 4    // a goroutine is writing to the map
                        // 有一个 goroutine正在写入map操作，用于并发读写检测
    sameSizeGrow = 8    // the current map growth is to a new map of the same size
                        // 表示正在进行相同大小的扩容，即 buckets 的数量不变，只是增加溢出桶的数量

    ...
}

type hmap struct {
    // Note: the format of the hmap is also encoded in cmd/compile/internal/reflectdata/reflect.go.
    // Make sure this stays in sync with the compiler's definition.
    count      int            // map中元素(key-value对)的数量，调用len()直接返回此值
    flags      uint8          // buckets 桶数组 状态标识符(bit位操作)
    B          uint8          // map中桶数组个数的对数，len(buckets) == 2^B，
                              // 可以最多容纳 6.5 * 2 ^ B 个元素，6.5为负载因子
    noverflow  uint16         // 溢出桶的近似值，当B小于16时是准确值，大于等于16时是近似值；
                              // 当溢出的桶太多时，map 会进行 same-size map growth；
                              // 其实质是避免桶过大导致内存泄露

    hash0      uint32         // 哈希种子，用于计算哈希值，为哈希函数的结果引入一定的随机性

    buckets    unsafe.Pointer // 指向 hash 常规桶数组，常规桶数组长度为 2^B ，存储实际的键值对数据，
                              // 每个桶存储一组具有相同哈希值的键值对，如果元素个数为0，就为 nil

    oldbuckets unsafe.Pointer // 在 map 扩容时，用于临时存储旧的桶数组；
                              // 扩容过程中会逐渐将键值对从旧的桶迁移到新的桶；
                              // 如果发生扩容, oldbuckets是指向老的buckets数组的指针, 
                              // 老的buckets数组大小是新的buckets的1/2，
                              // 当所有旧桶中的数据都已经转移到了新桶（buckets指向的hash桶数组）中时，
                              // 则清空该指针指向的 旧hash桶数组；
                              // 非扩容状态下, 它为nil；
                              // 它是判断是否处于扩容状态的标识

    nevacuate  uintptr        // 用来记录渐进式扩容阶段下一个要迁移的旧桶编号；
                              // 当 map 的负载因子超过一定阈值时，会触发扩容操作，
                              // 此时会分配新的 buckets 数组，并将旧的 buckets 数组保存在 oldbuckets 字段中；
                              // 为了避免一次性搬迁所有的键值对，造成性能下降，Go 语言采用了渐进式扩容的方式，
                              // 即每次插入或删除键值对时，都会尝试搬迁部分旧桶到新桶中；
                              // hmap.nevacuate 就是用来指示下一次搬迁的旧桶的索引，它的初始值为 0，
                              // 每次搬迁后会递增，直到等于旧桶的数量，表示扩容完成。
                              
    extra      *mapextra      // 可选字段，指向 mapextra 结构体的指针，存储额外的位标志，如迭代器状态和特殊标志等；
                              // 这个字段是为了优化GC扫描而设计的。
}

// 记录 map 溢出桶的信息
type mapextra struct {
    // 如果 key 和 value 都不包含指针，并且可以被 inline(<=128 字节)
    // 就使用 hmap的extra字段 来存储 overflow buckets，这样可以避免 GC 扫描整个 map
    // 然而 bmap.overflow 也是个指针，这时只能把这些 overflow 的指针
    // 都放在 hmap.extra.overflow 和 hmap.extra.oldoverflow 中了
    // overflow 包含的是 hmap.buckets 的 overflow 的 buckets
    // oldoverflow 包含扩容时的 hmap.oldbuckets 的 overflow 的 bucket
    overflow    *[]*bmap // 指针数组，指向所有溢出桶
    oldoverflow *[]*bmap // 指针数组，发生扩容时，指向所有旧的溢出桶
    nextOverflow *bmap // 指向空闲的 overflow bucket 的指针
}

// A bucket for a Go map.
type bmap struct {
    // tophash generally(通常) contains the top byte of the hash value
    // for each key in this bucket. If tophash[0] < minTopHash,
    // tophash[0] is a bucket evacuation state instead.
    // 译：tophash 通常包含此 buckets 中每个键的哈希值的最高字节。 如果 tophash[0] < minTopHash，则 tophash[0] 是一个桶疏散状态。
    tophash [bucketCnt]uint8    // bucketCnt = 8
    // Followed by bucketCnt（8）keys and then bucketCnt（8）elems.
    // NOTE: packing all the keys together and then all the elems together makes the
    // code a bit（稍微） more complicated（复杂） than alternating（使交替） key/elem/key/elem/... but it allows
    // us to eliminate padding（消除填充） which would be needed for, e.g., map[int64]int8.
    // Followed by an overflow pointer.
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

// ${GOROOT}/src/cmd/compile/internal/reflectdata/reflect.go
func MapBucketType(t *types.Type) *types.Type {
    // ...

    // 获取 map 的键类型和值类型
    keytype := t.Key()
    elemtype := t.Elem()

    // 计算键和值的大小
    types.CalcSize(keytype)
    types.CalcSize(elemtype)

    // 如果键的大小超过了 MAXKEYSIZE，则将其变为指针类型
    if keytype.Size() > MAXKEYSIZE {
        keytype = types.NewPtr(keytype)
    }

    // 如果值的大小超过了 MAXELEMSIZE，则将其变为指针类型
    if elemtype.Size() > MAXELEMSIZE {
        elemtype = types.NewPtr(elemtype)
    }

    // 创建桶类型的字段
    field := make([]*types.Field, 0, 5)

    // 创建包含 topbits 的数组字段
    arr := types.NewArray(types.Types[types.TUINT8], BUCKETSIZE)
    field = append(field, makefield("topbits", arr))

    // 创建包含键的数组字段
    arr = types.NewArray(keytype, BUCKETSIZE)
    arr.SetNoalg(true)
    keys := makefield("keys", arr)
    field = append(field, keys)

    // 创建包含值的数组字段
    arr = types.NewArray(elemtype, BUCKETSIZE)
    arr.SetNoalg(true)
    elems := makefield("elems", arr)
    field = append(field, elems)

    // 创建溢出字段，根据键和值是否有指针来确定类型
    otyp := types.Types[types.TUNSAFEPTR]
    if !elemtype.HasPointers() && !keytype.HasPointers() {
        otyp = types.Types[types.TUINTPTR]
    }
    overflow := makefield("overflow", otyp)
    field = append(field, overflow)

    // 创建桶类型
    bucket := types.NewStruct(types.NoPkg, field[:])
    bucket.SetNoalg(true)
    types.CalcSize(bucket)

    // 将桶类型赋值给 map 类型的 Bucket 字段
    t.MapType().Bucket = bucket

    // 设置桶类型的 Map 字段为当前的 map 类型
    bucket.StructType().Map = t

    // 返回桶类型
    return bucket
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

// 实际上编辑期间会动态生成一个新的 bmap 结构体
type bmap struct {
    topbits  [8]uint8     // 存放key哈希值的高8位，用于决定kv键值对放在桶内的哪个位置
    keys     [8]keytype   // 存放key的数组
    values   [8]valuetype // 存放value的数组
    pad      uintptr      // 用于对齐内存
    overflow uintptr      // 指向下一个桶，即溢出桶，拉链法解决hash冲突
    // 当发生碰撞时，一个桶里最多放8个键值对。
    // 当有第9个key被hash到该桶时，由于没有多余的位置，需要放到溢出桶
    // overflow即为指向溢出桶的指针，溢出桶和桶的内部结构是一样的。
}

1

10010111 | 000011110110110010001111001010100010010110010101010 │ 00110

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85

// runtime/map.go
func mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
    // ......
    // 如果 *hmap大小为0，或地址为nil，返回零值
    if h == nil || h.count == 0 {
        if t.hashMightPanic() {
            t.hasher(key, 0) // see issue 23734
        }
        return unsafe.Pointer(&zeroVal[0])
    }
    // 读写冲突
    if h.flags&hashWriting != 0 {
        throw("concurrent map read and map write")
    }
    // 计算哈希值，并且加入 hash0 引入随机性
    hash := t.hasher(key, uintptr(h.hash0))
    // 比如 B=5，那 m 就是31，二进制是全 1
    // 求 bucket num 时，将 hash 与 m 相与，
    // 达到 bucket num 由 hash 的低 8 位决定的效果
    m := bucketMask(h.B)
    // b 就是 bucket 的地址
    b := (*bmap)(add(h.buckets, (hash&m)*uintptr(t.bucketsize)))
    // oldbuckets 不为 nil，说明发生了扩容
    if c := h.oldbuckets; c != nil {
        // 如果不是同 size 扩容（看后面扩容的内容）
        // 对应条件 1 的解决方案
        if !h.sameSizeGrow() {
            // 新 bucket 数量是老的 2 倍
            m >>= 1
        }
        // 求出 key 在老的 map 中的 bucket 位置
        oldb := (*bmap)(add(c, (hash&m)*uintptr(t.bucketsize)))
        // 如果 oldb 没有搬迁到新的 bucket
        // 那就在老的 bucket 中寻找
        if !evacuated(oldb) {
            b = oldb
        }
    }
    // 计算出高 8 位的 hash
    // 相当于右移 56 位，只取高8位
    top := tophash(hash)
bucketloop:
    // 遍历 bucket 的 8 个位置
    // bucket 找完（还没找到），继续到 overflow bucket 里找
    for ; b != nil; b = b.overflow(t) {
        for i := uintptr(0); i < bucketCnt; i++ {
            // tophash 不匹配，继续遍历
            if b.tophash[i] != top {
                if b.tophash[i] == emptyRest {
                    break bucketloop
                }
                continue
            }
            // tophash 匹配，定位到 key 的位置
            k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
            // key 是指针
            if t.indirectkey() {
                // 解引用
                k = *((*unsafe.Pointer)(k))
            }
            // 如果 key 相等
            if t.key.equal(key, k) {
                // 定位到 value 的位置
                e := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize))
                // value 是指针
                if t.indirectelem() {
                    // 解引用
                    e = *((*unsafe.Pointer)(e))
                }
                return e
            }
        }
    }
    // 返回零值
    return unsafe.Pointer(&zeroVal[0])
}

func tophash(hash uintptr) uint8 {
    top := uint8(hash >> (sys.PtrSize*8 - 8))
    if top < minTopHash {
        // 增加一个 minTopHash
        top += minTopHash
    }
    return top
}

1

k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))

1

v := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.valuesize))

1
2
3
4

dataOffset = unsafe.Offsetof(struct {
        b bmap
        v int64
    }{}.v)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

// runtime/map.go
const (
    ...

    // Possible tophash values. We reserve(保留) a few possibilities for special marks.
    // Each bucket (including its overflow buckets, if any) will have either all or none of its
    // entries in the evacuated(搬迁)* states (except during the evacuate() method, which only happens
    // during map writes and thus no one else can observe（观察到） the map during that time).
    emptyRest      = 0 // this cell is empty, and there are no more non-empty cells at higher indexes or overflows. // 表示此桶单元为空(初始时 bucket 的状态)，其更高索引或者溢出桶也为空，即后面没有任何键值对存储在此桶中；
    emptyOne       = 1 // this cell is empty // 表示此桶单元为空，但更高索引的单元可能不为空，即后面可能还有键值对存储在此桶中；
    evacuatedX     = 2 // key/elem is valid.  Entry has been evacuated to first half of larger table.  // 表示此桶单元已经被迁移，且迁移到新桶的前半段区间，即新桶的索引为旧桶索引左移一位；
    evacuatedY     = 3 // same as above, but evacuated to second half of larger table. // 表示此桶单元已经被迁移，且迁移到新桶的后半段区间，即新桶的索引为旧桶索引左移一位加一；
    evacuatedEmpty = 4 // cell is empty, bucket is evacuated. //表示此桶单元已经被迁移，bucket的所有单元格都是空的，即没有任何键值对需要迁移；
    minTopHash     = 5 // minimum tophash for a normal filled cell. // 用来区分键的哈希值的高位和桶状态的标识位值

    ...
)

1
2
3
4

func evacuated(b *bmap) bool {
    h := b.tophash[0]
    return h > emptyOne && h < minTopHash
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

type mapextra struct {
    // 如果 key 和 value 都不包含指针，并且可以被 inline(<=128 字节)
    // 就使用 hmap的extra字段 来存储 overflow buckets，这样可以避免 GC 扫描整个 map
    // 然而 bmap.overflow 也是个指针，这时候只能把这些 overflow 的指针
    // 都放在 hmap.extra.overflow 和 hmap.extra.oldoverflow 中了
    // overflow 包含的是 hmap.buckets 的 overflow 的 buckets
    // oldoverflow 包含扩容时的 hmap.oldbuckets 的 overflow 的 bucket
    overflow    *[]*bmap // 指针数组，指向所有溢出桶
    oldoverflow *[]*bmap // 指针数组，发生扩容时，指向所有旧的溢出桶
    nextOverflow *bmap // 指向空闲的 overflow bucket 的指针
}

1
2
3
4
5

// 不指定初始化map大小
make(map[k]v)

// 指定初始化map大小为hint
make(map[k]v, hint)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

// main.go
package main
import "fmt"

func main() {
    m := make(map[string]int, 2)
    m1 := make(map[string]int, 8)
    m2 := make(map[string]int, 9)
    fmt.Println(m, m1, m2)
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

main.main STEXT size=185 args=0x0 locals=0x70 funcid=0x0 align=0x0
    0x0000 00000     TEXT    main.main(SB), ABIInternal, $112-0
    0x0000 00000     CMPQ    SP, 16(R14)
    0x0004 00004     PCDATA    $0, $-2
    0x0004 00004     JLS    175
    0x000a 00010     PCDATA    $0, $-1
    0x000a 00010     SUBQ    $112, SP
    0x000e 00014     MOVQ    BP, 104(SP)
    0x0013 00019     LEAQ    104(SP), BP
    0x0018 00024     FUNCDATA    $0, gclocals·ykHN0vawYuq1dUW4zEe2gA==(SB)
    0x0018 00024     FUNCDATA    $1, gclocals·I76sKbn5RubBl1jweLet5Q==(SB)
    0x0018 00024     FUNCDATA    $2, main.main.stkobj(SB)
    0x0018 00024     PCDATA    $1, $0
    0x0018 00024     CALL    runtime.makemap_small(SB)
    0x001d 00029     MOVQ    AX, main.m+48(SP)
    0x0022 00034     PCDATA    $1, $1
    0x0022 00034     CALL    runtime.makemap_small(SB)
    0x0027 00039     MOVQ    AX, main.m1+40(SP)
    0x002c 00044     MOVL    $9, BX
    0x0031 00049     XORL    CX, CX
    0x0033 00051     LEAQ    type:map[string]int(SB), AX
    0x003a 00058     PCDATA    $1, $2
    0x003a 00058     CALL    runtime.makemap(SB)
    0x003f 00063     MOVUPS    X15, main..autotmp_11+56(SP)
    0x0045 00069     MOVUPS    X15, main..autotmp_11+72(SP)
    0x004b 00075     MOVUPS    X15, main..autotmp_11+88(SP)
    ......

1
2
3
4
5
6

// ${GOROOT}/src/runtime/map.go 
func makemap_small() *hmap {
    h := new(hmap)
    h.hash0 = fastrand()
    return h
}

1
2
3
4
5
6
7

var h *hmap
var hv hmap
var bv bmap
h := &hv
b := &bv
h.buckets = b
h.hash0 = fashtrand0()

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

// ${GOROOT}/src/runtime/map.go 
func makemap(t *maptype, hint int, h *hmap) *hmap {
    // 计算需要分配的内存大小
    mem, overflow := math.MulUintptr(uintptr(hint), t.bucket.size)
    // 检查是否发生溢出或超过最大可分配内存
    if overflow || mem > maxAlloc {
        hint = 0
    }
    // 如果传入的 hmap 为空，则创建一个新的 hmap
    if h == nil {
        h = new(hmap)
    }
    // 初始化 hmap 的一些字段
    h.hash0 = fastrand() // 设置 hash0 字段为一个随机数
    B := uint8(0)
    // 根据负载因子计算 B 值，用于确定桶的数量
    for overLoadFactor(hint, B) {
        B++
    }
    h.B = B // 设置 hmap 的 B 字段，即桶的数量
    // 如果 B 不为 0，说明需要创建桶
    if h.B != 0 {
        var nextOverflow *bmap
        // 创建存储桶的数组，并返回下一个溢出桶的指针
        h.buckets, nextOverflow = makeBucketArray(t, h.B, nil)
        // 如果有下一个溢出桶，创建 mapextra 结构体，并将其赋值给 hmap 的 extra 字段
        if nextOverflow != nil {
            h.extra = new(mapextra)
            h.extra.nextOverflow = nextOverflow
        }
    }
    return h // 返回创建或更新后的 hmap
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

// go 1.20.3 path:/runtiime/type.go

type maptype struct {
    typ    _type  // 表示 map 类型本身的 _type 元信息，包括类型的名称、大小、对齐方式等
    key    *_type // 表示 map 的键类型的 _type 元信息
    elem   *_type // 表示 map 的值类型的 _type 元信息
    bucket *_type // 表示内部表示哈希桶的 _type 元信息
    hasher     func(unsafe.Pointer, uintptr) uintptr // 是一个哈希函数，用于计算键的哈希值
    keysize    uint8  // 键的大小（以字节为单位）
    elemsize   uint8  // 值的大小（以字节为单位）
    bucketsize uint16 // 哈希桶的大小（以字节为单位）
    flags      uint32 // 一些标志位，用于表示 map 的特性或配置
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

// go 1.20.3 path:/runtiime/map.go

const(
    bucketCntBits = 3
    bucketCnt     = 1 << bucketCntBits
    loadFactorNum = 13
    loadFactorDen = 2
)

func overLoadFactor(count int, B uint8) bool {
    return count > bucketCnt && uintptr(count) > loadFactorNum*(bucketShift(B)/loadFactorDen)
}

1
2
3

func bucketShift(b uint8) uintptr {
    return uintptr(1) << (b & (goarch.PtrSize*8 - 1))
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

// go 1.20.3 path:/runtiime/map.go

/**
 * @Description: 通过make创建map
 * @param t map的元类型
 * @param b map的哈希桶的数量的log2值
 * @param dirtyalloc 可选参数，表示存放桶的内存地址
 */
func makeBucketArray(t *maptype, b uint8, dirtyalloc unsafe.Pointer) (buckets unsafe.Pointer, nextOverflow *bmap) {
    //计算常规桶数量，即2^b
    base := bucketShift(b)
    //将常规桶的数量赋值给nbuckets
    nbuckets := base

    //如果b>=4,即桶的数量大于等于16，则nbuckets数量加上2^(b-4)个，多加的桶作为溢出桶使用
    if b >= 4 {
        //则nbuckets数量加上2^(b-4)个，多加的桶作为溢出桶使用
        nbuckets += bucketShift(b - 4)
        //计算创建nbuckets个桶所需的内存大小
        sz := t.bucket.size * nbuckets
        //取整对齐内存
        up := roundupsize(sz)
        if up != sz {
            nbuckets = up / t.bucket.size
        }
    }

    /**
    如果dirtyalloc为空，则分配新的内存；否则表示内存已经分配好了，直接使用并内存清零
    */
    if dirtyalloc == nil {
        //调用newarray函数分配一个新的数组作为桶的内存
        buckets = newarray(t.bucket, int(nbuckets))
    } else {
        //直接使用dirtyalloc作为桶的内存
        buckets = dirtyalloc
        //计算所有桶所需要的内存大小
        size := t.bucket.size * nbuckets
        if t.bucket.ptrdata != 0 {
            //如果桶的元素有指针，则调用memclrHasPointers函数将桶的内存清零
            memclrHasPointers(buckets, size)
        } else {
            //如果桶的元素没有指针，则调用memclrNoHeapPointers函数将桶的内存清零
            memclrNoHeapPointers(buckets, size)
        }
    }

    //如果base不等于nbuckets，说明分配了多余的桶作为溢出桶
    if base != nbuckets {
        //计算溢出桶的位置和设置溢出桶的链接
        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
}

1
2
3
4
5

hash := map[string]int{
    "1": 2,
    "3": 4,
    "5": 6,
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62

// go 1.20.3 path:/src/cmd/compile/internal/walk/complit.go

func maplit(n *ir.CompLitExpr, m ir.Node, init *ir.Nodes) {
    ......
      //如果字面量超过25个
    if len(entries) > 25 {
      //根据 n 的键类型和值类型，创建键类型数组 tk 和值类型数组 te，数组长度为 entries 的长度
      tk := types.NewArray(n.Type().Key(), int64(len(entries)))
          te := types.NewArray(n.Type().Elem(), int64(len(entries)))
      //调用 types.CalcSize 计算键类型数组和值类型数组的大小
        types.CalcSize(tk)
          types.CalcSize(te)
      //创建用于存储静态数组,变量名为 vstatk 和 vstate
          vstatk := readonlystaticname(tk)
          vstate := readonlystaticname(te)
      //创建两个空的 ir.CompLitExpr 表达式 datak 和 datae，表示键类型和值类型的静态数组
      datak := ir.NewCompLitExpr(base.Pos, ir.OARRAYLIT, nil, nil)
          datae := ir.NewCompLitExpr(base.Pos, ir.OARRAYLIT, nil, nil)
      //遍历 entries，将每个键和值表达式添加到对应的静态数组中
      for _, r := range entries {
        r := r.(*ir.KeyExpr)
        datak.List.Append(r.Key)
        datae.List.Append(r.Value)
      }
      //使用 fixedlit 函数将键类型和值类型的静态数组转化为静态初始值，并将其赋值给对应的静态变量 vstatk 和 vstate
      //最终将静态初始值的设置添加到 init 列表中
          fixedlit(inInitFunction, initKindStatic, datak, vstatk, init)
          fixedlit(inInitFunction, initKindStatic, datae, vstate, init)
      ......
      return
    }
  
    tmpkey := typecheck.Temp(m.Type().Key())  // 创建临时变量 tmpkey，用于存储键的值
    tmpelem := typecheck.Temp(m.Type().Elem())  // 创建临时变量 tmpelem，用于存储值的值

    // 遍历 entries 中的键值对
    for _, r := range entries {
      r := r.(*ir.KeyExpr)
      index, elem := r.Key, r.Value

      ir.SetPos(index)  // 设置当前位置为键表达式的位置
      appendWalkStmt(init, ir.NewAssignStmt(base.Pos, tmpkey, index))  // 构造赋值语句，将键的值赋给临时变量 tmpkey

      ir.SetPos(elem)  // 设置当前位置为值表达式的位置
      appendWalkStmt(init, ir.NewAssignStmt(base.Pos, tmpelem, elem))  // 构造赋值语句，将值的值赋给临时变量 tmpelem

      ir.SetPos(tmpelem)

      // 类型检查器将 OINDEX 重写为 OINDEXMAP
      lhs := typecheck.AssignExpr(ir.NewIndexExpr(base.Pos, m, tmpkey)).(*ir.IndexExpr)
      base.AssertfAt(lhs.Op() == ir.OINDEXMAP, lhs.Pos(), "want OINDEXMAP, have %+v", lhs)
      lhs.RType = n.RType

      // 构造赋值语句，将键值对存入 map
      var a ir.Node = ir.NewAssignStmt(base.Pos, lhs, tmpelem)
      a = typecheck.Stmt(a)  // 进行类型检查
      a = orderStmtInPlace(a, map[string][]*ir.Name{})  // 进行语句排序
      appendWalkStmt(init, a)  // 将赋值语句添加到初始化语句列表 init 中
    }

    ......
}

1
2
3
4

hash := make(map[string]int, 3)
hash["1"] = 2
hash["3"] = 4
hash["5"] = 6

1
2
3
4
5
6

hash := make(map[string]int, 26)
vstatk := []string{"1", "2", "3", ... ， "26"}
vstatv := []int{1, 2, 3, ... , 26}
for i := 0; i < len(vstak); i++ {
    hash[vstatk[i]] = vstatv[i]
}

1
2

v := m[key] 
v, ok := m[key]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

import (
    "fmt"
    "time"
)

type TimeStruct struct {
    Date time.Time
    Id   int64
}

func main() {
    dat, _ := time.Parse("2006-01-02", "2019-01-01")
    m := map[string]int{"one": 1, "two": 2, "three": 3}
    m2 := map[TimeStruct]int{TimeStruct{Date: dat, Id: 1}: 1, TimeStruct{Date: dat, Id: 2}: 2, TimeStruct{Date: dat, Id: 3}: 3}
    v1 := m["two"]
    v2, ok := m["two"]
    v3 := m2[TimeStruct{Date: dat, Id: 2}]
    fmt.Println(v1, v2, v3, ok)
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

# command-line-arguments
main.main STEXT size=1002 args=0x0 locals=0x348 funcid=0x0 align=0x0
    ......
    0x025b 00603     LEAQ    type:map[string]int(SB), AX
    0x0262 00610     LEAQ    main..autotmp_22+176(SP), BX
    0x026a 00618     LEAQ    go:string."two"(SB), CX
    0x0271 00625     MOVL    $3, DI
    0x0276 00630     CALL    runtime.mapaccess1_faststr(SB)
    0x027b 00635     MOVQ    (AX), DX
    0x027e 00638     MOVQ    DX, main.v1+64(SP)
    0x0283 00643     LEAQ    type:map[string]int(SB), AX
    0x028a 00650     LEAQ    main..autotmp_22+176(SP), BX
    0x0292 00658     LEAQ    go:string."two"(SB), CX
    0x0299 00665     MOVL    $3, DI
    0x029e 00670     PCDATA    $1, $3
    0x029e 00670     NOP
    0x02a0 00672     CALL    runtime.mapaccess2_faststr(SB)
    0x02a5 00677     MOVB    BL, main.ok+47(SP)
    0x02a9 00681     MOVQ    (AX), DX
    0x02ac 00684     MOVQ    DX, main.v2+56(SP)
    0x02b1 00689     MOVQ    main..autotmp_55+80(SP), SI
    0x02b6 00694     MOVQ    SI, main..autotmp_19+96(SP)
    0x02bb 00699     MOVQ    main..autotmp_56+72(SP), SI
    0x02c0 00704     MOVQ    SI, main..autotmp_19+104(SP)
    0x02c5 00709     MOVQ    main..autotmp_57+88(SP), SI
    0x02ca 00714     MOVQ    SI, main..autotmp_19+112(SP)
    0x02cf 00719     MOVQ    $2, main..autotmp_19+120(SP)
    0x02d8 00728     LEAQ    type:map[main.TimeStruct]int(SB), AX
    0x02df 00735     LEAQ    main..autotmp_19+96(SP), CX
    0x02e4 00740     LEAQ    main..autotmp_31+128(SP), BX
    0x02ec 00748     PCDATA    $1, $0
    0x02ec 00748     CALL    runtime.mapaccess1(SB)
    0x02f1 00753     MOVQ    (AX), DX
    0x02f4 00756     MOVQ    DX, main.v3+48(SP)
    0x02f9 00761     MOVUPS    X15, main..autotmp_45+224(SP)
    0x0302 00770     MOVUPS    X15, main..autotmp_45+240(SP)
    ......

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

//go 1.20.3  path:/src/cmd/complie/internal/typecheck/_builtin/runtime.go

func mapaccess1(mapType *byte, hmap map[any]any, key *any) (val *any)
func mapaccess1_fast32(mapType *byte, hmap map[any]any, key uint32) (val *any)
func mapaccess1_fast64(mapType *byte, hmap map[any]any, key uint64) (val *any)
func mapaccess1_faststr(mapType *byte, hmap map[any]any, key string) (val *any)
func mapaccess1_fat(mapType *byte, hmap map[any]any, key *any, zero *byte) (val *any)
func mapaccess2(mapType *byte, hmap map[any]any, key *any) (val *any, pres bool)
func mapaccess2_fast32(mapType *byte, hmap map[any]any, key uint32) (val *any, pres bool)
func mapaccess2_fast64(mapType *byte, hmap map[any]any, key uint64) (val *any, pres bool)
func mapaccess2_faststr(mapType *byte, hmap map[any]any, key string) (val *any, pres bool)
func mapaccess2_fat(mapType *byte, hmap map[any]any, key *any, zero *byte) (val *any, pres bool)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91

// go 1.20.3 path:/runtiime/map.go

func mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {

    //如果哈希表为空，或者哈希表的元素个数为0，那么直接零值对应的指针
    if h == nil || h.count == 0 {
        // 根据 Go 语言规范，传入非 comparable 类型时候，应该 panic，而不是返回空值
        if t.hashMightPanic() {
            t.hasher(key, 0) // see issue 23734
        }
        return unsafe.Pointer(&zeroVal[0])
    }
    //如果正在进行并发读写操作，那么直接报错
    if h.flags&hashWriting != 0 {
        throw("concurrent map read and map write")
    }
    //根据key计算哈希值
    hash := t.hasher(key, uintptr(h.hash0))
    //计算哈希值对应的桶的最大索引
    m := bucketMask(h.B)
    //计算哈希值对应的桶的地址
    b := (*bmap)(add(h.buckets, (hash&m)*uintptr(t.bucketsize)))
    /**
    如果 oldbuckets 不为空, 说明那么map发生了扩容,
    如果有扩容发生，老的buckets中的数据可能还未搬迁至新的buckets里
    所以需要先在老的buckets中找
    */
    if c := h.oldbuckets; c != nil {
        /**
        如果当前不是等大扩容(后面扩容部分会详细介绍)，就是桶的数量增加了一倍，这里直接除 2 (即 >> 1)缩小回来，就能对应到在老 bucket 中的位置
        */
        if !h.sameSizeGrow() {
            m >>= 1
        }
        // 计算老的 bucket 的地址
        oldb := (*bmap)(add(c, (hash&m)*uintptr(t.bucketsize)))
        /** 
        判断 bucket 是否已经迁移
        如果在oldbuckets中tophash[0]的值，为evacuatedX、evacuatedY，evacuatedEmpty其中之一,则evacuated()返回为true，代表搬迁完成
        因此，只有当搬迁未完成时，才会从此oldbucket中遍历
        */
        if !evacuated(oldb) {
            b = oldb
        }
    }
    //获取哈希值对应桶中的tophash,桶内的 hash定位仅使用 hash的高 8 位
    top := tophash(hash)
    /**
      下面这个循环会遍历 key 对应的所有桶中的数据。一次循环找一个桶，找不到就沿着 overflow 指针找下一个溢出桶
      双重循环遍历：外层循环是从桶到溢出桶遍历；内层是桶中的cell遍历
      跳出循环的条件有三种：
      第一种是已经找到key值；
      第二种是当前桶再无溢出桶；
      第三种是当前桶中有cell位的tophash值是emptyRest，这个值在前面解释过，它代表此时的桶后面的cell还未利用，所以无需再继续遍历。
    */
bucketloop:
    for ; b != nil; b = b.overflow(t) {
        for i := uintptr(0); i < bucketCnt; i++ {
            // 通过对比 tophash 来做初步定位
            if b.tophash[i] != top {
                /**
                emptyRest 是特殊的 tophash，该值表明该位置为空，且后面也为空，无需再向后找。
                */
                if b.tophash[i] == emptyRest {
                    break bucketloop
                }
                continue
            }
            // 直接计算偏移量找到 key 的地址
            //因为在bucket中key是用连续的存储空间存储的，因此可以通过bucket地址+数据偏移量（bmap结构体的大小）+ keysize的大小，得到k的地址
            k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
            //如果key值是间接引用的，那么就获取实际key值指针
            if t.indirectkey() {
                k = *((*unsafe.Pointer)(k))
            }
            //tophash相同也可能是hash碰撞，因此这里要确定当前键值与目标键值相等，如果相同则表示找到了
            if t.key.equal(key, k) {
                // 和找 key 一样，直接计算偏移量找到 value
                e := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize))
                //如果value值是间接引用的，那么就获取实际value值指针
                if t.indirectelem() {
                    e = *((*unsafe.Pointer)(e))
                }
        //返回value值指针
                return e
            }
        }
    }
    // 没找到的情况下，返回类型零值
    return unsafe.Pointer(&zeroVal[0])
}

1
2
3

func bucketShift(b uint8) uintptr {
    return uintptr(1) << (b & (goarch.PtrSize*8 - 1))
}

1
2
3

func bucketMask(b uint8) uintptr {
    return bucketShift(b) - 1
}

1
2
3

hash := t.hasher(key, uintptr(h.hash0))
m := bucketMask(h.B)
b := (*bmap)(add(h.buckets, (hash&m)*uintptr(t.bucketsize)))

1
2
3
4

hash值： 10010111000011110110110010001111001010100010010110010101010 01010
bucket最大索引：                                 &                    11111
----------------------------------------------------------------------------------------
                                                                    01010 = 10

1
2
3
4
5
6
7

//go 1.20.3  path:/src/cmd/complie/internal/typecheck/_builtin/runtime.go
func mapassign(mapType *byte, hmap map[any]any, key *any) (val *any)
func mapassign_fast32(mapType *byte, hmap map[any]any, key uint32) (val *any)
func mapassign_fast32ptr(mapType *byte, hmap map[any]any, key unsafe.Pointer) (val *any)
func mapassign_fast64(mapType *byte, hmap map[any]any, key uint64) (val *any)
func mapassign_fast64ptr(mapType *byte, hmap map[any]any, key unsafe.Pointer) (val *any)
func mapassign_faststr(mapType *byte, hmap map[any]any, key string) (val *any)

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145