Golang Data Structure - Map

map用于存储一系列无序的键值对。 map是一种集合，可以像迭代数组和切片那样迭代它。不过，Map 是无序的，遍历 Map 时返回的键值对的顺序是不确定的。在获取 Map 的值时，如果键不存在，返回该类型的零值。Map 是引用类型，如果将一个 Map 传递给一个函数或赋值给另一个变量，它们都指向同一个底层数据结构，因此对 Map 的修改会影响到所有引用它的变量。

  • 任何可比较的类型都可以是键——所有简单的标量类型（布尔、整数、浮点、复数、字符串）、指针、通道、数组、接口。

  • 不可比较的类型——切片、映射、函数。

map常见设计

Map的底层都是通过哈希表进行实现的。

一般的Map会包含两个主要结构：

  • 数组：数组里的值指向一个链表
  • 链表：目的解决hash冲突的问题，并存放键值

读取一个key值的过程大致如下:

  1. key通过hash函数得到key的hash

  2. key的hash通过取模或者位操作得到key在数组上的索引

  3. 通过索引找到对应的链表

  4. 遍历链表对比key和目标key

  5. 相等则返回value

JDK1.8之前，哈希表底层采用数组+链表实现，即使用链表处理冲突，同一hash值的链表都存储在一个链表里。但是当位于一个桶中的元素较多，即hash值相等的元素较多时，通过key值依次查找的效率较低。

JDK1.8中，哈希表存储采用数组+链表+红黑树实现，当链表长度超过阈值8时，将链表转换为红黑树，这样大大减少了查找时间。

hash函数

哈希表是计算机中最重要的数据结构之一，不仅是因为它$O(1)$的读写性能非常好，它还提供了键值之间的映射。

想要实现一个性能优异的哈希表，需要注意两个关键点：

  • 哈希函数的选择
  • 哈希冲突的解决

实现哈希表的关键点在于哈希函数的选择，哈希函数的选择在很大程度上能够决定哈希表的读写性能。

实际的方式是让哈希函数的结果能够尽可能的均匀分布，然后通过相应的方法来解决哈希冲突的问题。哈希函数映射的结果一定要尽可能均匀，结果不均匀的哈希函数会带来更多的哈希冲突以及更差的读写性能。

如果使用结果分布较为均匀的哈希函数，那么哈希的增删改查的时间复杂度为 $O(1)$；但是如果哈希函数的结果分布不均匀，那么所有操作的时间复杂度可能会达到 $O(n)$，由此看来，选择使用好的哈希函数是至关重要的。

哈希查找表一般会存在“碰撞”的问题，就是说不同的 key 被哈希到了同一个 bucket。 一般有两种应对方法：链表法和开放地址法。

链表法将一个 bucket 实现成一个链表，落在同一个 bucket 中的 key 都会插入这个链表。开放地址法则是碰撞发生后，通过一定的规律，在数组的后面挑选“空位”，用来放置新的 key。

搜索树法一般采用自平衡搜索树，包括：AVL 树，红黑树。自平衡搜索树法的最差搜索效率是 O(logN)，而哈希查找表最差是 O(N)。当然，哈希查找表的平均查找效率是 O(1)，如果哈希函数设计的很好，最坏的情况基本不会出现。还有一点，遍历自平衡搜索树，返回的 key 序列，一般会按照从小到大的顺序；而哈希查找表则是乱序的。

Golang Map

实现原理

Go中的map是一个指针，占用8个字节，指向hmap结构体。每个map的底层结构是hmap，hmap包含若干个结构为bmap的bucket数组。每个bucket底层都采用链表结构。接下来，我们来详细看下map的结构

Go语言解决hash冲突不是链表，实际主要用的数组(内存上的连续空间)，如下图所示：

  • 分别对应的是两个核心的结构体hmap和bmap
  • bmap里有两个数组分别存放key和value

把上面简化的关系转换一下，其实就是这样的一个大致关系，如下图所示：

读取某个key的值的大致过程：

  1. 通过hash函数获取目标key的哈希，哈希和数组的长度通过位操作获取数组位置的索引(备注：获取索引值的方式一般有取模或位操作，位操作的性能好些)

  2. 遍历bmap里的键，和目标key对比获取key的索引(找不到则返回空值)

  3. 根据key的索引通过计算偏移量，获取到对应value

hmap

hmap 是 hashmap 的缩写。map是Go语言的内置数据类型之一，以map关键字作为Go语言的语法之一。runtime层的定义如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 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.
    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
}

  • count ：记录map当前存储的key数量，可以通过builtin包中的len()函数返回map的长度。

  • flags：迭代map或者对map进行写操作的时候，会记录该标志位，用于一些并发场景的检测校验。

  • B：存放当前map存放的bucket数组长度的对数，即len(buckets) == 2^B。

  • noverflow 为 map 中溢出桶的近似数量。当溢出的桶太多时，map 会进行 same-size map growth，其实质是避免桶过大导致内存泄露。

  • hash0 代表生成 hash 的随机数种子。能够为Hash函数的结果引入随机性。

  • buckets 是指向具体的buckets数组的指针。

  • oldbuckets 是在 map 扩容时存储旧buckets数组的，当所有旧桶中的数据都已经转移到了新桶中时，则清空。

  • nevacuate 用于表示扩容的搬迁进度。在扩容时使用，用于标记当前旧桶中小于 nevacuate 的数据都已经转移到了新桶中。

  • extra 当map的key和value都不是指针，Go为了避免GC扫描整个hmap，会将bmap的overflow字段移动到extra

bmap

Go 中桶 buckets 是 bmap 结构。在运行时只列出了首个字段，即一个固定长度为 8 的数组。此字段顺序存储 key 的哈希值的前 8 位。

1
2
3
4
5
6
7
8
9
10
11
12
// 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 [bucketCnt]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.
}

tophash 通常包含此 buckets 中每个键的哈希值的最高字节。 如果 tophash[0] < minTopHash，则 tophash[0] 是一个桶疏散状态。

map 在编译时即确定了 map 中 key、value 及桶的大小，因此在运行时仅仅通过指针操作就可以找到特定位置的元素。在实际编译期间，Go语言的bmap会经过reflect生成真正的bmap类型：

1
2
3
4
5
6
7
type bmap struct {
    topbits  [8]uint8
    keys     [8]keytype
    values   [8]valuetype
    pad      uintptr
    overflow uintptr
}

bmap 就是我们常说的“桶”，桶里面会最多装 8 个 key，这些 key 之所以会落入同一个桶，是因为它们经过哈希计算后，哈希结果是“一类”的。在桶内，又会根据 key 计算出来的 hash 值的高 8 位来决定 key 到底落入桶内的哪个位置（一个桶内最多有 8 个位置）。桶在存储的 tophash 字段后，会存储 key 数组和 value 数组。为了空间利用率，key和value分别存放，超过桶大小的部分会创建新的桶并通过overflow串联起来。顶层的tophash则存放了每个key Hash值的前8位，用于插入时候的快速比较等场景。

mapextra

当 map 的 key 和 value 都不是指针，并且 size 都小于 128 字节的情况下，会把 bmap 标记为不含指针，这样可以避免 gc 时扫描整个 hmap。但是，我们看 bmap 其实有一个 overflow 的字段，是指针类型的，破坏了 bmap 不含指针的设想，这时会把 overflow 移动到 extra 字段来。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// mapextra holds fields that are not present on all maps.
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 的指针
}

特性

引用类型

map是个指针，底层指向hmap，所以是个引用类型

golang 有三个常用的高级类型slice、map、channel, 它们都是引用类型，当引用类型作为函数参数时，可能会修改原内容数据。

golang 中没有引用传递，只有值和指针传递。所以 map 作为函数实参传递时本质上也是值传递，只不过因为 map 底层数据结构是通过指针指向实际的元素存储空间，在被调函数中修改 map，对调用者同样可见，所以 map 作为函数实参传递时表现出了引用传递的效果。

因此，传递 map 时，如果想修改map的内容而不是map本身，函数形参无需使用指针

1
2
3
4
5
6
7
8
9
10
11
12
func TestSliceFn(t *testing.T) {
    m := map[string]int{}
    t.Log(m, len(m))
    // map[a:1]
    mapAppend(m, "b", 2)
    t.Log(m, len(m))
    // map[a:1 b:2] 2
}

func mapAppend(m map[string]int, key string, val int) {
    m[key] = val
}

共享存储空间

map 底层数据结构是通过指针指向实际的元素存储空间 ，这种情况下，对其中一个map的更改，会影响到其他map

1
2
3
4
5
6
7
8
9
func TestMapShareMemory(t *testing.T) {
    m1 := map[string]int{}
    m2 := m1
    m1["a"] = 1
    t.Log(m1, len(m1))
    // map[a:1] 1
    t.Log(m2, len(m2))
    // map[a:1]
}

遍历顺序随机

map 在没有被修改的情况下，使用 range 多次遍历 map 时输出的 key 和 value 的顺序可能不同。这是 Go 语言的设计者们有意为之，在每次 range 时的顺序被随机化，旨在提示开发者们，Go 底层实现并不保证 map 遍历顺序稳定，请大家不要依赖 range 遍历结果顺序。

map 本身是无序的，且遍历时顺序还会被随机化，如果想顺序遍历 map，需要对 map key 先排序，再按照 key 的顺序遍历 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
func TestMapRange(t *testing.T) {
    m := map[int]string{1: "a", 2: "b", 3: "c"}
    t.Log("first range:")
    // 默认无序遍历
    for i, v := range m {
        t.Logf("m[%v]=%v ", i, v)
    }
    t.Log("\nsecond range:")
    for i, v := range m {
        t.Logf("m[%v]=%v ", i, v)
    }

    // 实现有序遍历
    var sl []int
    // 把 key 单独取出放到切片
    for k := range m {
        sl = append(sl, k)
    }
    // 排序切片
    sort.Ints(sl)
    // 以切片中的 key 顺序遍历 map 就是有序的了
    for _, k := range sl {
        t.Log(k, m[k])
    }
}

非线程安全

map默认是并发不安全的，原因如下：

Go 官方在经过了长时间的讨论后，认为 Go map 更应适配典型使用场景（不需要从多个 goroutine 中进行安全访问），而不是为了小部分情况（并发访问），导致大部分程序付出加锁代价（性能），决定了不支持。

场景: 2个协程同时读和写，以下程序会出现致命错误：fatal error: concurrent map writes

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
func main() {

    m := make(map[int]int)
    go func() {
                    //开一个协程写map
        for i := 0; i < 10000; i++ {

            m[i] = i
        }
    }()

    go func() {
                    //开一个协程读map
        for i := 0; i < 10000; i++ {

            fmt.Println(m[i])
        }
    }()

    //time.Sleep(time.Second * 20)
    for {

        ;
    }
}

如果想实现map线程安全，有两种方式：

方式一：使用读写锁 map + sync.RWMutex

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func BenchmarkMapConcurrencySafeByMutex(b *testing.B) {
    var lock sync.Mutex //互斥锁
    m := make(map[int]int, 0)
    var wg sync.WaitGroup
    for i := 0; i < b.N; i++ {
        wg.Add(1)
        go func(i int) {
            defer wg.Done()
            lock.Lock()
            defer lock.Unlock()
            m[i] = i
        }(i)
    }
    wg.Wait()
    b.Log(len(m), b.N)
}

方式二：使用golang提供的 sync.Map

sync.map是用读写分离实现的，其思想是空间换时间。和map+RWLock的实现方式相比，它做了一些优化：可以无锁访问read map，而且会优先操作read map，倘若只操作read map就可以满足要求(增删改查遍历)，那就不用去操作write map(它的读写都要加锁)，所以在某些特定场景中它发生锁竞争的频率会远远小于map+RWLock的实现方式。

1
2
3
4
5
6
7
8
9
10
11
12
13
func BenchmarkMapConcurrencySafeBySyncMap(b *testing.B) {
    var m sync.Map
    var wg sync.WaitGroup
    for i := 0; i < b.N; i++ {
        wg.Add(1)
        go func(i int) {
            defer wg.Done()
            m.Store(i, i)
        }(i)
    }
    wg.Wait()
    b.Log(b.N)
}

哈希冲突

golang中map是一个kv对集合。底层使用hash table，用链表来解决冲突 ，出现冲突时，不是每一个key都申请一个结构通过链表串起来，而是以bmap为最小粒度挂载，一个bmap可以放8个kv。在哈希函数的选择上，会在程序启动时，检测 cpu 是否支持 aes，如果支持，则使用 aes hash，否则使用 memhash。

获取数据

需要找到键和值的内存地址。

首先找到桶。它是通过将密钥散列的前 8 位与桶结构中的相应数据存储进行比较来选择的。

接下来通过其地址查找键值。

1
2
3
4
k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
if t.indirectkey() {
    k = *((*unsafe.Pointer)(k))
}

接下来以同样的方式找到值。

1
2
3
4
5
6
7
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
}

map创建

可以通过make函数创建并初始化map：

1
2
3
4
5
6
7
8
9
10
package main

import "fmt"

func main() {
    m1 := make(map[int]int) 
    m2 := make(map[int]int, 10) // 创建map支持传递一个参数，表示初始大小

    fmt.Println(m1, m2)
}

通过go的官方工具来查看汇编结果：

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
$ go tool compile -S main.go

"".main STEXT size=207 args=0x0 locals=0x70 funcid=0x0
    0x0000 00000 (main.go:5)    TEXT    "".main(SB), ABIInternal, $112-0
    0x0000 00000 (main.go:5)    MOVQ    (TLS), CX
    0x0009 00009 (main.go:5)    CMPQ    SP, 16(CX)
    0x000d 00013 (main.go:5)    PCDATA    $0, $-2
    0x000d 00013 (main.go:5)    JLS    197
    0x0013 00019 (main.go:5)    PCDATA    $0, $-1
    0x0013 00019 (main.go:5)    SUBQ    $112, SP
    0x0017 00023 (main.go:5)    MOVQ    BP, 104(SP)
    0x001c 00028 (main.go:5)    LEAQ    104(SP), BP
    0x0021 00033 (main.go:5)    FUNCDATA    $0, gclocals·69c1753bd5f81501d95132d08af04464(SB)
    0x0021 00033 (main.go:5)    FUNCDATA    $1, gclocals·d527b79a98f329c2ba624a68e7df03d6(SB)
    0x0021 00033 (main.go:5)    FUNCDATA    $2, "".main.stkobj(SB)
    0x0021 00033 (main.go:6)    PCDATA    $1, $0
    0x0021 00033 (main.go:6)    CALL    runtime.makemap_small(SB)
    0x0026 00038 (main.go:6)    MOVQ    (SP), AX
    0x002a 00042 (main.go:6)    MOVQ    AX, ""..autotmp_25+64(SP)
    0x002f 00047 (main.go:7)    LEAQ    type.map[int]int(SB), CX
    0x0036 00054 (main.go:7)    MOVQ    CX, (SP)
    0x003a 00058 (main.go:7)    MOVQ    $10, 8(SP)
    0x0043 00067 (main.go:7)    MOVQ    $0, 16(SP)
    0x004c 00076 (main.go:7)    PCDATA    $1, $1
    0x004c 00076 (main.go:7)    CALL    runtime.makemap(SB)
    0x0051 00081 (main.go:7)    MOVQ    24(SP), AX
    0x0056 00086 (main.go:9)    XORPS    X0, X0
    0x0059 00089 (main.go:9)    MOVUPS    X0, ""..autotmp_17+72(SP)
    0x005e 00094 (main.go:9)    MOVUPS    X0, ""..autotmp_17+88(SP)
    0x0063 00099 (main.go:9)    LEAQ    type.map[int]int(SB), CX
    0x006a 00106 (main.go:9)    MOVQ    CX, ""..autotmp_17+72(SP)
    0x006f 00111 (main.go:9)    MOVQ    ""..autotmp_25+64(SP), DX
    0x0074 00116 (main.go:9)    MOVQ    DX, ""..autotmp_17+80(SP)
    0x0079 00121 (main.go:9)    MOVQ    CX, ""..autotmp_17+88(SP)
    0x007e 00126 (main.go:9)    MOVQ    AX, ""..autotmp_17+96(SP)
    ... 省略不相关的部分

从汇编结果中，我们可以看出make对应的底层实现出现了两种不同的结果：runtime.makemap_small和runtime.makemap。让我们进一步翻阅相关的源码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 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 {
    h := new(hmap)
    h.hash0 = fastrand()
    return h
}

const (
    // Maximum number of key/elem pairs a bucket can hold.
    bucketCntBits = 3
    bucketCnt     = 1 << bucketCntBits
)

从以上源码中，我们可以得出一个结论：当编译期能够确定map的长度不大于bucketCnt（也就是8），将会对应到底层的runtime.makemap_small实现。makemap_small只是简单创建了hmap的结构体并没有初始化buckets。

其它情况最终都会调用runtime.makemap（笔者已在关键位置加上中文注释）：

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
// 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.

// 如果编译器发现map或者它第一个bucket能够被分配在栈上，则传入的h参数将不为空。
func makemap(t *maptype, hint int, h *hmap) *hmap {
    mem, overflow := math.MulUintptr(uintptr(hint), t.bucket.size)
    if overflow || mem > maxAlloc {
        hint = 0
    }

    // initialize Hmap
    if h == nil {
        h = new(hmap)
    }
    h.hash0 = fastrand()

    // Find the size parameter B which will hold the requested # of elements.
    // For hint < 0 overLoadFactor returns false since hint < bucketCnt.

    // hint表示创建map的预期初始大小，因此要计算一个合适的对数B
    // overLoadFactor即用于判断当前的2^B是否已经超过hint
    B := uint8(0)
    for overLoadFactor(hint, B) {
        B++
    }
    h.B = B

    // allocate initial hash table
    // if B == 0, the buckets field is allocated lazily later (in mapassign)
    // If hint is large zeroing this memory could take a while.

    // 如果B == 0，则Buckets数组将会延迟初始化，直到调用mapassign给该map存值
    if h.B != 0 {
        var nextOverflow *bmap
        h.buckets, nextOverflow = makeBucketArray(t, h.B, nil) // 给Buckets数组分配内存
        if nextOverflow != nil {
            h.extra = new(mapextra)
            h.extra.nextOverflow = nextOverflow
        }
    }

    return h
}

此外，从Go的源码中也发现另外一个runtime.makemap64函数，这是当传入的初始长度类型为int64时候会调用：

1
2
3
4
5
6
func makemap64(t *maptype, hint int64, h *hmap) *hmap {
    if int64(int(hint)) != hint {
        hint = 0
    }
    return makemap(t, int(hint), h)
}

小结一下，map的创建底层有三种实现：

  1. makemap_small：当map编译期确定初始长度不大于8，只创建hmap，不初始化buckets。
  2. makemap64：当make函数传递的长度参数类型是int64时候，调用该函数，底层仍然是复用makemap。
  3. makemap：初始化hash0加入随机性，计算对数B，并初始化buckets。

选择Hash函数

map底层使用的Hash函数在runtime层的初始化中会根据CPU架构和一些系统支持来选择。相关源码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func alginit() {
    // Install AES hash algorithms if the instructions needed are present.

    // 对于386/amd64/arm64都优先判断是否支持AES Hash函数
    if (GOARCH == "386" || GOARCH == "amd64") &&
        cpu.X86.HasAES && // AESENC
        cpu.X86.HasSSSE3 && // PSHUFB
        cpu.X86.HasSSE41 { // PINSR{D,Q}
        initAlgAES()
        return
    }
    if GOARCH == "arm64" && cpu.ARM64.HasAES {
        initAlgAES()
        return
    }
    getRandomData((*[len(hashkey) * sys.PtrSize]byte)(unsafe.Pointer(&hashkey))[:])
    hashkey[0] |= 1 // make sure these numbers are odd
    hashkey[1] |= 1
    hashkey[2] |= 1
    hashkey[3] |= 1
}

由上述源码可知，map的Hash函数优先选择AES，不支持的情况下进入默认逻辑。

map的访问

map的访问即通过给定的key在map中寻找其对应value，它的大致步骤如下：

  1. 以64位操作系统为例，原始的key通过Hash函数映射成64位二进制。
  2. 末尾B位对应bmap的位置，从[]bmap中找到对应的bmap。
  3. 首8位对应该key的tophash，从步骤2所定位的bmap开始检索。首先会比较bmap顶层的tophash与原始key的tophash是否相同，若不相同则直接跳过比较下一个；若相同则进一步比较key是否相同。
  4. 若当前的bmap中比较完，没有匹配到目标key，且overflow不为空，则继续从overflow指向的下一个bmap继续比较。

基本用法

map的访问方式直接通过key下标获取，返回值可以是一个value，也可以在此基础上多一个表示是否存在的bool：

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

import "fmt"

func main() {
    m := map[int8]int{
        1: 1,
        2: 2,
        3: 3,
    }

    v1 := m[1]
    v2, ok := m[2] // ok是一个bool值，用于判断是否存在2这个key

    fmt.Println(v1)
    fmt.Println(v2, ok)
}

让我们通过go的官方工具来查看汇编结果：

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
$ go tool compile -S main.go
"".main STEXT size=741 args=0x0 locals=0x120 funcid=0x0
    0x0000 00000 (main.go:5)    TEXT    "".main(SB), ABIInternal, $288-0
    0x0000 00000 (main.go:5)    MOVQ    (TLS), CX
    0x0009 00009 (main.go:5)    LEAQ    -160(SP), AX
    0x0011 00017 (main.go:5)    CMPQ    AX, 16(CX)
    0x0015 00021 (main.go:5)    PCDATA    $0, $-2
    0x0015 00021 (main.go:5)    JLS    726
    0x001b 00027 (main.go:5)    PCDATA    $0, $-1
    0x001b 00027 (main.go:5)    SUBQ    $288, SP
    0x0022 00034 (main.go:5)    MOVQ    BP, 280(SP)
    0x002a 00042 (main.go:5)    LEAQ    280(SP), BP
    0x0032 00050 (main.go:5)    FUNCDATA    $0, gclocals·69c1753bd5f81501d95132d08af04464(SB)
    0x0032 00050 (main.go:5)    FUNCDATA    $1, gclocals·164458436596f10dcbb268ec85fd5e10(SB)
    0x0032 00050 (main.go:5)    FUNCDATA    $2, "".main.stkobj(SB)
    0x0032 00050 (main.go:6)    XORPS    X0, X0
    0x0035 00053 (main.go:6)    MOVUPS    X0, ""..autotmp_20+232(SP)
    0x003d 00061 (main.go:6)    MOVUPS    X0, ""..autotmp_20+248(SP)
    0x0045 00069 (main.go:6)    MOVUPS    X0, ""..autotmp_20+264(SP)
    0x004d 00077 (main.go:6)    MOVQ    $0, ""..autotmp_21+96(SP)
    0x0056 00086 (main.go:6)    LEAQ    ""..autotmp_21+104(SP), DI
    0x005b 00091 (main.go:6)    PCDATA    $0, $-2
    0x005b 00091 (main.go:6)    LEAQ    -48(DI), DI
    0x005f 00095 (main.go:6)    NOP
    0x0060 00096 (main.go:6)    DUFFZERO    $277
    0x0073 00115 (main.go:6)    PCDATA    $0, $-1
    0x0073 00115 (main.go:6)    LEAQ    ""..autotmp_21+96(SP), AX
    0x0078 00120 (main.go:6)    MOVQ    AX, ""..autotmp_20+248(SP)
    0x0080 00128 (main.go:6)    PCDATA    $1, $1
    0x0080 00128 (main.go:6)    CALL    runtime.fastrand(SB)
    0x0085 00133 (main.go:6)    MOVL    (SP), AX
    0x0088 00136 (main.go:6)    MOVL    AX, ""..autotmp_20+244(SP)
    0x008f 00143 (main.go:7)    MOVB    $1, ""..autotmp_24+71(SP)
    0x0094 00148 (main.go:7)    LEAQ    type.map[int8]int(SB), AX
    0x009b 00155 (main.go:7)    MOVQ    AX, (SP)
    0x009f 00159 (main.go:7)    LEAQ    ""..autotmp_20+232(SP), CX
    0x00a7 00167 (main.go:7)    MOVQ    CX, 8(SP)
    0x00ac 00172 (main.go:7)    LEAQ    ""..autotmp_24+71(SP), DX
    0x00b1 00177 (main.go:7)    MOVQ    DX, 16(SP)
    0x00b6 00182 (main.go:7)    CALL    runtime.mapassign(SB)
    0x00bb 00187 (main.go:7)    MOVQ    24(SP), AX
    0x00c0 00192 (main.go:7)    MOVQ    $1, (AX)
    0x00c7 00199 (main.go:8)    MOVB    $2, ""..autotmp_24+71(SP)
    0x00cc 00204 (main.go:8)    LEAQ    type.map[int8]int(SB), AX
    0x00d3 00211 (main.go:8)    MOVQ    AX, (SP)
    0x00d7 00215 (main.go:8)    LEAQ    ""..autotmp_20+232(SP), CX
    0x00df 00223 (main.go:8)    MOVQ    CX, 8(SP)
    0x00e4 00228 (main.go:8)    LEAQ    ""..autotmp_24+71(SP), DX
    0x00e9 00233 (main.go:8)    MOVQ    DX, 16(SP)
    0x00ee 00238 (main.go:8)    CALL    runtime.mapassign(SB)
    0x00f3 00243 (main.go:8)    MOVQ    24(SP), AX
    0x00f8 00248 (main.go:8)    MOVQ    $2, (AX)
    0x00ff 00255 (main.go:9)    MOVB    $3, ""..autotmp_24+71(SP)
    0x0104 00260 (main.go:9)    LEAQ    type.map[int8]int(SB), AX
    0x010b 00267 (main.go:9)    MOVQ    AX, (SP)
    0x010f 00271 (main.go:9)    LEAQ    ""..autotmp_20+232(SP), CX
    0x0117 00279 (main.go:9)    MOVQ    CX, 8(SP)
    0x011c 00284 (main.go:9)    LEAQ    ""..autotmp_24+71(SP), DX
    0x0121 00289 (main.go:9)    MOVQ    DX, 16(SP)
    0x0126 00294 (main.go:9)    CALL    runtime.mapassign(SB)
    0x012b 00299 (main.go:9)    MOVQ    24(SP), AX
    0x0130 00304 (main.go:9)    MOVQ    $3, (AX)
    0x0137 00311 (main.go:12)    LEAQ    type.map[int8]int(SB), AX
    0x013e 00318 (main.go:12)    MOVQ    AX, (SP)
    0x0142 00322 (main.go:12)    LEAQ    ""..autotmp_20+232(SP), CX
    0x014a 00330 (main.go:12)    MOVQ    CX, 8(SP)
    0x014f 00335 (main.go:12)    LEAQ    ""..stmp_0(SB), DX
    0x0156 00342 (main.go:12)    MOVQ    DX, 16(SP)
    0x015b 00347 (main.go:12)    NOP
    0x0160 00352 (main.go:12)    CALL    runtime.mapaccess1(SB)
    0x0165 00357 (main.go:12)    MOVQ    24(SP), AX
    0x016a 00362 (main.go:12)    MOVQ    (AX), AX
    0x016d 00365 (main.go:12)    MOVQ    AX, "".v1+80(SP)
    0x0172 00370 (main.go:13)    LEAQ    type.map[int8]int(SB), CX
    0x0179 00377 (main.go:13)    MOVQ    CX, (SP)
    0x017d 00381 (main.go:13)    LEAQ    ""..autotmp_20+232(SP), CX
    0x0185 00389 (main.go:13)    MOVQ    CX, 8(SP)
    0x018a 00394 (main.go:13)    LEAQ    ""..stmp_1(SB), CX
    0x0191 00401 (main.go:13)    MOVQ    CX, 16(SP)
    0x0196 00406 (main.go:13)    PCDATA    $1, $0
    0x0196 00406 (main.go:13)    CALL    runtime.mapaccess2(SB)
    0x019b 00411 (main.go:13)    MOVQ    24(SP), AX
    0x01a0 00416 (main.go:13)    MOVQ    (AX), AX
    0x01a3 00419 (main.go:13)    MOVQ    AX, "".v2+72(SP)
    0x01a8 00424 (main.go:13)    MOVBLZX    32(SP), CX
    0x01ad 00429 (main.go:13)    MOVQ    CX, ""..autotmp_53+88(SP)
    0x01b2 00434 (main.go:15)    MOVQ    "".v1+80(SP), DX
    0x01b7 00439 (main.go:15)    MOVQ    DX, (SP)
    0x01bb 00443 (main.go:15)    NOP
    0x01c0 00448 (main.go:15)    CALL    runtime.convT64(SB)
    0x01c5 00453 (main.go:15)    MOVQ    8(SP), AX
    0x01ca 00458 (main.go:15)    XORPS    X1, X1
    0x01cd 00461 (main.go:15)    MOVUPS    X1, ""..autotmp_34+184(SP)
    0x01d5 00469 (main.go:15)    LEAQ    type.int(SB), CX
    0x01dc 00476 (main.go:15)    MOVQ    CX, ""..autotmp_34+184(SP)
    0x01e4 00484 (main.go:15)    MOVQ    AX, ""..autotmp_34+192(SP)
    ... 省略不相关的部分

从汇编的结果中，我们可以看出map的访问对应到底层主要是runtime.mapaccess1和runtime.mapaccess2两个方法：

1
2
func mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer
func mapaccess2(t *maptype, h *hmap, key unsafe.Pointer) (unsafe.Pointer, bool)

其中mapaccess2相比mapaccess1多出一个bool的返回值，表示该key是否存在，其它逻辑基本一致。接下来主要分析mapaccess1的实现：

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
// 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 := funcPC(mapaccess1)
        racereadpc(unsafe.Pointer(h), callerpc, pc)
        raceReadObjectPC(t.key, key, callerpc, pc)
    }
    if msanenabled && h != nil {
        msanread(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])
    }

    // map不允许并发读写，会触发该panic。这里是通过flags的标记位来判断是否正在进行写操作。
    if h.flags&hashWriting != 0 {
        throw("concurrent map read and map write")
    }
    hash := t.hasher(key, uintptr(h.hash0))
    m := bucketMask(h.B) // m即后B位，用于定位[]bmap中对应的bmap。
    b := (*bmap)(add(h.buckets, (hash&m)*uintptr(t.bucketsize))) // 定位到具体的bmap。
    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) // tophash即首8位，用于快速比较。
bucketloop:
    // 遍历迭代bmap和它的overflow bmap。
    for ; b != nil; b = b.overflow(t) {
        for i := uintptr(0); i < bucketCnt; i++ {
            // 首先比较tophash是否相同，不相同会直接continue。
            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))
            }

            // tophash相同的情况下，会比较key的值是否相同。若相同，则说明已经定位到该key，返回结果。
            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
            }
        }
    }
    return unsafe.Pointer(&zeroVal[0])
}

key是string/32位整型/64位整型

值得一提的是，当map对应的key类型是string、int32/uint32、int64/uint64其中之一的时候，在Go语言runtime中将会被汇编成不同的函数。下面列出函数签名：

1
2
3
4
5
6
7
8
func mapaccess1_fast32(t *maptype, h *hmap, key uint32) unsafe.Pointer
func mapaccess2_fast32(t *maptype, h *hmap, key uint32) (unsafe.Pointer, bool)

func mapaccess1_fast64(t *maptype, h *hmap, key uint64) unsafe.Pointer
func mapaccess2_fast64(t *maptype, h *hmap, key uint64) (unsafe.Pointer, bool)

func mapaccess1_faststr(t *maptype, h *hmap, ky string) unsafe.Pointer
func mapaccess2_faststr(t *maptype, h *hmap, ky string) (unsafe.Pointer, bool)

整体逻辑与mapaccess1和mapaccess2框架一致，Go语言针对这几种确定类型会有一定的逻辑优化。以int64为例（直接比较key）：

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
func mapaccess1_fast64(t *maptype, h *hmap, key uint64) unsafe.Pointer {
    if raceenabled && h != nil {
        callerpc := getcallerpc()
        racereadpc(unsafe.Pointer(h), callerpc, funcPC(mapaccess1_fast64))
    }
    if h == nil || h.count == 0 {
        return unsafe.Pointer(&zeroVal[0])
    }
    if h.flags&hashWriting != 0 {
        throw("concurrent map read and map write")
    }
    var b *bmap
    if h.B == 0 {
        // One-bucket table. No need to hash.
        b = (*bmap)(h.buckets)
    } else {
        hash := t.hasher(noescape(unsafe.Pointer(&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
            }
        }
    }
    for ; b != nil; b = b.overflow(t) {
        for i, k := uintptr(0), b.keys(); i < bucketCnt; i, k = i+1, add(k, 8) {
            if *(*uint64)(k) == key && !isEmpty(b.tophash[i]) { // 直接比较key，没有先比较tophash再比较key。
                return add(unsafe.Pointer(b), dataOffset+bucketCnt*8+i*uintptr(t.elemsize))
            }
        }
    }
    return unsafe.Pointer(&zeroVal[0])
}

map的赋值

不考虑扩容的情况下，map的赋值与map的访问基本逻辑是一致的。首先遵循map访问的方式通过后B位定位bmap，通过前8位快速比较tophash。当map中不存在这个key，会记录bmap中的第一个空闲的tophash，并插入该key。当map中存在这个key，会更新该key的value。

基本用法

1
2
3
4
5
6
7
8
9
10
11
package main

import "fmt"

func main() {
    m := make(map[int8]int)

    m[1] = 1

    fmt.Println(m)
}

让我们通过go的官方工具来查看汇编结果：

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
$ go tool compile -S main.go

"".main STEXT size=202 args=0x0 locals=0x60 funcid=0x0
    0x0000 00000 (main.go:5)    TEXT    "".main(SB), ABIInternal, $96-0
    0x0000 00000 (main.go:5)    MOVQ    (TLS), CX
    0x0009 00009 (main.go:5)    CMPQ    SP, 16(CX)
    0x000d 00013 (main.go:5)    PCDATA    $0, $-2
    0x000d 00013 (main.go:5)    JLS    192
    0x0013 00019 (main.go:5)    PCDATA    $0, $-1
    0x0013 00019 (main.go:5)    SUBQ    $96, SP
    0x0017 00023 (main.go:5)    MOVQ    BP, 88(SP)
    0x001c 00028 (main.go:5)    LEAQ    88(SP), BP
    0x0021 00033 (main.go:5)    FUNCDATA    $0, gclocals·69c1753bd5f81501d95132d08af04464(SB)
    0x0021 00033 (main.go:5)    FUNCDATA    $1, gclocals·713abd6cdf5e052e4dcd3eb297c82601(SB)
    0x0021 00033 (main.go:5)    FUNCDATA    $2, "".main.stkobj(SB)
    0x0021 00033 (main.go:6)    PCDATA    $1, $0
    0x0021 00033 (main.go:6)    CALL    runtime.makemap_small(SB)
    0x0026 00038 (main.go:6)    MOVQ    (SP), AX
    0x002a 00042 (main.go:6)    MOVQ    AX, ""..autotmp_20+64(SP)
    0x002f 00047 (main.go:8)    LEAQ    type.map[int8]int(SB), CX
    0x0036 00054 (main.go:8)    MOVQ    CX, (SP)
    0x003a 00058 (main.go:8)    MOVQ    AX, 8(SP)
    0x003f 00063 (main.go:8)    LEAQ    ""..stmp_0(SB), DX
    0x0046 00070 (main.go:8)    MOVQ    DX, 16(SP)
    0x004b 00075 (main.go:8)    PCDATA    $1, $1
    0x004b 00075 (main.go:8)    CALL    runtime.mapassign(SB)
    0x0050 00080 (main.go:8)    MOVQ    24(SP), AX
    0x0055 00085 (main.go:8)    MOVQ    $1, (AX)
    0x005c 00092 (main.go:10)    XORPS    X0, X0
    0x005f 00095 (main.go:10)    MOVUPS    X0, ""..autotmp_14+72(SP)
    0x0064 00100 (main.go:10)    LEAQ    type.map[int8]int(SB), AX
    0x006b 00107 (main.go:10)    MOVQ    AX, ""..autotmp_14+72(SP)
    0x0070 00112 (main.go:10)    MOVQ    ""..autotmp_20+64(SP), AX
    0x0075 00117 (main.go:10)    MOVQ    AX, ""..autotmp_14+80(SP)
    ... 省略不相关的部分

从汇编结果中，我们可以看出map的赋值对应的底层实现主要是runtime.mapassign：

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
// 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 {
    if h == nil {
        panic(plainError("assignment to entry in nil map"))
    }
    if raceenabled {
        callerpc := getcallerpc()
        pc := funcPC(mapassign)
        racewritepc(unsafe.Pointer(h), callerpc, pc)
        raceReadObjectPC(t.key, key, callerpc, pc)
    }
    if msanenabled {
        msanread(key, t.key.size)
    }
    // map不允许并发读写，通过flags的位判断。
    if h.flags&hashWriting != 0 {
        throw("concurrent map writes")
    }
    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.
    // 因为赋值是写操作，因此置位flags写标志。
    h.flags ^= hashWriting

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

again:
    bucket := hash & bucketMask(h.B)
    if h.growing() { // 判断是否处于扩容中。
        growWork(t, h, bucket)
    }
    b := (*bmap)(add(h.buckets, bucket*uintptr(t.bucketsize))) // 定位bmap
    top := tophash(hash) // 计算tophash

    var inserti *uint8
    var insertk unsafe.Pointer
    var elem unsafe.Pointer
bucketloop:
    for {
        for i := uintptr(0); i < bucketCnt; i++ {
            if b.tophash[i] != top {
                // 当遇到第一个空闲位置的tophash，记录下来。
                // 遍历完整个bmap及其overflow bmap，没有找到该key，则认为map中不存在该key。
                // 最终插入位置即这里记录的位置。
                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))
                }
                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) {
                continue
            }
            // already have a mapping for key. Update it.
            // 表明在map中已经存在这个key，那么就需要对该key的值进行更新操作。
            if t.needkeyupdate() {
                typedmemmove(t.key, k, key)
            }
            elem = add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize))
            goto done
        }
        ovf := b.overflow(t) // 继续遍历下一个overflow bmap
        if ovf == nil {
            break
        }
        b = ovf
    }

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

    // If we hit the max load factor or we have too many overflow buckets,
    // and we're not already in the middle of growing, start growing.

    // 触发扩容的情况。
    if !h.growing() && (overLoadFactor(h.count+1, h.B) || tooManyOverflowBuckets(h.noverflow, h.B)) {
        hashGrow(t, h)
        goto again // Growing the table invalidates everything, so try again
    }

    if inserti == nil {
        // The current bucket and all the overflow buckets connected to it are full, allocate a new one.
        newb := h.newoverflow(t, b)
        inserti = &newb.tophash[0]
        insertk = add(unsafe.Pointer(newb), dataOffset)
        elem = add(insertk, bucketCnt*uintptr(t.keysize))
    }

    // store new key/elem at insert position
    if t.indirectkey() {
        kmem := newobject(t.key)
        *(*unsafe.Pointer)(insertk) = kmem
        insertk = kmem
    }
    if t.indirectelem() {
        vmem := newobject(t.elem)
        *(*unsafe.Pointer)(elem) = vmem
    }
    typedmemmove(t.key, insertk, key)
    *inserti = top
    h.count++

done:
    if h.flags&hashWriting == 0 {
        throw("concurrent map writes")
    }
    h.flags &^= hashWriting // 将写操作标记位置空。
    if t.indirectelem() {
        elem = *((*unsafe.Pointer)(elem))
    }
    return elem
}

key是string/32位整型/64位整型

与map的访问同理，当map对应的key类型是string、int32/uint32、int64/uint64其中之一，Go语言的runtime层会调用不同函数，签名如下：

1
2
3
4
5
func mapassign_fast32(t *maptype, h *hmap, key uint32) unsafe.Pointer

func mapassign_fast64(t *maptype, h *hmap, key uint64) unsafe.Pointer

func mapassign_faststr(t *maptype, h *hmap, s string) unsafe.Pointer

map的扩容

概述

map扩容的目的在于减少Hash冲突，防止算法复杂度退化，保持Hash算法O(1)的时间复杂度。

map的扩容对使用方不可见，开发者在使用map的过程中是不会感知到map是否处于扩容中，以及当前扩容的进度。Go语言的map扩容是渐进式的，即整个扩容过程拆散在每一次的写操作里面，这样做的好处是保证每一次map的读写操作时间复杂度都是稳定的。

Golang 衡量装载率的指标是装载因子，它的计算方式是：

1
loadFactor := count / (2^B)

其中：

  • count 表示 Map 中的元素个数

  • 2^B 表示桶数量

所以装载因子 loadFactor 的含义是平均每个桶装载的元素个数。Golang 定义的装载因子阈值是 6.5。

插入 key 时map触发扩容的时机有两个：

  1. map的负载因子超过阈值，此时map被认为无法承担更多的key，需要进行2倍扩容。

  1. map存在局部bmap包含过多overflow的情况，此时map会认为局部的bmap可以进行tophash密集排列，需要进行等量扩容让overflow数量更少，判定标准：

    • B < 15 时，溢出桶数量 >= 2^B

    • B >= 15 时，溢出桶数量 >= 2^15

等量扩容和翻倍扩容

什么时候采用翻倍扩容策略？

触发扩容的第 1 种情况，随着 Map 中不断插入新元素，装载因子不断升高直至超过 6.5 ，这时候就需要翻倍扩容。

翻倍扩容后，分配的新桶数量是旧桶的 2 倍。

什么时候采用等量扩容策略？

触发扩容的第 2 种情况，是在装载因子较小的情况下， Map 的读写效率也较低。这种现象是 Map 元素少，但溢出桶数量很多， 这个时候需要等量扩容。

可能造成这种情况的原因是：不停地插入元素、删除元素：

  • 先插入很多元素，导致创建了很多桶，但装载因子未达到临界值，不触发扩容；

  • 之后，删除元素降低元素总数量；

  • 再插入很多元素，导致创建很多溢出桶。

等量扩容后，分配的新桶数量跟旧桶数量相同，但新桶中存储的数据更加紧密。

扩容相关的方法是 hashGrow()，但是需要注意，它只是分配了新桶，实际上并没有真正地“迁移数据”。

在扩容相关的 hashGrow() 方法中，最后一段注释中提到， Map 扩容后真正的数据迁移工作是由 growWork() 和 evacuate() 这两个方法渐进式地完成的，而触发数据迁移的时机是插入 Key 和 删除 Key。

对于翻倍扩容，需要重新计算 key 的哈希值，才能确定它到底落在哪个桶。例如，原来 B = 5，计算出 key 的哈希值后，只用看它的低 5 位，就能确定它落在哪个 桶。扩容后，B 变成了 6，因此需要多看一位，它的低 6 位决定了 key 落在哪个桶，这也被称为 rehash。

因此，某个 key 在迁移前后，所在桶的序号可能和原来相同，也可能在原来基础上加上 2^B（原来的 B 值），这取决于哈希值 第 6 bit 位是 0 还是 1。

扩容过程

首先，我们通过源码来查看如何判断负载因子是否超过阈值：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// 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)
}

// bucketShift returns 1<<b, optimized for code generation.
func bucketShift(b uint8) uintptr {
    // Masking the shift amount allows overflow checks to be elided.
    return uintptr(1) << (b & (sys.PtrSize*8 - 1))
}

const (
    // Maximum number of key/elem pairs a bucket can hold.
    bucketCntBits = 3
    bucketCnt     = 1 << bucketCntBits

    // Maximum average load of a bucket that triggers growth is 6.5.
    // Represent as loadFactorNum/loadFactorDen, to allow integer math.
    loadFactorNum = 13
    loadFactorDen = 2
)

从上述源码逻辑可以看出，loadFactorNum和loadFactorDen是预定义的负载因子阈值，所以负载因子阈值是6.5。而实际的负载因子由count和bucketShift(B)决定，也就是长度/桶个数。

接下来分析一下hashGrow：

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
func hashGrow(t *maptype, h *hmap) {
    // If we've hit the load factor, get bigger.
    // Otherwise, there are too many overflow buckets,
    // so keep the same number of buckets and "grow" laterally.
    bigger := uint8(1)
    if !overLoadFactor(h.count+1, h.B) { // 如果不是负载因子超过阈值，那么本次map的扩容实际上更应该理解为map的整理，容量不变。
        bigger = 0
        h.flags |= sameSizeGrow // 标记sameSizeGrow，表示容量不变。
    }
    oldbuckets := h.buckets // 保留旧的buckets。
    newbuckets, nextOverflow := makeBucketArray(t, h.B+bigger, nil) // 创建新的buckets。

    flags := h.flags &^ (iterator | oldIterator)
    if h.flags&iterator != 0 {
        flags |= oldIterator
    }
    // commit the grow (atomic wrt gc)
    h.B += bigger
    h.flags = flags
    h.oldbuckets = oldbuckets
    h.buckets = newbuckets
    h.nevacuate = 0 // 表示搬迁进度，从0开始将会依次递增，每调用一次evacuate()会自增一次。
    h.noverflow = 0

    if h.extra != nil && h.extra.overflow != nil {
        // Promote current overflow buckets to the old generation.
        if h.extra.oldoverflow != nil {
            throw("oldoverflow is not nil")
        }
        h.extra.oldoverflow = h.extra.overflow
        h.extra.overflow = nil
    }
    if nextOverflow != nil {
        if h.extra == nil {
            h.extra = new(mapextra)
        }
        h.extra.nextOverflow = nextOverflow
    }

    // the actual copying of the hash table data is done incrementally
    // by growWork() and evacuate().
}

由此可见，真正执行map扩容过程的逻辑在evacuate中：

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
// evacDst is an evacuation destination.
type evacDst struct {
    b *bmap          // current destination bucket // 搬迁目标bmap。
    i int            // key/elem index into b // 目标bmap的当前索引。
    k unsafe.Pointer // pointer to current key storage // 当前key。
    e unsafe.Pointer // pointer to current elem storage // 当前value。
}

func evacuate(t *maptype, h *hmap, oldbucket uintptr) {
    b := (*bmap)(add(h.oldbuckets, oldbucket*uintptr(t.bucketsize))) // 定位旧bmap。
    newbit := h.noldbuckets()
    if !evacuated(b) { // 判断是否已经被搬迁过。
        // TODO: reuse overflow buckets instead of using new ones, if there
        // is no iterator using the old buckets.  (If !oldIterator.)

        // xy contains the x and y (low and high) evacuation destinations.
        var xy [2]evacDst
        x := &xy[0]
        x.b = (*bmap)(add(h.buckets, oldbucket*uintptr(t.bucketsize)))
        x.k = add(unsafe.Pointer(x.b), dataOffset)
        x.e = add(x.k, bucketCnt*uintptr(t.keysize))

        if !h.sameSizeGrow() { // 对于2倍扩容的场景，搬迁目标可能有2个，因此xy[1]记录另一个目标。
            // Only calculate y pointers if we're growing bigger.
            // Otherwise GC can see bad pointers.
            y := &xy[1]
            y.b = (*bmap)(add(h.buckets, (oldbucket+newbit)*uintptr(t.bucketsize)))
            y.k = add(unsafe.Pointer(y.b), dataOffset)
            y.e = add(y.k, bucketCnt*uintptr(t.keysize))
        }

        for ; b != nil; b = b.overflow(t) { // 遍历当前的bmap。
            k := add(unsafe.Pointer(b), dataOffset)
            e := add(k, bucketCnt*uintptr(t.keysize))
            for i := 0; i < bucketCnt; i, k, e = i+1, add(k, uintptr(t.keysize)), add(e, uintptr(t.elemsize)) {
                top := b.tophash[i]
                if isEmpty(top) {
                    b.tophash[i] = evacuatedEmpty
                    continue
                }
                if top < minTopHash {
                    throw("bad map state")
                }
                k2 := k
                if t.indirectkey() {
                    k2 = *((*unsafe.Pointer)(k2))
                }
                var useY uint8
                if !h.sameSizeGrow() { // 对于2倍扩容的场景，要重新计算tophash
                    // Compute hash to make our evacuation decision (whether we need
                    // to send this key/elem to bucket x or bucket y).
                    hash := t.hasher(k2, uintptr(h.hash0))
                    if h.flags&iterator != 0 && !t.reflexivekey() && !t.key.equal(k2, k2) {
                        // If key != key (NaNs), then the hash could be (and probably
                        // will be) entirely different from the old hash. Moreover,
                        // it isn't reproducible. Reproducibility is required in the
                        // presence of iterators, as our evacuation decision must
                        // match whatever decision the iterator made.
                        // Fortunately, we have the freedom to send these keys either
                        // way. Also, tophash is meaningless for these kinds of keys.
                        // We let the low bit of tophash drive the evacuation decision.
                        // We recompute a new random tophash for the next level so
                        // these keys will get evenly distributed across all buckets
                        // after multiple grows.
                        useY = top & 1
                        top = tophash(hash)
                    } else {
                        if hash&newbit != 0 {
                            useY = 1
                        }
                    }
                }

                if evacuatedX+1 != evacuatedY || evacuatedX^1 != evacuatedY {
                    throw("bad evacuatedN")
                }

                b.tophash[i] = evacuatedX + useY // evacuatedX + 1 == evacuatedY
                dst := &xy[useY]                 // evacuation destination

                if dst.i == bucketCnt {
                    dst.b = h.newoverflow(t, dst.b)
                    dst.i = 0
                    dst.k = add(unsafe.Pointer(dst.b), dataOffset)
                    dst.e = add(dst.k, bucketCnt*uintptr(t.keysize))
                }
                dst.b.tophash[dst.i&(bucketCnt-1)] = top // mask dst.i as an optimization, to avoid a bounds check

                // 拷贝内存数据到新的搬迁位置
                if t.indirectkey() {
                    *(*unsafe.Pointer)(dst.k) = k2 // copy pointer
                } else {
                    typedmemmove(t.key, dst.k, k) // copy elem
                }
                if t.indirectelem() {
                    *(*unsafe.Pointer)(dst.e) = *(*unsafe.Pointer)(e)
                } else {
                    typedmemmove(t.elem, dst.e, e)
                }
                dst.i++
                // These updates might push these pointers past the end of the
                // key or elem arrays.  That's ok, as we have the overflow pointer
                // at the end of the bucket to protect against pointing past the
                // end of the bucket.
                dst.k = add(dst.k, uintptr(t.keysize))
                dst.e = add(dst.e, uintptr(t.elemsize))
            }
        }
        // Unlink the overflow buckets & clear key/elem to help GC.
        // 把旧的bmap引用解除，便于GC完成内存回收。
        if h.flags&oldIterator == 0 && t.bucket.ptrdata != 0 {
            b := add(h.oldbuckets, oldbucket*uintptr(t.bucketsize))
            // Preserve b.tophash because the evacuation
            // state is maintained there.
            ptr := add(b, dataOffset)
            n := uintptr(t.bucketsize) - dataOffset
            memclrHasPointers(ptr, n)
        }
    }

    if oldbucket == h.nevacuate {
        advanceEvacuationMark(h, t, newbit)
    }
}

map的删除

概述

map的删除与map的访问基本逻辑也是一致的。遍历bmap与overflow寻找目标key，如果找到则清空tophash并删除key/value释放内存。

基本用法

删除map中的元素可以通过builtin中的delete函数完成：

1
2
3
4
5
6
7
package main

func main() {
    m := make(map[int8]int)

    delete(m, 1)
}

让我们通过go的官方工具来查看汇编结果：

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
$ go tool compile -S main.go
"".main STEXT size=204 args=0x0 locals=0xa8 funcid=0x0
    0x0000 00000 (main.go:3)    TEXT    "".main(SB), ABIInternal, $168-0
    0x0000 00000 (main.go:3)    MOVQ    (TLS), CX
    0x0009 00009 (main.go:3)    LEAQ    -40(SP), AX
    0x000e 00014 (main.go:3)    CMPQ    AX, 16(CX)
    0x0012 00018 (main.go:3)    PCDATA    $0, $-2
    0x0012 00018 (main.go:3)    JLS    194
    0x0018 00024 (main.go:3)    PCDATA    $0, $-1
    0x0018 00024 (main.go:3)    SUBQ    $168, SP
    0x001f 00031 (main.go:3)    MOVQ    BP, 160(SP)
    0x0027 00039 (main.go:3)    LEAQ    160(SP), BP
    0x002f 00047 (main.go:3)    FUNCDATA    $0, gclocals·69c1753bd5f81501d95132d08af04464(SB)
    0x002f 00047 (main.go:3)    FUNCDATA    $1, gclocals·d9a525d1de6bc16975a5efbb873db17d(SB)
    0x002f 00047 (main.go:3)    FUNCDATA    $2, "".main.stkobj(SB)
    0x002f 00047 (main.go:4)    XORPS    X0, X0
    0x0032 00050 (main.go:4)    MOVUPS    X0, ""..autotmp_1+112(SP)
    0x0037 00055 (main.go:4)    MOVUPS    X0, ""..autotmp_1+128(SP)
    0x003f 00063 (main.go:4)    MOVUPS    X0, ""..autotmp_1+144(SP)
    0x0047 00071 (main.go:4)    MOVQ    $0, ""..autotmp_2+24(SP)
    0x0050 00080 (main.go:4)    LEAQ    ""..autotmp_2+32(SP), DI
    0x0055 00085 (main.go:4)    PCDATA    $0, $-2
    0x0055 00085 (main.go:4)    LEAQ    -48(DI), DI
    0x0059 00089 (main.go:4)    NOP
    0x0060 00096 (main.go:4)    DUFFZERO    $277
    0x0073 00115 (main.go:4)    PCDATA    $0, $-1
    0x0073 00115 (main.go:4)    LEAQ    ""..autotmp_2+24(SP), AX
    0x0078 00120 (main.go:4)    MOVQ    AX, ""..autotmp_1+128(SP)
    0x0080 00128 (main.go:4)    PCDATA    $1, $1
    0x0080 00128 (main.go:4)    CALL    runtime.fastrand(SB)
    0x0085 00133 (main.go:4)    MOVL    (SP), AX
    0x0088 00136 (main.go:4)    MOVL    AX, ""..autotmp_1+124(SP)
    0x008c 00140 (main.go:6)    LEAQ    type.map[int8]int(SB), AX
    0x0093 00147 (main.go:6)    MOVQ    AX, (SP)
    0x0097 00151 (main.go:6)    LEAQ    ""..autotmp_1+112(SP), AX
    0x009c 00156 (main.go:6)    MOVQ    AX, 8(SP)
    0x00a1 00161 (main.go:6)    LEAQ    ""..stmp_0(SB), AX
    0x00a8 00168 (main.go:6)    MOVQ    AX, 16(SP)
    0x00ad 00173 (main.go:6)    PCDATA    $1, $0
    0x00ad 00173 (main.go:6)    CALL    runtime.mapdelete(SB)
    0x00b2 00178 (main.go:7)    MOVQ    160(SP), BP
    0x00ba 00186 (main.go:7)    ADDQ    $168, SP
    0x00c1 00193 (main.go:7)    RET
    0x00c2 00194 (main.go:7)    NOP
    0x00c2 00194 (main.go:3)    PCDATA    $1, $-1
    0x00c2 00194 (main.go:3)    PCDATA    $0, $-2
    0x00c2 00194 (main.go:3)    CALL    runtime.morestack_noctxt(SB)
    0x00c7 00199 (main.go:3)    PCDATA    $0, $-1
    0x00c7 00199 (main.go:3)    JMP    0
    ... 省略不相关的部分

从编译结果中，我们可以看出map的删除底层实现是runtime.mapdelete：

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
func mapdelete(t *maptype, h *hmap, key unsafe.Pointer) {
    if raceenabled && h != nil {
        callerpc := getcallerpc()
        pc := funcPC(mapdelete)
        racewritepc(unsafe.Pointer(h), callerpc, pc)
        raceReadObjectPC(t.key, key, callerpc, pc)
    }
    if msanenabled && h != nil {
        msanread(key, t.key.size)
    }
    if h == nil || h.count == 0 {
        if t.hashMightPanic() {
            t.hasher(key, 0) // see issue 23734
        }
        return
    }
    if h.flags&hashWriting != 0 {
        throw("concurrent map writes")
    }

    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 (delete).
    h.flags ^= hashWriting

    bucket := hash & bucketMask(h.B)
    if h.growing() {
        growWork(t, h, bucket)
    }
    b := (*bmap)(add(h.buckets, bucket*uintptr(t.bucketsize)))
    bOrig := b
    top := tophash(hash)
search:
    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 search
                }
                continue
            }
            k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
            k2 := k
            if t.indirectkey() {
                k2 = *((*unsafe.Pointer)(k2))
            }
            if !t.key.equal(key, k2) {
                continue
            }
            // 删除key
            // Only clear key if there are pointers in it.
            if t.indirectkey() {
                *(*unsafe.Pointer)(k) = nil
            } else if t.key.ptrdata != 0 {
                memclrHasPointers(k, t.key.size)
            }

            // 删除value
            e := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize))
            if t.indirectelem() {
                *(*unsafe.Pointer)(e) = nil
            } else if t.elem.ptrdata != 0 {
                memclrHasPointers(e, t.elem.size)
            } else {
                memclrNoHeapPointers(e, t.elem.size)
            }

            // 清空tophash
            b.tophash[i] = emptyOne
            // If the bucket now ends in a bunch of emptyOne states,
            // change those to emptyRest states.
            // It would be nice to make this a separate function, but
            // for loops are not currently inlineable.
            if i == bucketCnt-1 {
                if b.overflow(t) != nil && b.overflow(t).tophash[0] != emptyRest {
                    goto notLast
                }
            } else {
                if b.tophash[i+1] != emptyRest {
                    goto notLast
                }
            }
            for {
                b.tophash[i] = emptyRest
                if i == 0 {
                    if b == bOrig {
                        break // beginning of initial bucket, we're done.
                    }
                    // Find previous bucket, continue at its last entry.
                    c := b
                    for b = bOrig; b.overflow(t) != c; b = b.overflow(t) {
                    }
                    i = bucketCnt - 1
                } else {
                    i--
                }
                if b.tophash[i] != emptyOne {
                    break
                }
            }
        notLast:
            h.count--
            // Reset the hash seed to make it more difficult for attackers to
            // repeatedly trigger hash collisions. See issue 25237.
            if h.count == 0 {
                h.hash0 = fastrand()
            }
            break search
        }
    }

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

key是string/32位整型/64位整型

与map的访问同理，当map对应的key类型是string、int32/uint32、int64/uint64其中之一，Go语言的runtime层会调用不同函数，签名如下：

1
2
3
func mapdelete_fast32(t *maptype, h *hmap, key uint32)
func mapdelete_fast64(t *maptype, h *hmap, key uint64)
func mapdelete_faststr(t *maptype, h *hmap, ky string)

map的迭代

概述

由于map存在渐进式扩容，因此map的迭代并不像想象中的那么直接，而需要考虑搬迁过程中的迭代。在上文的描述中，我们知道，map在搬迁过程中会通过nevacuate来记录搬迁进度，因此在迭代过程中需要同时考虑遍历旧的bmap和新的bmap。

基本用法

map的迭代通过Go语言的基本语法for range完成：

1
2
3
4
5
6
7
8
9
10
11
package main

import "fmt"

func main() {
    m := make(map[int8]int)

    for k, v := range m {
        fmt.Println(k, v)
    }
}

让我们通过go的官方工具来查看汇编结果：

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
$ go tool compile -S main.go

"".main STEXT size=466 args=0x0 locals=0x158 funcid=0x0
    0x0000 00000 (main.go:5)    TEXT    "".main(SB), ABIInternal, $344-0
    0x0000 00000 (main.go:5)    MOVQ    (TLS), CX
    0x0009 00009 (main.go:5)    LEAQ    -216(SP), AX
    0x0011 00017 (main.go:5)    CMPQ    AX, 16(CX)
    0x0015 00021 (main.go:5)    PCDATA    $0, $-2
    0x0015 00021 (main.go:5)    JLS    456
    0x001b 00027 (main.go:5)    PCDATA    $0, $-1
    0x001b 00027 (main.go:5)    SUBQ    $344, SP
    0x0022 00034 (main.go:5)    MOVQ    BP, 336(SP)
    0x002a 00042 (main.go:5)    LEAQ    336(SP), BP
    0x0032 00050 (main.go:5)    FUNCDATA    $0, gclocals·7d2d5fca80364273fb07d5820a76fef4(SB)
    0x0032 00050 (main.go:5)    FUNCDATA    $1, gclocals·78b4c479b253ac6bc6556563a2e18726(SB)
    0x0032 00050 (main.go:5)    FUNCDATA    $2, "".main.stkobj(SB)
    0x0032 00050 (main.go:6)    XORPS    X0, X0
    0x0035 00053 (main.go:6)    MOVUPS    X0, ""..autotmp_15+192(SP)
    0x003d 00061 (main.go:6)    MOVUPS    X0, ""..autotmp_15+208(SP)
    0x0045 00069 (main.go:6)    MOVUPS    X0, ""..autotmp_15+224(SP)
    0x004d 00077 (main.go:6)    MOVQ    $0, ""..autotmp_16+72(SP)
    0x0056 00086 (main.go:6)    LEAQ    ""..autotmp_16+80(SP), DI
    0x005b 00091 (main.go:6)    PCDATA    $0, $-2
    0x005b 00091 (main.go:6)    LEAQ    -48(DI), DI
    0x005f 00095 (main.go:6)    NOP
    0x0060 00096 (main.go:6)    DUFFZERO    $277
    0x0073 00115 (main.go:6)    PCDATA    $0, $-1
    0x0073 00115 (main.go:6)    LEAQ    ""..autotmp_16+72(SP), AX
    0x0078 00120 (main.go:6)    MOVQ    AX, ""..autotmp_15+208(SP)
    0x0080 00128 (main.go:6)    PCDATA    $1, $1
    0x0080 00128 (main.go:6)    CALL    runtime.fastrand(SB)
    0x0085 00133 (main.go:6)    MOVL    (SP), AX
    0x0088 00136 (main.go:6)    MOVL    AX, ""..autotmp_15+204(SP)
    0x008f 00143 (main.go:8)    LEAQ    ""..autotmp_11+240(SP), DI
    0x0097 00151 (main.go:8)    XORPS    X0, X0
    0x009a 00154 (main.go:8)    PCDATA    $0, $-2
    0x009a 00154 (main.go:8)    LEAQ    -32(DI), DI
    0x009e 00158 (main.go:8)    NOP
    0x00a0 00160 (main.go:8)    DUFFZERO    $273
    0x00b3 00179 (main.go:8)    PCDATA    $0, $-1
    0x00b3 00179 (main.go:8)    LEAQ    type.map[int8]int(SB), AX
    0x00ba 00186 (main.go:8)    MOVQ    AX, (SP)
    0x00be 00190 (main.go:8)    LEAQ    ""..autotmp_15+192(SP), AX
    0x00c6 00198 (main.go:8)    MOVQ    AX, 8(SP)
    0x00cb 00203 (main.go:8)    LEAQ    ""..autotmp_11+240(SP), AX
    0x00d3 00211 (main.go:8)    MOVQ    AX, 16(SP)
    0x00d8 00216 (main.go:8)    PCDATA    $1, $2
    0x00d8 00216 (main.go:8)    CALL    runtime.mapiterinit(SB)
    0x00dd 00221 (main.go:8)    NOP
    0x00e0 00224 (main.go:8)    JMP    423
    0x00e5 00229 (main.go:8)    MOVQ    ""..autotmp_11+248(SP), CX
    0x00ed 00237 (main.go:8)    MOVQ    (CX), CX
    0x00f0 00240 (main.go:8)    MOVBLZX    (AX), AX
    0x00f3 00243 (main.go:8)    MOVQ    AX, ""..autotmp_32+64(SP)
    0x00f8 00248 (main.go:9)    MOVQ    CX, (SP)
    0x00fc 00252 (main.go:9)    NOP
    0x0100 00256 (main.go:9)    CALL    runtime.convT64(SB)
    0x0105 00261 (main.go:9)    MOVQ    8(SP), AX
    0x010a 00266 (main.go:9)    XORPS    X0, X0
    0x010d 00269 (main.go:9)    MOVUPS    X0, ""..autotmp_24+160(SP)
    0x0115 00277 (main.go:9)    MOVUPS    X0, ""..autotmp_24+176(SP)
    0x011d 00285 (main.go:9)    LEAQ    type.int8(SB), CX
    0x0124 00292 (main.go:9)    MOVQ    CX, ""..autotmp_24+160(SP)
    0x012c 00300 (main.go:9)    MOVQ    ""..autotmp_32+64(SP), DX
    0x0131 00305 (main.go:9)    LEAQ    runtime.staticuint64s(SB), BX
    0x0138 00312 (main.go:9)    LEAQ    (BX)(DX*8), DX
    0x013c 00316 (main.go:9)    MOVQ    DX, ""..autotmp_24+168(SP)
    0x0144 00324 (main.go:9)    LEAQ    type.int(SB), DX
    0x014b 00331 (main.go:9)    MOVQ    DX, ""..autotmp_24+176(SP)
    0x0153 00339 (main.go:9)    MOVQ    AX, ""..autotmp_24+184(SP)
    0x015b 00347 (<unknown line number>)    NOP
    0x015b 00347 ($GOROOT/src/fmt/print.go:274)    MOVQ    os.Stdout(SB), AX
    0x0162 00354 ($GOROOT/src/fmt/print.go:274)    LEAQ    go.itab.*os.File,io.Writer(SB), SI
    0x0169 00361 ($GOROOT/src/fmt/print.go:274)    MOVQ    SI, (SP)
    0x016d 00365 ($GOROOT/src/fmt/print.go:274)    MOVQ    AX, 8(SP)
    0x0172 00370 ($GOROOT/src/fmt/print.go:274)    LEAQ    ""..autotmp_24+160(SP), AX
    0x017a 00378 ($GOROOT/src/fmt/print.go:274)    MOVQ    AX, 16(SP)
    0x017f 00383 ($GOROOT/src/fmt/print.go:274)    MOVQ    $2, 24(SP)
    0x0188 00392 ($GOROOT/src/fmt/print.go:274)    MOVQ    $2, 32(SP)
    0x0191 00401 ($GOROOT/src/fmt/print.go:274)    CALL    fmt.Fprintln(SB)
    0x0196 00406 (main.go:8)    LEAQ    ""..autotmp_11+240(SP), AX
    0x019e 00414 (main.go:8)    MOVQ    AX, (SP)
    0x01a2 00418 (main.go:8)    CALL    runtime.mapiternext(SB)
    0x01a7 00423 (main.go:8)    MOVQ    ""..autotmp_11+240(SP), AX
    0x01af 00431 (main.go:8)    TESTQ    AX, AX
    0x01b2 00434 (main.go:8)    JNE    229
    0x01b8 00440 (main.go:8)    PCDATA    $1, $-1
    0x01b8 00440 (main.go:8)    MOVQ    336(SP), BP
    0x01c0 00448 (main.go:8)    ADDQ    $344, SP
    0x01c7 00455 (main.go:8)    RET
    0x01c8 00456 (main.go:8)    NOP
    0x01c8 00456 (main.go:5)    PCDATA    $1, $-1
    0x01c8 00456 (main.go:5)    PCDATA    $0, $-2
    0x01c8 00456 (main.go:5)    CALL    runtime.morestack_noctxt(SB)
    0x01cd 00461 (main.go:5)    PCDATA    $0, $-1
    0x01cd 00461 (main.go:5)    JMP    0
    ... 省略不相关的部分

从编译结果中，我们可以看出map的迭代底层对应的是runtime.mapiterinit和runtime.mapiternext：

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
// mapiterinit initializes the hiter struct used for ranging over maps.
// The hiter struct pointed to by 'it' is allocated on the stack
// by the compilers order pass or on the heap by reflect_mapiterinit.
// Both need to have zeroed hiter since the struct contains pointers.
func mapiterinit(t *maptype, h *hmap, it *hiter) {
    if raceenabled && h != nil {
        callerpc := getcallerpc()
        racereadpc(unsafe.Pointer(h), callerpc, funcPC(mapiterinit))
    }

    if h == nil || h.count == 0 {
        return
    }

    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
    // 可以看出，map的迭代器会随机选择一个开始的bucket位置和开始的offset。
    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)
}
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
func mapiternext(it *hiter) {
    h := it.h
    if raceenabled {
        callerpc := getcallerpc()
        racereadpc(unsafe.Pointer(h), callerpc, funcPC(mapiternext))
    }
    if h.flags&hashWriting != 0 {
        throw("concurrent map iteration and map write")
    }
    t := it.t
    bucket := it.bucket
    b := it.bptr
    i := it.i
    checkBucket := it.checkBucket

next:
    if b == nil {
        if bucket == it.startBucket && it.wrapped {
            // end of iteration
            it.key = nil
            it.elem = nil
            return
        }
        // 判断是否正处于扩容搬迁中，对于正在搬迁过程中仍未完成搬迁的bucket，迭代过程中需要考虑进入旧的bucket里面。
        if h.growing() && it.B == h.B {
            // Iterator was started in the middle of a grow, and the grow isn't done yet.
            // If the bucket we're looking at hasn't been filled in yet (i.e. the old
            // bucket hasn't been evacuated) then we need to iterate through the old
            // bucket and only return the ones that will be migrated to this bucket.
            oldbucket := bucket & it.h.oldbucketmask()
            b = (*bmap)(add(h.oldbuckets, oldbucket*uintptr(t.bucketsize)))
            if !evacuated(b) {
                checkBucket = bucket
            } else {
                b = (*bmap)(add(it.buckets, bucket*uintptr(t.bucketsize)))
                checkBucket = noCheck
            }
        } else {
            b = (*bmap)(add(it.buckets, bucket*uintptr(t.bucketsize)))
            checkBucket = noCheck
        }
        bucket++
        if bucket == bucketShift(it.B) {
            bucket = 0
            it.wrapped = true
        }
        i = 0
    }
    for ; i < bucketCnt; i++ {
        offi := (i + it.offset) & (bucketCnt - 1)
        if isEmpty(b.tophash[offi]) || b.tophash[offi] == evacuatedEmpty {
            // TODO: emptyRest is hard to use here, as we start iterating
            // in the middle of a bucket. It's feasible, just tricky.
            continue
        }
        k := add(unsafe.Pointer(b), dataOffset+uintptr(offi)*uintptr(t.keysize))
        if t.indirectkey() {
            k = *((*unsafe.Pointer)(k))
        }
        e := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+uintptr(offi)*uintptr(t.elemsize))
        if checkBucket != noCheck && !h.sameSizeGrow() {
            // Special case: iterator was started during a grow to a larger size
            // and the grow is not done yet. We're working on a bucket whose
            // oldbucket has not been evacuated yet. Or at least, it wasn't
            // evacuated when we started the bucket. So we're iterating
            // through the oldbucket, skipping any keys that will go
            // to the other new bucket (each oldbucket expands to two
            // buckets during a grow).
            if t.reflexivekey() || t.key.equal(k, k) {
                // If the item in the oldbucket is not destined for
                // the current new bucket in the iteration, skip it.
                hash := t.hasher(k, uintptr(h.hash0))
                if hash&bucketMask(it.B) != checkBucket {
                    continue
                }
            } else {
                // Hash isn't repeatable if k != k (NaNs).  We need a
                // repeatable and randomish choice of which direction
                // to send NaNs during evacuation. We'll use the low
                // bit of tophash to decide which way NaNs go.
                // NOTE: this case is why we need two evacuate tophash
                // values, evacuatedX and evacuatedY, that differ in
                // their low bit.
                if checkBucket>>(it.B-1) != uintptr(b.tophash[offi]&1) {
                    continue
                }
            }
        }
        if (b.tophash[offi] != evacuatedX && b.tophash[offi] != evacuatedY) ||
            !(t.reflexivekey() || t.key.equal(k, k)) {
            // This is the golden data, we can return it.
            // OR
            // key!=key, so the entry can't be deleted or updated, so we can just return it.
            // That's lucky for us because when key!=key we can't look it up successfully.
            it.key = k
            if t.indirectelem() {
                e = *((*unsafe.Pointer)(e))
            }
            it.elem = e
        } else {
            // The hash table has grown since the iterator was started.
            // The golden data for this key is now somewhere else.
            // Check the current hash table for the data.
            // This code handles the case where the key
            // has been deleted, updated, or deleted and reinserted.
            // NOTE: we need to regrab the key as it has potentially been
            // updated to an equal() but not identical key (e.g. +0.0 vs -0.0).
            rk, re := mapaccessK(t, h, k)
            if rk == nil {
                continue // key has been deleted
            }
            it.key = rk
            it.elem = re
        }
        it.bucket = bucket
        if it.bptr != b { // avoid unnecessary write barrier; see issue 14921
            it.bptr = b
        }
        it.i = i + 1
        it.checkBucket = checkBucket
        return
    }
    b = b.overflow(t)
    i = 0
    goto next
}

小结一下，map的迭代顺序是完全随机的，并且map在迭代过程中会根据搬迁进度来判断是否要兼顾旧的bucket。

是否能在迭代过程中删除元素

这是一个比较热门的话题，即map中是否可以在迭代过程中删除元素。在不同语言中的行为结果可能是不一样的，熟悉C++的读者应该知道这样的行为在C++语言中是不合法的，本文讨论的是Go语言的行为：

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

func main() {
    m := map[int]int{
        1: 1,
        2: 2,
        3: 3,
    }

    for k := range m {
        if k == 1 {
            delete(m, k)
        }
    }

    fmt.Println(m)
}

在Go语言中，上述操作是允许且可以正确运行的。从上述map的删除分析中，我们可以看出，map的删除是找到对应的bmap删除key/value并且清空tophash，但是并不会导致下标产生偏移，因此该操作可以正常执行并得到预期的结果。

Time & Space complexity

时间复杂度

go map是hash实现，hash实现的基本就是O(1)的时间复杂度：

  • 正常情况，且不考虑扩容状态，复杂度O(1)：通过hash值定位桶是O(1)，一个桶最多8个元素，合理的hash算法应该能把元素相对均匀散列，所以溢出链表（如果有）也不会太长，所以虽然在桶和溢出链表上定位key是遍历，考虑到数量小也可以认为是O(1)
  • 正常情况，处于扩容状态时，复杂度也是O(1)：相比于上一种状态，扩容会增加搬迁最多2个桶和溢出链表的时间消耗，当溢出链表不太长时，复杂度也可以认为是O(1)
  • 极端情况，散列极不均匀，大部分数据被集中在一条散列链表上，复杂度退化为O(n)。

go采用的hash算法应是很成熟的算法，极端情况暂不考虑。所以综合情况下go map的时间复杂度应为O(1)

Hash散列之所以成为map底层实现的首选，核心原因就是：**平均增删改查时间复杂度都是O(1)**。相比之下，基于平衡树的map（例如：C++ STL的map）平均时间复杂度是O(logN)。

Algorithm Action Average Time Complexity Worst Time Complexity
Hash Insert O(1) O(N)
Hash Delete O(1) O(N)
Hash Update O(1) O(N)
Hash Get O(1) O(N)
Balanced Binary Tree Insert O(logN) O(logN)
Balanced Binary Tree Delete O(logN) O(logN)
Balanced Binary Tree Update O(logN) O(logN)
Balanced Binary Tree Get O(logN) O(logN)

需要注意的是，基于平衡树的map在最坏情况下依然能够保证时间复杂度是O(logN)，并且能够提供key的有序遍历，这是基于Hash的map所不具备的能力。

空间复杂度

首先我们不考虑因删除大量元素导致的空间浪费情况（这种情况现在go是留给程序员自己解决），只考虑一个持续增长状态的map的一个空间使用率： 由于溢出桶数量超过hash桶数量时会触发缩容，所以最坏的情况是数据被集中在一条链上，hash表基本是空的，这时空间浪费O(n)。

最好的情况下，数据均匀散列在hash表上，没有元素溢出，这时最好的空间复杂度就是扩散因子决定了，当前go的扩散因子由全局变量决定，即loadFactorNum/loadFactorDen = 6.5。即平均每个hash桶被分配到6.5个元素以上时，开始扩容。所以最小的空间浪费是(8-6.5)/8 = 0.1875，即O(0.1875n)

结论：go map的空间复杂度（指除去正常存储元素所需空间之外的空间浪费）是O(0.1875n) ~ O(n)之间。

Golang Map 实现中的一些优化

  1. 哈希算法选用高效的 memhash 算法 和 CPU AES指令集。AES 指令集充分利用 CPU 硬件特性，计算哈希值的效率高；

  2. key/value 在内存中的存储方式是一组 key 连续存储，一组 value 连续存储，而不是key、value成对存储。这种形式方便内存对齐，在数据量较大时可节约因内存对齐造成的浪费；

  3. key 和 value 超过128字节后使用指针存储；

  4. tophash 数组的设计加速了 key 的查找过程，tophash 也被复用来标记扩容操作时的状态；

  5. 用位运算转换求余操作，m % n ，当 n = 1 << B 的时候，可以转换成 m & (1 << B - 1) ；

  6. 渐进式扩容提高效率；

  7. 等量扩容，紧凑操作。

Golang Map 一些待优化的地方

  1. 在扩容迁移过程中，不会重用溢出桶，而是直接申请一个新桶。这里可优化成优先重用没有指针指向的溢出桶，当没有可用的溢出桶时，再去申请新桶。关于这一点， Go 作者已经写在 TODO 里面了。

  2. 当前版本中没有 shrink 操作，Map 只能增长而不能收缩。runtime: maps do not shrink after elements removal (delete)

添加数据

第一步：首先会通过你传的key，结合哈希因子生成哈希值

第二步：拿到哈希值后B位（哈希值是二进制）来确定该数据应该存储在那个捅(Bmap)

第三步：确定捅之后，就可以添加数据了，存储的是将高8位存储到Bmap里面tophash，添加捅满的时候，会通过overflow找到溢出捅。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
    // 计算哈希
    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.
    h.flags ^= hashWriting

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

again:
    bucket := hash & bucketMask(h.B)
    if h.growing() {
        growWork(t, h, bucket)
    }
    b := (*bmap)(add(h.buckets, bucket*uintptr(t.bucketsize)))
    top := tophash(hash)

    var inserti *uint8
    var insertk unsafe.Pointer
    var elem unsafe.Pointer

扩容

扩容条件：

  • map数据总个数 / 捅个数 > 6.5 ，会触发翻倍扩容
  • 使用太多的溢出捅（溢出捅使用太多会导致map处理速度降低）
    • B <= 15 已使用的溢出捅个数 >= 2的B次方时，触发等量扩容
    • B > 15 已使用的溢出捅个数 >= 2的15次方时，触发等量扩容

使用 oldbuckets 映射结构属性进行数据迁移。当存储桶中的数据过多时，迁移开始。我们将桶的当前值保存到旧桶中，然后在桶属性中创建双倍数量的桶。映射数据从旧桶复制到桶。 桶的数量总是 2 的幂。 这就是为什么有B 属性——它是 2 的幂，显示当前的桶数。在迁移映射上是可访问的。这就是为什么在源代码的相同功能中使用存储桶和旧存储桶进行大量工作的原因。迁移后oldbuckets 设置为 nil。数据的迁移地址可以更改，因此 GO 不允许获取映射值的指针：

1
2
3
4
mymap := map[string]string{"1": "1"}
fmt.Println(&mymap["1"])

// cannot take the address of mymap["1"]

随着哈希表中元素的逐渐增加，哈希的性能会逐渐恶化，所以我们需要更多的桶和更大的内存保证哈希的读写性能：

1
2
3
4
5
6
7
8
func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
    ...
    if !h.growing() && (overLoadFactor(h.count+1, h.B) || tooManyOverflowBuckets(h.noverflow, h.B)) {
        hashGrow(t, h)
        goto again
    }
    ...
}

runtime.mapassign 函数会在以下两种情况发生时触发哈希的扩容：

  1. 装载因子已经超过 6.5；
  2. 哈希使用了太多溢出桶；

不过因为 Go 语言哈希的扩容不是一个原子的过程，所以 runtime.mapassign 还需要判断当前哈希是否已经处于扩容状态，避免二次扩容造成混乱。

根据触发的条件不同扩容的方式分成两种，如果这次扩容是溢出的桶太多导致的，那么这次扩容就是等量扩容 sameSizeGrow，sameSizeGrow 是一种特殊情况下发生的扩容，当我们持续向哈希中插入数据并将它们全部删除时，如果哈希表中的数据量没有超过阈值，就会不断积累溢出桶造成缓慢的内存泄漏。runtime: limit the number of map overflow buckets 引入了 sameSizeGrow 通过复用已有的哈希扩容机制解决该问题，一旦哈希中出现了过多的溢出桶，它会创建新桶保存数据，垃圾回收会清理老的溢出桶并释放内存runtime: limit the number of map overflow buckets。

扩容的入口是 runtime.hashGrow：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
func hashGrow(t *maptype, h *hmap) {
    bigger := uint8(1)
    if !overLoadFactor(h.count+1, h.B) {
        bigger = 0
        h.flags |= sameSizeGrow
    }
    oldbuckets := h.buckets
    newbuckets, nextOverflow := makeBucketArray(t, h.B+bigger, nil)

    h.B += bigger
    h.flags = flags
    h.oldbuckets = oldbuckets
    h.buckets = newbuckets
    h.nevacuate = 0
    h.noverflow = 0

    h.extra.oldoverflow = h.extra.overflow
    h.extra.overflow = nil
    h.extra.nextOverflow = nextOverflow
}

哈希在扩容的过程中会通过 runtime.makeBucketArray 创建一组新桶和预创建的溢出桶，随后将原有的桶数组设置到 oldbuckets 上并将新的空桶设置到 buckets 上，溢出桶也使用了相同的逻辑更新，下图展示了触发扩容后的哈希：

我们在 runtime.hashGrow 中还看不出来等量扩容和翻倍扩容的太多区别，等量扩容创建的新桶数量只是和旧桶一样，该函数中只是创建了新的桶，并没有对数据进行拷贝和转移。哈希表的数据迁移的过程在是 runtime.evacuate 中完成的，它会对传入桶中的元素进行再分配。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
func evacuate(t *maptype, h *hmap, oldbucket uintptr) {
    b := (*bmap)(add(h.oldbuckets, oldbucket*uintptr(t.bucketsize)))
    newbit := h.noldbuckets()
    if !evacuated(b) {
        var xy [2]evacDst
        x := &xy[0]
        x.b = (*bmap)(add(h.buckets, oldbucket*uintptr(t.bucketsize)))
        x.k = add(unsafe.Pointer(x.b), dataOffset)
        x.v = add(x.k, bucketCnt*uintptr(t.keysize))

        y := &xy[1]
        y.b = (*bmap)(add(h.buckets, (oldbucket+newbit)*uintptr(t.bucketsize)))
        y.k = add(unsafe.Pointer(y.b), dataOffset)
        y.v = add(y.k, bucketCnt*uintptr(t.keysize))

runtime.evacuate 会将一个旧桶中的数据分流到两个新桶，所以它会创建两个用于保存分配上下文的 runtime.evacDst 结构体，这两个结构体分别指向了一个新桶：

如果这是等量扩容，那么旧桶与新桶之间是一对一的关系，所以两个 runtime.evacDst 只会初始化一个。而当哈希表的容量翻倍时，每个旧桶的元素会都分流到新创建的两个桶中，这里仔细分析一下分流元素的逻辑：

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
for ; b != nil; b = b.overflow(t) {
            k := add(unsafe.Pointer(b), dataOffset)
            v := add(k, bucketCnt*uintptr(t.keysize))
            for i := 0; i < bucketCnt; i, k, v = i+1, add(k, uintptr(t.keysize)), add(v, uintptr(t.valuesize)) {
                top := b.tophash[i]
                k2 := k
                var useY uint8
                hash := t.key.alg.hash(k2, uintptr(h.hash0))
                if hash&newbit != 0 {
                    useY = 1
                }
                b.tophash[i] = evacuatedX + useY
                dst := &xy[useY]

                if dst.i == bucketCnt {
                    dst.b = h.newoverflow(t, dst.b)
                    dst.i = 0
                    dst.k = add(unsafe.Pointer(dst.b), dataOffset)
                    dst.v = add(dst.k, bucketCnt*uintptr(t.keysize))
                }
                dst.b.tophash[dst.i&(bucketCnt-1)] = top
                typedmemmove(t.key, dst.k, k)
                typedmemmove(t.elem, dst.v, v)
                dst.i++
                dst.k = add(dst.k, uintptr(t.keysize))
                dst.v = add(dst.v, uintptr(t.valuesize))
            }
        }
        ...
}

只使用哈希函数是不能定位到具体某一个桶的，哈希函数只会返回很长的哈希，例如：b72bfae3f3285244c4732ce457cca823bc189e0b，我们还需一些方法将哈希映射到具体的桶上。我们一般都会使用取模或者位操作来获取桶的编号，假如当前哈希中包含 4 个桶，那么它的桶掩码就是 0b11(3)，使用位操作就会得到 3， 我们就会在 3 号桶中存储该数据：

1
0xb72bfae3f3285244c4732ce457cca823bc189e0b & 0b11 #=> 0

如果新的哈希表有 8 个桶，在大多数情况下，原来经过桶掩码 0b11 结果为 3 的数据会因为桶掩码增加了一位变成 0b111 而分流到新的 3 号和 7 号桶，所有数据也都会被 runtime.typedmemmove 拷贝到目标桶中：

runtime.evacuate 最后会调用 runtime.advanceEvacuationMark 增加哈希的 nevacuate 计数器并在所有的旧桶都被分流后清空哈希的 oldbuckets 和 oldoverflow：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func advanceEvacuationMark(h *hmap, t *maptype, newbit uintptr) {
    h.nevacuate++
    stop := h.nevacuate + 1024
    if stop > newbit {
        stop = newbit
    }
    for h.nevacuate != stop && bucketEvacuated(t, h, h.nevacuate) {
        h.nevacuate++
    }
    if h.nevacuate == newbit { // newbit == # of oldbuckets
        h.oldbuckets = nil
        if h.extra != nil {
            h.extra.oldoverflow = nil
        }
        h.flags &^= sameSizeGrow
    }
}

之前在分析哈希表访问函数 runtime.mapaccess1 时其实省略了扩容期间获取键值对的逻辑，当哈希表的 oldbuckets 存在时，会先定位到旧桶并在该桶没有被分流时从中获取键值对。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
func mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
    ...
    alg := t.key.alg
    hash := alg.hash(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() {
            m >>= 1
        }
        oldb := (*bmap)(add(c, (hash&m)*uintptr(t.bucketsize)))
        if !evacuated(oldb) {
            b = oldb
        }
    }
bucketloop:
    ...
}

因为旧桶中的元素还没有被 runtime.evacuate 函数分流，其中还保存着我们需要使用的数据，所以旧桶会替代新创建的空桶提供数据。

我们在 runtime.mapassign 函数中也省略了一段逻辑，当哈希表正在处于扩容状态时，每次向哈希表写入值时都会触发 runtime.growWork 增量拷贝哈希表中的内容：

1
2
3
4
5
6
7
8
9
func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
    ...
again:
    bucket := hash & bucketMask(h.B)
    if h.growing() {
        growWork(t, h, bucket)
    }
    ...
}

当然除了写入操作之外，删除操作也会在哈希表扩容期间触发 runtime.growWork，触发的方式和代码与这里的逻辑几乎完全相同，都是计算当前值所在的桶，然后拷贝桶中的元素。

我们简单总结一下哈希表扩容的设计和原理，哈希在存储元素过多时会触发扩容操作，每次都会将桶的数量翻倍，扩容过程不是原子的，而是通过 runtime.growWork 增量触发的，在扩容期间访问哈希表时会使用旧桶，向哈希表写入数据时会触发旧桶元素的分流。除了这种正常的扩容之外，为了解决大量写入、删除造成的内存泄漏问题，哈希引入了 sameSizeGrow 这一机制，在出现较多溢出桶时会整理哈希的内存减少空间的占用。

reference

由浅到深，入门Go语言Map实现原理 - TIGERB

map - 码农桃花源

理解 Golang 哈希表 Map 的原理 | Go 语言设计与实现

深入理解 Go 语言的 map 实现原理_Go_宇宙之一粟_InfoQ写作社区