Map(原理)

 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

// This file contains the implementation of Go's map type.
//
// A map is just a hash table. The data is arranged
// into an array of buckets. Each bucket contains up to
// 8 key/elem pairs. The low-order bits of the hash are
// used to select a bucket. Each bucket contains a few
// high-order bits of each hash to distinguish the entries
// within a single bucket.
//
// If more than 8 keys hash to a bucket, we chain on
// extra buckets.
//
// When the hashtable grows, we allocate a new array
// of buckets twice as big. Buckets are incrementally
// copied from the old bucket array to the new bucket array.
//
// Map iterators walk through the array of buckets and
// return the keys in walk order (bucket #, then overflow
// chain order, then bucket index).  To maintain iteration
// semantics, we never move keys within their bucket (if
// we did, keys might be returned 0 or 2 times).  When
// growing the table, iterators remain iterating through the
// old table and must check the new table if the bucket
// they are iterating through has been moved ("evacuated")
// to the new table.

// Picking loadFactor: too large and we have lots of overflow
// buckets, too small and we waste a lot of space. I wrote
// a simple program to check some stats for different loads:
// (64-bit, 8 byte keys and elems)
//
// Picking loadFactor: 太大会有很多溢出的桶，太小会浪费很多空间。
// 我写了一个简单的程序来检查不同加载的一些统计信息:(64-bit, 8 byte keys and elems)
//  loadFactor    %overflow  bytes/entry     hitprobe    missprobe
//        4.00         2.13        20.77         3.00         4.00
//        4.50         4.05        17.30         3.25         4.50
//        5.00         6.85        14.77         3.50         5.00
//        5.50        10.55        12.94         3.75         5.50
//        6.00        15.27        11.67         4.00         6.00
//        6.50        20.90        10.79         4.25         6.50  -- loadFactor = 13/2
//        7.00        27.14        10.15         4.50         7.00
//        7.50        34.03         9.73         4.75         7.50
//        8.00        41.10         9.40         5.00         8.00
//
// %overflow   = percentage of buckets which have an overflow bucket # 有溢出桶的桶的百分比
// bytes/entry = overhead bytes used per key/elem pair  # 每个 key/elem 对使用的开销字节数
// hitprobe    = # of entries to check when looking up a present key # 在查找当前键时要检查的条目
// missprobe   = # of entries to check when looking up an absent key # 在查找缺失键时要检查的条目
//
// Keep in mind this data is for maximally loaded tables, i.e. just
// before the table grows. Typical tables will be somewhat less loaded.

 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

// A header for a Go map.
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.
    
    // 1. 已经存储的键值对个数，len(map) == count
    // 2. map不能使用cap()函数，cap()函数是计算容量，对于map来说意义不大
    count     int // # live cells == size of map.  Must be first (used by len() builtin)
    flags     uint8 // 当前hmap的状态，比如正处于写入数据中等，参看下面的常量
    // 【常规桶】个数等于 2^B，make()初始化时该值会被设置，注意这里并【没用】包含溢出桶的数量
    B         uint8  // log_2 of # of buckets (最多可以容纳 loadFactor * 2^B items)
    // 已使用的溢出桶数量，用于是否等量扩容判断，在make初始化和扩容初始化时被重置为0
    // 已使用溢出桶的计数规则：
    //  1. 常规桶 h.B <= 15 时，每使用了一个溢出桶 h.noverflow++
    //  2. 常规桶 h.B > 16 时，按照一定概率增加溢出桶 1/((1 << (h.B-15))-1) 的概率 h.noverflow++
    noverflow uint16 // approximate number of overflow buckets; see incrnoverflow for details
    // 在make初始化时根据随机数生成
    // hash随机数，用于生成key的hash值，make初始化时该值会被设置
    hash0     uint32 // hash seed	

    // 常规桶起始地址，make初始化时该值会被设置
    // 该值也许为nil，当count==0时，在【[key] = elem】时会初始化分配内存
    buckets    unsafe.Pointer // array of 2^B Buckets. may be nil if count==0.
    // 当存在扩容时会把hmap.buckets值拷贝到hmap.oldbuckets
    // 这也是判断扩容的条件 hmap.oldbuckets != nil
    oldbuckets unsafe.Pointer // previous bucket array of half the size, non-nil only when growing
    // 记录下一个要被迁移的旧桶编号，在扩容初始化时被重置为0，被分摊到到每次map操作中渐进迁移
    nevacuate  uintptr  // progress counter for evacuation (buckets less than this have been evacuated)

    // make初始化时extra.nextOverflow改值会被设置，记录溢出桶的首地址
    //  溢出桶分配规则常规桶 【h.B >= 4】，就会预分配 【h.B-4】 个溢出桶备用
    // extra 主要是记录分配的备用空闲溢出桶地址 extra.nextOverflow，以及分配过的无指针溢出桶记录在extra.overflow
    extra *mapextra // optional fields	溢出桶信息 以及 扩容信息
}

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

func (h *hmap) createOverflow() {
    if h.extra == nil {	
        h.extra = new(mapextra)
    }
    if h.extra.overflow == nil {
        // slice多采用make()创建，这里采用new创建
        // 也就是只是创建24B大小内存，&slice{0,0,0}
        // 后续overflow字段会通过append()函数添加元素
        // 当bmap是指针类型时，用于存储溢出bmap，以免被GC给回收了
        h.extra.overflow = new([]*bmap) 
    }
}

1
2
3
4

// 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 // true.处于扩容状态
}

1
2
3
4

// sameSizeGrow reports whether the current growth is to a map of the same size.
func (h *hmap) sameSizeGrow() bool {
    return h.flags&sameSizeGrow != 0 // true.等量扩容
}

1
2
3
4
5
6
7
8

// noldbuckets calculates the number of buckets prior to the current map growth.
func (h *hmap) noldbuckets() uintptr {
    oldB := h.B
    if !h.sameSizeGrow() {
        oldB--
    }
    return bucketShift(oldB) // 1 << B
}

1
2
3
4

// oldbucketmask provides a mask that can be applied to calculate n % noldbuckets().
func (h *hmap) oldbucketmask() uintptr {
    return h.noldbuckets() - 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

// incrnoverflow increments h.noverflow.
// noverflow counts the number of overflow buckets.
// This is used to trigger same-size map growth.
// See also tooManyOverflowBuckets.
// To keep hmap small, noverflow is a uint16.
// When there are few buckets, noverflow is an exact count.
// When there are many buckets, noverflow is an approximate count.
func (h *hmap) incrnoverflow() {	// 增加使用的溢出桶计数器
    // We trigger same-size map growth if there are
    // as many overflow buckets as buckets.
    // We need to be able to count to 1<<h.B.
    // 
    // 如果溢出桶和常规桶一样多，我们就会触发等量扩容map。我们需要能够数到 1<<h.B。
    if h.B < 16 {       // 当桶的数量 <= 2^15 溢出桶加一
        h.noverflow++
        return
    }
    // Increment with probability 1/(1<<(h.B-15)).
    // When we reach 1<<15 - 1, we will have approximately
    // as many overflow buckets as buckets.
    // 
    // 以1/(1<<(h.B-15))概率递增加一
    mask := uint32(1)<<(h.B-15) - 1	
    // Example: if h.B == 18, then mask == 7,
    // and fastrand & 7 == 0 with probability 1/8.
    if fastrand()&mask == 0 {
        h.noverflow++
    }
}

 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

func (h *hmap) newoverflow(t *maptype, b *bmap) *bmap {
    var ovf *bmap // 分配的溢出桶 *bmap
    // 当前溢出桶信息不为空 并且 下一个溢出桶不为空 直接从后面获取
    if h.extra != nil && h.extra.nextOverflow != nil {	
        // We have preallocated overflow buckets available.
        // See makeBucketArray for more details.
        // 
        // 我们有预先分配的溢出桶可用。更多细节请参见makeBucketArray方法。
        ovf = h.extra.nextOverflow
        // 判断溢出桶的overflow字段是否为nil，用于判断分配的备用溢出桶使用已用完
        // 参看makeBucketArray方法中把最后一个溢出桶overflow指向了第一个常规桶地址
        if ovf.overflow(t) == nil {
            // We're not at the end of the preallocated overflow buckets. Bump the pointer.
            //
            // 我们还没有到达预分配的溢出桶的末尾。碰一下指针。
            h.extra.nextOverflow = (*bmap)(add(unsafe.Pointer(ovf), uintptr(t.bucketsize)))	// 下一个空闲的溢出桶
        } else { // 已经是最后一个备用的溢出桶了（最后一个溢出桶指向了第一个常规桶，其他溢出桶都应该未nil）
            // This is the last preallocated overflow bucket.
            // Reset the overflow pointer on this bucket,
            // which was set to a non-nil sentinel value.
            //
            // 这是最后一个预分配的溢出桶。
            // 重置此桶上的溢出指针，该指针被设置为非nil哨兵值。
            ovf.setoverflow(t, nil) // ovf.overflow = nil
            h.extra.nextOverflow = nil
        }
    } else {
        // 溢出桶以分配完了 或者 没有分配溢出桶时
        // 注意：这里直接调用new()函数分配的
        ovf = (*bmap)(newobject(t.bucket))	
    }
    
    // 已使用溢出桶计数器
    h.incrnoverflow()	
    // 桶不包含指针
    if t.bucket.ptrdata == 0 {
        h.createOverflow()	// 防止 h.extra 或 h.extra.overflow 没有初始化
        // 将分配的溢出桶保存在h.extra.overflow中，主要是防止这部分内存不该被GC清理，结果被清除了
        *h.extra.overflow = append(*h.extra.overflow, ovf)
    }
    b.setoverflow(t, ovf)   // b.overflow = ovf
    return ovf
}

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

// 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通常包含该桶中每个键的散列值的顶部字节。
    // 如果tophash[0] < minTopHash，则tophash[0]为桶疏散状态。
    // const minTopHash = 5 
    // const bucketCnt = 8;
    tophash [bucketCnt]uint8    // [8]uint8
    // Followed by bucketCnt keys and then bucketCnt 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. 
    //
    // 接下来是bucketCnt的keys，然后是bucketCnt的elems。
    // 注意: 将所有key打包在一起，然后将所有elem打包在一起
    // 这比交替使用key/elem/key/elem/…但它允许我们消除所需的内边距，例如 map[int64]int8。
    // 后跟一个溢出指针。
}

1
2
3
4
5
6
7
8

func evacuated(b *bmap) bool {
    h := b.tophash[0]
    // 参看后面 consts 中相关常量定义
    // const emptyOne = 1
    // const minTopHash = 5
    // return h IN (2,3,4)
    return h > emptyOne && h < minTopHash
}

1
2
3
4

func (b *bmap) overflow(t *maptype) *bmap {
    // b + bucketsize - goarch.PtrSize
    return *(**bmap)(add(unsafe.Pointer(b), uintptr(t.bucketsize)-goarch.PtrSize))
}

1
2
3
4

func (b *bmap) setoverflow(t *maptype, ovf *bmap) {
    // bmap.overflow = ovf
    *(**bmap)(add(unsafe.Pointer(b), uintptr(t.bucketsize)-goarch.PtrSize)) = ovf
}

1
2
3
4
5

func (b *bmap) keys() unsafe.Pointer {
    // dataOffset 参看后面 consts 中的常量定义
    // dataOffset -> [8]uint8
    return add(unsafe.Pointer(b), dataOffset)
}

 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

// mapextra holds fields that are not present on all maps.
type mapextra struct {
    // If both key and elem do not contain pointers and are inline, then we mark bucket
    // type as containing no pointers. This avoids scanning such maps.
    // However, bmap.overflow is a pointer. In order to keep overflow buckets
    // alive, we store pointers to all overflow buckets in hmap.extra.overflow and hmap.extra.oldoverflow.
    // overflow and oldoverflow are only used if key and elem do not contain pointers.
    // overflow contains overflow buckets for hmap.buckets.
    // oldoverflow contains overflow buckets for hmap.oldbuckets.
    // The indirection allows to store a pointer to the slice in hiter.
    //
    // 如果 key 和 elem 都不包含指针并且是允许内联(inline)的，那么我们将bucket类型标记为【不包含指针】。这样避免了扫描这样的map。
    // 然而 bmap.overflow 是一个指针。
    // 为了保持overflow桶是alive(活跃的不被GC回收)，我们将指向所有overflow桶的指针存储在hmap.extra.overflow和hmap.extra.oldoverflow中
    // 【仅当 key 和 elem 不包含指针时，才使用 overflow 和 oldoverflow。】因为不包含指针才容易被GC回收，因此需要保存。
    // overflow 包含用于 hmap.buckets 的overflow桶集
    // oldoverflow 包含用于 hmap.oldbuckets 的overflow桶集
    // 间接允许在hiter中存储一个指向切片的指针。(hiter是遍历相关结构)
    overflow    *[]*bmap // 在 key 和 elem 不包含指针时，把已经用到的溢出桶存储起来，主要是保存 alive
    oldoverflow *[]*bmap // 扩容正在进行时，把 overflow 数据拷贝到这里 

    // nextOverflow holds a pointer to a free overflow bucket.
    // 
    // nextOverflow保存了一个指向空闲溢出桶的指针。
    // 下一个尚未使用的溢出桶，这里桶之间是一个链表链接所有的溢出桶。
    // 该值在make函数中被设置成申请的首个溢出桶
    nextOverflow *bmap	
}

 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

const (
    // Maximum number of key/elem pairs a bucket can hold.
    // 
    // 一个桶可以容纳的最大 key/elem 对数量
    bucketCntBits = 3
    bucketCnt     = 1 << bucketCntBits // 2^3 = 8

    // Maximum average load of a bucket that triggers growth is 6.5.
    // Represent as loadFactorNum/loadFactorDen, to allow integer math.
    // 
    // 触发增长的桶的最大平均负载为13/2 = 6.5。
    // 表示为 loadFactorNum/loadFactorDen ，允许进行整数运算。
    loadFactorNum = 13  // loadFactorNum/loadFactorDen = 6.5
    loadFactorDen = 2

    // Maximum key or elem size to keep inline (instead of mallocing per element).
    // Must fit in a uint8.
    // Fast versions cannot handle big elems - the cutoff size for
    // fast versions in cmd/compile/internal/gc/walk.go must be at most this elem.
    // 
    // 保存inline的最大 key 或 elem 大小(而不是为每个元素分配内存)
    // 必须适配在uint8中。快速版本不能处理大元素-在cmd/compile/internal/gc/walk中快速版本的截止大小。Go最多只能是这个elem。
    maxKeySize  = 128 // map键最大内存值 128B，超过该值则是桶的key是间接存储的，也就是只是存储的是指针
    maxElemSize = 128 // map值最大内存值 128B，超过该值则是桶的elem是间接存储的，也就是只是存储的是指针

    // data offset should be the size of the bmap struct, but needs to be
    // aligned correctly. For amd64p32 this means 64-bit alignment
    // even though pointers are 32 bit.
    // 
    // dataOffset 是bmap结构体的长度，但需要正确对齐
    // 对于amd64p32，这意味着即使指针是32位，也会进行64位对齐。
    dataOffset = unsafe.Offsetof(struct {
        b bmap      // 8B
        v int64     // 8B
    }{}.v) // dataOffset = 8B   bmap桶的第一个key偏移量

    // 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).
    // 
    // 可能的 tophash 值。我们保留一些特殊标记的可能性。
    // 每个桶(包括它的溢出桶，如果有的话)的所有条目都将处于 evacuated* 状态(除非在使用evacuate()方法时，这种情况只发生在map写操作期间，
    // 因此，在这段时间内，没有其他人可以观察map)。
    // 当前格为空的默认状态，后面格都为空不存在其他数据
    emptyRest      = 0 // this cell is empty, and there are no more non-empty cells at higher indexes or overflows.
    // 当前格为空，后面格还存在其他数据。在当前格被删除时会被标记为1
    emptyOne       = 1 // this cell is empty
    // key/elem是有效的，entry已被疏散到翻倍后的新桶里，原来的桶号处
    evacuatedX     = 2 // key/elem is valid.  Entry has been evacuated to first half of larger table.
    // key/elem是有效的，entry已被疏散到翻倍后的新桶里，原来桶号的2倍处
    evacuatedY     = 3 // same as above, but evacuated to second half of larger table.
    // 单元格是空的。在扩容进行中被标记从 0或1标记为4
    evacuatedEmpty = 4 // cell is empty, bucket is evacuated.
    // 正常填充单元格的最小值，比如某个key计算后的hash值为0则填充为5。
    minTopHash     = 5 // minimum tophash for a normal filled cell.

    // flags
    // 可能有一个使用buckets的迭代器
    iterator     = 1 // there may be an iterator using buckets
    // 可能有一个使用oldbuckets的迭代器
    oldIterator  = 2 // there may be an iterator using oldbuckets
    // 一个goroutine正在向map写入数据，用于判断map是否在读写删除并发操作
    // 在m[key] = elem时被设置或在delete删除key时被设置
    hashWriting  = 4 // a goroutine is writing to the map
    // 等量扩容标志位
    sameSizeGrow = 8 // the current map growth is to a new map of the same size

    // sentinel bucket ID for iterator checks
    // 迭代器检查的哨兵桶ID，如果桶号为该值不需要检查
    // 迭代器相关，在扩容进行中迭代器用于检查的桶号
    noCheck = 1<<(8*goarch.PtrSize) - 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

type maptype struct {
    typ    _type        // map类型
    key    *_type       // key类型
    elem   *_type       // elem类型
    
    // 桶的类型，桶包含tophashs、keys、elems、overflow这四块
    // 由于key/elem是不确定的类型，所以bucket也是不同的类型
    // bucket是否包含指针类型，是取决于该结构中是否存在指针
    //	1. tophashs 是非指针
    //  2. keys、elems 是根据具体情况的
    //  3. overflow 是个指针，那么是否意味则bucket是否包含指针类型?
    // 其实bucket是否包含指针类型是根据keys、elems决定的，原因是overflow是用户操作不到的
    // 因此处理这个特殊情况时，采用了非指针形式采用mapextra结构保存溢出桶数据，以便不被GC回收
    bucket *_type // internal type representing a hash bucket
    // function for hashing keys (ptr to key, seed) -> hash
    // hash函数，用于(key, h.hash0)
    hasher     func(unsafe.Pointer, uintptr) uintptr	
    // size of key slot
    keysize    uint8  // key值大小
    // size of elem slot
    elemsize   uint8  // value值大小
    // size of bucket
    bucketsize uint16 // 桶大小
    flags      uint32 // map的标志位
}

1
2
3
4
5
6

// Note: flag values must match those used in the TMAP case
// in ../cmd/compile/internal/reflectdata/reflect.go:writeType.
func (mt *maptype) indirectkey() bool { // store ptr to key instead of key itself
    // flags = 1：key占用内存大于 128B
    return mt.flags&1 != 0	
}

1
2
3
4

func (mt *maptype) indirectelem() bool { // store ptr to elem instead of elem itself
    // flags = 2：elem占用内存大于 128B
    return mt.flags&2 != 0	
}

1
2
3
4

func (mt *maptype) reflexivekey() bool { // true if k==k for all keys
    // flags = 4：说明 x == x始终是成立的
    return mt.flags&4 != 0	
}

1
2
3
4

func (mt *maptype) needkeyupdate() bool { // true if we need to update key on an overwrite
    // flags = 8：需要更新slot的key
    return mt.flags&8 != 0	
}

1
2
3
4

func (mt *maptype) hashMightPanic() bool { // true if hash function might panic
    // flags = 16：key生成hash可能panic的
    return mt.flags&16 != 0	
}

 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

// makemap implements Go map creation for make(map[k]v, hint).
// If the compiler has determined that the map or the first bucket
// can be created on the stack, h and/or bucket may be non-nil.
// If h != nil, the map can be created directly in h.
// If h.buckets != nil, bucket pointed to can be used as the first bucket.
func makemap(t *maptype, hint int, h *hmap) *hmap {
    // MulUintptr 返回 a * b 以及乘法是否溢出
    //      mem = uintptr(hint) * t.bucket.size
    // 这里使用 key/elem 对乘上 桶大小 显示是在扩大计算内存，因为 hint 一定是大于 桶的数量的
    mem, overflow := math.MulUintptr(uintptr(hint), t.bucket.size)
    if overflow || mem > maxAlloc {
        hint = 0
    }

    // initialize Hmap
    if h == nil {
        // 初始化 hmap
        // 注意这里使用了new函数创建的
        h = new(hmap)	
    }
    // 生成一个随机数用于后续key的hash，该值在桶每次清空时该值会从新生成随机值
    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的大小，它将保存请求的元素
    // 对于 hint < 0 overLoadFactor 返回 false，因为 hint < bucketCnt。
    B := uint8(0)
    // 计算保存hint个key/elem对不扩容最小需要的B的数量
    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.
    // 
    // 分配初始hash表，如果B == 0，则稍后(在mapassign中，也就是存储数据过程中)延迟分配buckets字段，
    // 如果hint很大，则清空该内存可能需要一段时间。
    if h.B != 0 {
        var nextOverflow *bmap  // 用于记录 makeBucketArray 是否分配了溢出桶
        // makeBucketArray 根据B分配常规桶和溢出桶，如果分配了溢出桶则将最后一个溢出桶地址指向第一个常规桶地址
        // 溢出桶分配规则 B >= 4 分配最少 B-4 个溢出桶备用，溢出桶数量 >= 1 << (B-4)
        h.buckets, nextOverflow = makeBucketArray(t, h.B, nil)
        if nextOverflow != nil {
            h.extra = new(mapextra)
            // 记录下一个可使用的溢出桶
            h.extra.nextOverflow = nextOverflow
        }
    }

    return h
}

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

// overLoadFactor reports whether count items placed in 1<<B buckets is over loadFactor.
func overLoadFactor(count int, B uint8) bool {
    // const (
    //  bucketCnt = 8
    //  loadFactorNum = 13
    //  loadFactorDen = 2
    // )
    // bucketShift(B) == 1 << B
    // uintptr(count)/bucketShift(B) < loadFactorNum/loadFactorDen
    //
    // return count > 8 && count > 6.5 * (1 << B)
    return count > bucketCnt && uintptr(count) > loadFactorNum*(bucketShift(B)/loadFactorDen)
}

1
2
3
4
5
6
7
8

// bucketShift returns 1<<b, optimized for code generation.
func bucketShift(b uint8) uintptr {
    // Masking the shift amount allows overflow checks to be elided.
    // 
    // 屏蔽移位量可以省略溢出检查。
    // goarch.PtrSize 64位下为8，32位下为4; goarch.PtrSize*8 - 1 掩码为了防止溢出
    return uintptr(1) << (b & (goarch.PtrSize*8 - 1))   // 1 << b
}

 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

// makeBucketArray initializes a backing array for map buckets.
// 1<<b is the minimum number of buckets to allocate.
// dirtyalloc should either be nil or a bucket array previously
// allocated by makeBucketArray with the same t and b parameters.
// If dirtyalloc is nil a new backing array will be alloced and
// otherwise dirtyalloc will be cleared and reused as backing array.
func makeBucketArray(t *maptype, b uint8, dirtyalloc unsafe.Pointer) (buckets unsafe.Pointer, nextOverflow *bmap) {
    // base := 1 << b
    base := bucketShift(b) // 常规桶数量 
    nbuckets := base // 存储(常规桶 + 溢出桶)的总数量
    // For small b, overflow buckets are unlikely.
    // Avoid the overhead of the calculation.
    // 
    // 对于小值b来说，溢出桶不太可能出现。避免计算的开销。
    // 溢出桶分配规则 B >= 4 分配最少 B-4 个溢出桶备用。
    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.
        // 
        // 再加上用该值b插入元素的中位数所需的溢出桶的估计数量。
        // nbuckets += 1 << (b - 4)
        nbuckets += bucketShift(b - 4) // 常规桶 + 溢出桶
        sz := t.bucket.size * nbuckets // 计算全部桶(常规桶 + 溢出桶)所需内存大小
        up := roundupsize(sz) // 匹配最接近sz的内存大小规格
        if up != sz { // 匹配的内存规格偏大	
            // 调整 nbuckets 数量，这里应该是偏大设置
            // 因为不能能匹配后出现偏小的情况
            nbuckets = up / t.bucket.size
        }
    }

    if dirtyalloc == nil {
        // 没有可重新利用的内存块，重新向内存管理系统申请内存
        // buckets 申请的桶首地址 包含常规桶和溢出桶，因此常规桶和溢出桶是一整块连续的内存
        buckets = newarray(t.bucket, int(nbuckets))	
    } else {
        // dirtyalloc was previously generated by
        // the above newarray(t.bucket, int(nbuckets))
        // but may not be empty.
        // 
        // dirtyalloc是由上述 newarray(t.bucket, int(nbuckets)) 生成的，但不能为空。
        buckets = dirtyalloc // 桶内存块地址
        size := t.bucket.size * nbuckets // 内存块大小
        if t.bucket.ptrdata != 0 {
            // 当前桶中存在指针数据时
            // 重置从buckets地址开始长度为size大小的内存
            memclrHasPointers(buckets, size)
        } else {
            // 当前桶中不存在指针数据时
            // 重置从buckets地址开始长度为size大小的内存
            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.
        //
        // 我们预先分配了一些溢出桶。
        // 为了将跟踪这些溢出桶的开销降到最低，我们使用约定:如果预分配的溢出桶的overflow指针为nil，则通过碰撞指针来提供更多可用的内存。
        // 我们需要为最后一个溢出桶提供一个安全的 non-nil 指针; 就用常规桶吧。用于在分配溢出桶时判断溢出桶以分配完
        nextOverflow = (*bmap)(add(buckets, base*uintptr(t.bucketsize))) // 首个溢出桶 *bmap
        last := (*bmap)(add(buckets, (nbuckets-1)*uintptr(t.bucketsize)))// 最后一个溢出桶 *bmap
        // 之所以将最后一个溢出桶overflow指向第一个常规桶地址是用于分配溢出桶是判断是否分配完参看(*hmap).newoverflow()方法
        last.setoverflow(t, (*bmap)(buckets))   // 最后一个溢出桶指针指向首个常规桶
    }
    return buckets, nextOverflow
}

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

// newarray allocates an array of n elements of type typ.
func newarray(typ *_type, n int) unsafe.Pointer {
    if n == 1 {
        // 只有一个桶，直接申请
        return mallocgc(typ.size, typ, true)
    }
    // 溢出判断，typ.size * uintptr(n) 为桶总共占用的内存
    mem, overflow := math.MulUintptr(typ.size, uintptr(n))
    if overflow || mem > maxAlloc || n < 0 {
        panic(plainError("runtime: allocation size out of range"))
    }
    return mallocgc(mem, typ, true)
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

// makemap_small implements Go map creation for make(map[k]v) and
// make(map[k]v, hint) when hint is known to be at most bucketCnt
// at compile time and the map needs to be allocated on the heap.
func makemap_small() *hmap {
    // 当 hint <= 8 时
    // 初始化 map
    h := new(hmap)
    h.hash0 = fastrand()
    return h
}

1
2
3
4
5
6
7

func mapaccess1_fat(t *maptype, h *hmap, key, zero unsafe.Pointer) unsafe.Pointer {
    e := mapaccess1(t, h, key)
    if e == unsafe.Pointer(&zeroVal[0]) {
        return zero
    }
    return e
}

  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

// mapaccess1 returns a pointer to h[key].  Never returns nil, instead
// it will return a reference to the zero object for the elem type if
// the key is not in the map.
// NOTE: The returned pointer may keep the whole map live, so don't
// hold onto it for very long.
func mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
    if raceenabled && h != nil {
        callerpc := getcallerpc()
        pc := abi.FuncPCABIInternal(mapaccess1)
        racereadpc(unsafe.Pointer(h), callerpc, pc)
        raceReadObjectPC(t.key, key, callerpc, pc)
    }
    if msanenabled && h != nil {
        msanread(key, t.key.size)
    }
    if asanenabled && h != nil {
        asanread(key, t.key.size)
    }
    
    // 1) map未初始化 或 没有key/elem对
    if h == nil || h.count == 0 {
        // 当key为any类型时，在key经过hash时可能会发生panic
        // t.hashMightPanic()判断当前hash函数是否可能发生panic
        // 这是因为 any 存储的值可能不适合作为 map 的 key
        if t.hashMightPanic() {
            // 尝试hash panic
            t.hasher(key, 0) // see issue 23734
        }
        // 直接返回 &zeroVal[0]，返回默认值
        return unsafe.Pointer(&zeroVal[0])
    }
    
    // 2) 当前map存在其他goroutine正在写操作，直接报错不支持并发
    // hashWriting 标志在写map或delete map时被设置
    if h.flags&hashWriting != 0 {
        fatal("concurrent map read and map write")  // 并发的map读写操作
    }
    
    // 3) key根据h.hash0生成hash值，根据上面key为any时这里hash可能会panic
    hash := t.hasher(key, uintptr(h.hash0))
    m := bucketMask(h.B) // map常规桶数量; m = (1 << B) - 1
    // 4) 偏移到当前key对应的常规桶处 *bmap
    b := (*bmap)(add(h.buckets, (hash&m)*uintptr(t.bucketsize)))
    // 5) c != nil 当前map正在扩容中，需要判断当前旧桶数据是否迁移，没迁移数据还在旧桶中
    if c := h.oldbuckets; c != nil {
        // !h.sameSizeGrow() == true; 
        // 翻倍扩容时
        if !h.sameSizeGrow() {
            // There used to be half as many buckets; mask down one more power of two.
            // 
            // 过去桶的数量只有现在的一半;再除一个2的倍数。
            m >>= 1 // 需要把m缩小两倍
        }
        oldb := (*bmap)(add(c, (hash&m)*uintptr(t.bucketsize)))
        // 判断旧桶是否已经迁移了，没有迁移则从旧桶里面取数据
        // 不是2|3|4时表示数据还在旧桶里面，tophash[0] NOT IN (2,3,4)
        if !evacuated(oldb) {
            b = oldb    // 替换为旧桶 *bmap
        }
    }
    
    // 6) top 是 hash 的高八位值，用于快速比对 key
    // hash >> (8*8 - 8)
    top := tophash(hash) // uint8
bucketloop:
    // 7) 遍历当前桶以及后面的溢出桶
    for ; b != nil; b = b.overflow(t) {
        // 遍历当前桶; bucketCnt = 8
        for i := uintptr(0); i < bucketCnt; i++ {
            // 7.1) 当前 tophash 不相等
            if b.tophash[i] != top {
                // const emptyRest = 0
                // 当前桶包括溢出桶后面没有数据了
                if b.tophash[i] == emptyRest {
                    break bucketloop    // 结束遍历
                }
                continue
            }
            
            // 7.2) b.tophash[i] == top; 并不代表一定找到key，可能出现tophash冲突情况
            k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize)) // 找到当前key的地址
            // key的数据是间接存储的，关于常量maxKeySize的相关情况
            if t.indirectkey() {
                k = *((*unsafe.Pointer)(k)) // 拿到key地址
            }
            // 7.3) 调用key的比较函数，比较key和k是否相等。
            // 这里也是key必须是可比较类型的原因
            // 不可比较的类型：
            //  1. map，以及包含map的结构
            //  2. slice，以及包含slice的结构
            // 这里key如果是 NaN 的话比对不通过。
            if t.key.equal(key, k) {
                // 比对成功。偏移到elem元素地址处
                e := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize))
                // elem的数据是间接存储的，关于常量maxElemSize的相关情况
                if t.indirectelem() {
                    e = *((*unsafe.Pointer)(e)) // 拿到elem地址
                }
                return e    // 成功返回找到的elem地址指针
            }
            
            // 未匹配成功出现tophash【冲突】情况
        }
    }
    // map 中没有 key，返回默认值
    return unsafe.Pointer(&zeroVal[0])
}

1
2
3
4

// bucketMask returns 1<<b - 1, optimized for code generation.
func bucketMask(b uint8) uintptr {
    return bucketShift(b) - 1 // (1<<b) - 1
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

// tophash calculates the tophash value for hash.
func tophash(hash uintptr) uint8 {
    // hash >> (8*8 - 8)
    // hash高八位
    top := uint8(hash >> (goarch.PtrSize*8 - 8))	
    // top < 5
    if top < minTopHash {
        top += minTopHash
    }
    return top
}

1
2
3
4
5

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

1
2
3
4
5
6
7
8
9

func mapaccess2_fat(t *maptype, h *hmap, key, zero unsafe.Pointer) (unsafe.Pointer, bool) {
    // 没看错，这里依然是调用的 mapaccess1() 函数
    // 因为如果没找到key会返回&zeroVal[0]，根据该值能判断bool。
    e := mapaccess1(t, h, key)
    if e == unsafe.Pointer(&zeroVal[0]) {
        return zero, false
    }
    return e, true
}

 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

func mapaccess2(t *maptype, h *hmap, key unsafe.Pointer) (unsafe.Pointer, bool) {
    if raceenabled && h != nil {
        callerpc := getcallerpc()
        pc := abi.FuncPCABIInternal(mapaccess2)
        racereadpc(unsafe.Pointer(h), callerpc, pc)
        raceReadObjectPC(t.key, key, callerpc, pc)
    }
    if msanenabled && h != nil {
        msanread(key, t.key.size)
    }
    if asanenabled && h != nil {
        asanread(key, t.key.size)
    }
    if h == nil || h.count == 0 {
        if t.hashMightPanic() {
            t.hasher(key, 0) // see issue 23734
        }
        return unsafe.Pointer(&zeroVal[0]), false // 这里获取失败返回 false
    }
    if h.flags&hashWriting != 0 {
        fatal("concurrent map read and map write")
    }
    hash := t.hasher(key, uintptr(h.hash0))
    m := bucketMask(h.B)
    b := (*bmap)(add(h.buckets, (hash&m)*uintptr(t.bucketsize)))
    if c := h.oldbuckets; c != nil {
        if !h.sameSizeGrow() {
            // There used to be half as many buckets; mask down one more power of two.
            m >>= 1
        }
        oldb := (*bmap)(add(c, (hash&m)*uintptr(t.bucketsize)))
        if !evacuated(oldb) {
            b = oldb
        }
    }
    top := tophash(hash)
bucketloop:
    for ; b != nil; b = b.overflow(t) {
        for i := uintptr(0); i < bucketCnt; i++ {
            if b.tophash[i] != top {
                if b.tophash[i] == emptyRest {
                    break bucketloop
                }
                continue
            }
            k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
            if t.indirectkey() {
                k = *((*unsafe.Pointer)(k))
            }
            if t.key.equal(key, k) {
                e := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize))
                if t.indirectelem() {
                    e = *((*unsafe.Pointer)(e))
                }
                return e, true // 这里获取成功返回 true
            }
        }
    }
    return unsafe.Pointer(&zeroVal[0]), false // 这里获取失败返回 false
}

1
2
3
4
5
6
7

//go:linkname reflect_mapassign reflect.mapassign
func reflect_mapassign(t *maptype, h *hmap, key unsafe.Pointer, elem unsafe.Pointer) {
    // 从map中找到elem应该放入插槽的地址
    p := mapassign(t, h, key)	
    // 拷贝数据，也就四把&v复制给map插槽
    typedmemmove(t.elem, p, elem)	
}

  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
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183

// Like mapaccess, but allocates a slot for the key if it is not present in the map.
func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
    // 1) 未初始化的map不允许写操作
    // 这里就是为什么向nil的map写入数据会panic原因
    if h == nil {
        panic(plainError("assignment to entry in nil map"))
    }
    if raceenabled {
        callerpc := getcallerpc()
        pc := abi.FuncPCABIInternal(mapassign)
        racewritepc(unsafe.Pointer(h), callerpc, pc)
        raceReadObjectPC(t.key, key, callerpc, pc)
    }
    if msanenabled {
        msanread(key, t.key.size)
    }
    if asanenabled {
        asanread(key, t.key.size)
    }
    // 2) 检查map是否存在并发的写操作，删除也是写操作。
    if h.flags&hashWriting != 0 {
        fatal("concurrent map writes")
    }
    // 3) key根据h.hash0生成hash值，根据上面key为any时这里hash可能会panic。
    hash := t.hasher(key, uintptr(h.hash0))

    // Set hashWriting after calling t.hasher, since t.hasher may panic,
    // in which case we have not actually done a write.
    //
    // 在调用t.hasher之后设置hashWriting，因为t.hasher可能会出错，在这种情况下我们实际上并没有写入。
    // 这里使用 ^= 有点小窍门，因为在并发写的情况下可能存在上面的h.flags&hashWriting != 0检查时被跳过了，
    // 所以这个函数最后还需要判断并是否已经发生 ^ 异或 相同得0，不同得1; hashWriting = 4 = 0b100
    // 按照正常逻辑 h.flags 的3bit位应该是0，那么0^1=1。在函数的最后 h.flags&hashWriting == 0 判断时 1&1=1。
    // 异常逻辑 h.flags 的3bit位是1，那么 1^1=0。在函数的最后 h.flags&hashWriting == 0 判断时 0&1=0。因此判断并发发生
    h.flags ^= hashWriting  // 写状态标记

    // 4) 没有分配常规桶，这种情况来自makemap_small()函数，hint<=8 时
    if h.buckets == nil {
        // 申请一个常规桶内存块
        h.buckets = newobject(t.bucket) // newarray(t.bucket, 1)
    }

again:
    // 5) 根据 hash 映射到指定桶号
    bucket := hash & bucketMask(h.B) // bucket = hash & ((1 << B) - 1)
    // 6) 是否正处于扩容中：【等量扩容】 或 【翻倍扩容】
    if h.growing() {    // h.oldbuckets != nil
        // 迁移当前key对应的桶数据到新桶完成部分扩容任务
        // 迁移后会把旧桶数据迁移到新桶，因此以下代码处理新桶即可
        // growWork() 函数在delete(map)和map[k]=v时被调用，渐进式迁移数据
        growWork(t, h, bucket)	
    }
    
    // 7) 寻找对应的桶(*bmap)，key对应的桶 *bmap
    b := (*bmap)(add(h.buckets, bucket*uintptr(t.bucketsize)))
    // top = uint8( hash & (1>>8*8-8) )
    top := tophash(hash)    // hash 高八位，用于快速判断 key

    // inserti 对应key应该放入tophash的slot位置地址
    var inserti *uint8	
    // insertk 对应key应该放入keys的slot位置地址
    var insertk unsafe.Pointer
    // elem 对应key应该放入elems的slot位置地址
    var elem unsafe.Pointer	
bucketloop:
    // 8) 遍历常规桶和溢出桶，寻找slot位置
    // 被删除的slot会被优先使用来存储数据
    for {
        // 8.1) 遍历单个桶; const bucketCnt = 8
        for i := uintptr(0); i < bucketCnt; i++ {
            // 8.1.1) tophash 比对失败
            if b.tophash[i] != top {
                // isEmpty(b.tophash[i]) --> b.tophash[i] <= 1
                // inserti == nil; 寻找到slot后不会再进入这里
                // 这里也是判断当前可能是新增的情况，当前位可以插入数据如果是新增的话。
                if isEmpty(b.tophash[i]) && inserti == nil {
                    // 记录当前插槽位置
                    inserti = &b.tophash[i]
                    insertk = add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
                    elem = add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize))
                }
                
                // b.tophash[i] == 0; 后面没有数据了
                if b.tophash[i] == emptyRest {
                    break bucketloop
                }
                
                // b.tophash[i] == 1
                // 后面有数据需要继续遍历判断是否当前key已经存在在map中了
                continue    // continue的作用就是继续遍历map寻找key
            }
            
            // tophash匹配成功
            //  1. 可能是hash冲突，继续向后寻找
            //  2. 可能是匹配到了key，则是更新
            
            // 8.1.2) 当前key的slot地址
            k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
            if t.indirectkey() {    // key 间接存储
                k = *((*unsafe.Pointer)(k))
            }
            // 8.1.3) 比较key和k是否相等，不相等说明 tophash冲突了
            // 如果存储的 key 是 NaN 这里比对不通过。
            if !t.key.equal(key, k) {
                continue    // key != k 继续向后寻找
            }
            
            // key == k; 匹配成功则本次是更新操作
                
            // already have a mapping for key. Update it.
            // 
            // 已经有一个key的映射。【更新它】。
            // key == key成立，但是可能生成的hash值不同，比如+0和-0
            if t.needkeyupdate() {
                typedmemmove(t.key, k, key) // 把k更新为key
            }
            // 8.1.4) 找到elem地址
            elem = add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize))
            goto done
        }
        ovf := b.overflow(t)    // b后面链接的溢出桶
        // 没有溢出桶了
        if ovf == nil {
            break
        }
        b = ovf
    }
    
    // Did not find mapping for key. Allocate new cell & add entry.
    // 
    // 9) 没有找到key的映射。分配新的单元格并添加entry。新增 key/elem 

    // 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.
    // 
    // 10) 如果我们达到了最大负载系数，或者我们有太多溢出桶，而我们还没有达到增长的一半，就开始增长。
    // h.growing() -> (h.oldbuckets != nil); 是否正在扩容中
    if !h.growing() && (overLoadFactor(h.count+1, h.B) || tooManyOverflowBuckets(h.noverflow, h.B)) {
        hashGrow(t, h)  // 扩容初始化
        // 扩容hash table会使上面的所有操作失效，所以再试一次
        goto again // Growing the table invalidates everything, so try again
    }

    // 11) 常规桶和溢出桶(如果存在)都没找到slot，这时候需要分配新的溢出桶
    if inserti == nil {
        // The current bucket and all the overflow buckets connected to it are full, allocate a new one.
        //
        // 当前桶和连接到它的所有溢出桶已满，分配一个新的桶。
        newb := h.newoverflow(t, b) // 分配一个溢出桶 *bmap
        inserti = &newb.tophash[0]
        insertk = add(unsafe.Pointer(newb), dataOffset)
        elem = add(insertk, bucketCnt*uintptr(t.keysize))
    }

    // store new key/elem at insert position
    //
    // 12) 将新的键/elem存储在插入位置
    if t.indirectkey() {    // key 间接存储
        kmem := newobject(t.key)
        *(*unsafe.Pointer)(insertk) = kmem
        insertk = kmem
    }
    if t.indirectelem() {   // elem 间接存储
        vmem := newobject(t.elem)
        *(*unsafe.Pointer)(elem) = vmem
        // 由于done后面有 t.indirectelem() 判断所有这里没有 elem = vmem 这行代码
    }
    // 13) 拷贝数据
    typedmemmove(t.key, insertk, key) // 保存key的值
    *inserti = top // tophash 保存
    h.count++ // key/elem 对加一

done:
    // 14) 再次判断是否有其他goroutine正在对map进行写操作
    if h.flags&hashWriting == 0 {
        fatal("concurrent map writes")
    }
    h.flags &^= hashWriting // 清除hashWriting标志位
    if t.indirectelem() { // elem 间接存储
        elem = *((*unsafe.Pointer)(elem))
    }
    return elem // 返回当前slot的地址
}

1
2
3
4

// isEmpty reports whether the given tophash array entry represents an empty bucket entry.
func isEmpty(x uint8) bool {
    return x <= emptyOne    // x <= 1
}

1
2
3
4
5

// overLoadFactor reports whether count items placed in 1<<B buckets is over loadFactor.
func overLoadFactor(count int, B uint8) bool {
    // count > 8 && count > 13*((1<<B) / 2)
    return count > bucketCnt && uintptr(count) > loadFactorNum*(bucketShift(B)/loadFactorDen)
}

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

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

1
2
3