Golang学习 - 字典（Map）
hanpy
  2023-01-14 12:27:19 2023-01-14 12:27   2023-01-14 12:29:19    

Map 的底层实现是通过 Hash 表来进行的，Map 中所有的 key 都有相同的类型，所有的 value 也有着相同的类型，但是 key 和 value 之间可以是不同的数据类型。

Map的键类型会受到那些限制

字典类型其实是一种哈希表的实现，键是需要在哈希表中定位元素使用的。一般都是通过hash函数来确认桶的位置，然后在桶中再通过键来查找元素，所以字典的键必须是能够做==和!=操作的类型

那些类型不能够做键？

正是因为有了上面的限制，所以函数类型、字典类型、切片类型是不能做为map的key的，因为它们都不支持==和!=操作

优先考虑哪些类型作为Map的键类型

字典是基于hash表的封装，所以对于键来说，“把键值转换为哈希值”以及“把要查找的键值与哈希桶中的键值做对比”，明显是两个重要且比较耗时的操作，求哈希和判等操作的速度越快，对应的类型就越适合作为键类型。

所有的基本类型、指针类型，以及数组类型、结构体类型和接口类型，Go 语言都有一套算法与之对应。这套算法中就包含了哈希和判等。以求哈希的操作为例，宽度(指它的单个值需要占用的字节数)越小的类型速度通常越快。对于布尔类型、整数类型、浮点数类型、复数类型和指针类型来说都是如此。对于字符串类型，由于它的宽度是不定的，所以要看它的值的具体长度，长度越短求哈希越快。

数组类型的值求哈希实际上是依次求得它的每个元素的哈希值并进行合并，所以速度就取决于它的元素类型以及它的长度。细则同上。与之类似，对结构体类型的值求哈希实际上就是对它的所有字段值求哈希并进行合并，所以关键在于它的各个字段的类型以及字段的数量。而对于接口类型，具体的哈希算法，则由值的实际类型决定。

优先选用数值类型和指针类型，通常情况下类型的宽度越小越好。如果非要选择字符串类型的话，最好对键值的长度进行额外的约束。

在值为nil的Map上执行读写操作会发生什么

1
2
3
4
5
6
7
8
9
10
11
12
var m map[int]string
fmt.Println(m == nil) // true

v := m[100]
fmt.Println(v)

v1, ok := m[200]
fmt.Println(v1)
fmt.Println(ok)

// panic: assignment to entry in nil map [recovered]
m[300] = "test_string"

除了添加键-元素对，我们在一个值为nil的字典上做任何操作都不会引起错误。
当我们试图在一个值为nil的字典中添加键-元素对的时候，Go 语言的运行时系统就会立即抛出一个panic。

Map的底层数据结构

Map的底层是一种Hash表的实现，主要涉及到两个数据结构，一个叫hmap ，一个是bmap ，bmap就是常说的桶
go/src/runtime/map.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
type hmap struct {
    count      int            //元素个数，调用len(map)时直接返回
    flags      uint8          //标志map当前状态,正在删除元素、添加元素.....
    B          uint8          //单元(buckets)的对数 B=5表示能容纳32个元素 2^B放代表有多少个桶
    noverflow  uint16        //单元(buckets)溢出数量，如果一个单元能存8个key，此时存储了9个，溢出了，就需要再增加一个单元
    hash0      uint32         //哈希种子
    buckets    unsafe.Pointer //指向单元(buckets)数组,大小为2^B，可以为nil
    oldbuckets unsafe.Pointer //扩容的时候，buckets长度会是oldbuckets的两倍
    nevacute   uintptr        //指示扩容进度，小于此buckets迁移完成
    extra      *mapextra      //与gc相关 可选字段
}

type mapextra struct {
    // 如果 key 和 value 都不包含指针，并且可以被 inline(<=128 字节)
    // 使用 extra 来存储 overflow bucket，这样可以避免 GC 扫描整个 map
    // 然而 bmap.overflow 也是个指针。这时候我们只能把这些 overflow 的指针
    // 都放在 hmap.extra.overflow 和 hmap.extra.oldoverflow 中了
    // overflow 包含的是 hmap.buckets 的 overflow 的 bucket
    // oldoverflow 包含扩容时的 hmap.oldbuckets 的 overflow 的 bucket
    overflow    *[]*bmap
    oldoverflow *[]*bmap

    // 指向空闲的 overflow bucket 的指针
    nextOverflow *bmap
}


// runtime.bmap 定义的结构
type bmap struct {
    tophash [bucketCnt]uint8 // bucketCnt=1<<3,每个捅只能存储8个元素,tophash存储了键的Hash的高8位
}

//实际上编译期间会生成一个新的数据结构
type bmap struct {
    topbits  [8]uint8     // 值能存放8个元素,存储的键的Hash的高8位
    keys     [8]keytype   // 指向keytype的指针
    values   [8]valuetype // 指向valuetype的支持
    overflow uintptr      // 溢出桶的地址
}

Map原理图解

借用一下同事画的一张图

image

初始化

make方式初始化

使用make的方式初始化的时候，在类型检查阶段会转化为runtime.makemap,makemap函数会计算出需要的桶的数量，即log2N，并调用makeBucketArray函数生成桶和溢出桶。如果初始化时生成了溢出桶， 则会放置到map的extra字段里去。

/usr/local/go/src/runtime/map.go | 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
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()

    // 按照提供的元素个数，计算所需要的桶的数量
    B := uint8(0)
    for overLoadFactor(hint, B) {
        B++
    }
    h.B = B

    // allocate initial hash table
    // if B == 0, the buckets field is allocated lazily later (in mapassign)
    // If hint is large zeroing this memory could take a while.
    if h.B != 0 {
        var nextOverflow *bmap
        h.buckets, nextOverflow = makeBucketArray(t, h.B, nil)
        if nextOverflow != nil {
            h.extra = new(mapextra)
            h.extra.nextOverflow = nextOverflow
        }
    }

    return h
}

函数的执行逻辑

  1. 计算哈希占用的内存是否溢出或者超出能分配的最大值
  2. 调用runtime.fastrand获取一个随机的哈希种子；
  3. 根据传入的hint计算出需要的最小需要的桶的数量；
  4. 使用runtime.makeBucketArray创建用于保存桶的数组；

runtime.makeBucketArray会根据传入的 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
func makeBucketArray(t *maptype, b uint8, dirtyalloc unsafe.Pointer) (buckets unsafe.Pointer, nextOverflow *bmap) {
    base := bucketShift(b)
    nbuckets := base
    if b >= 4 {
        nbuckets += bucketShift(b - 4)
        sz := t.bucket.size * nbuckets
        up := roundupsize(sz)
        if up != sz {
            nbuckets = up / t.bucket.size
        }
    }

    if dirtyalloc == nil {
        buckets = newarray(t.bucket, int(nbuckets))
    } else {
        buckets = dirtyalloc
        size := t.bucket.size * nbuckets
        if t.bucket.ptrdata != 0 {
            memclrHasPointers(buckets, size)
        } else {
            memclrNoHeapPointers(buckets, size)
        }
    }

    if base != nbuckets {
        nextOverflow = (*bmap)(add(buckets, base*uintptr(t.bucketsize)))
        last := (*bmap)(add(buckets, (nbuckets-1)*uintptr(t.bucketsize)))
        last.setoverflow(t, (*bmap)(buckets))
    }
    return buckets, nextOverflow
}

字面量初始化

如果map采取了字面量初始化的方式，那么它最终仍然需要转换为 make操作。map的长度被自动推断为字面量的长度。

当哈希表中的元素数量少于或者等于 25 个时，编译器会将字面量初始化的结构体转换成以下的代码，将所有的键值对一次加入到哈希表中：

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

一旦哈希表中元素的数量超过了 25 个，编译器会创建两个数组分别存储键和值，这些键值对会通过如下所示的 for 循环加入哈希：

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

Map访问原理

赋值语句左侧接受参数的个数会决定使用的运行时方法：
当接受一个参数时，会使用runtime.mapaccess1，该函数仅会返回一个指向目标值的指针；
当接受两个参数时，会使用runtime.mapaccess2，除了返回目标值之外，它还会返回一个用于表示当前键对应的值是否存在的bool值：
主要是对key进行hash计算，计算后用低B位(决定桶的位置)和高8位hash(桶中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
40
41
42
43
44
45
46
47
48
49
func mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
	// --省略代码--
    
    // 计算hash值
    hash := t.hasher(key, uintptr(h.hash0))
    m := bucketMask(h.B)
    // b 就是 bucket 的地址
    b := (*bmap)(add(h.buckets, (hash&m)*uintptr(t.bucketsize)))
    
    // oldbuckets 不为 nil，说明发生了扩容
    if c := h.oldbuckets; c != nil {
        // 判断是不是同容量扩容,如果不是,那就是2倍扩容 | same:相同
        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
        }
    }
    // tophash 取其高 8bit 的值
    top := tophash(hash)
    bucketloop:
    // 依次遍历正常桶和溢出桶中的数据
    for ; b != nil; b = b.overflow(t) {
        for i := uintptr(0); i < bucketCnt; i++ {
            if b.tophash[i] != top {
                // emptyRest意思后面都是空的了 | [h1][h2][h3][h4][h5][emptyRest][emptyOne][emptyOne]
                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
            }
        }
    }
    return unsafe.Pointer(&zeroVal[0])
}

这个地方是比较的哈希的高8位，这种设计能够减少同一个桶中有大量相等tophash的概率影响性能。

《Go语言设计与实现》中的图

image

Map赋值原理

map的赋值主要是通过mapassign系列函数来进行的

go/src/runtime/map.go | 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
// 计算key的hash值
hash := t.hasher(key, uintptr(h.hash0))

// 修改map的状态为写入
h.flags ^= hashWriting

// 如果没有buckt分配第一个buckt
if h.buckets == nil {
    h.buckets = newobject(t.bucket) // newarray(t.bucket, 1)
}

again:
// 计算低B位 hash，根据计算出的bucketMask选择对应的bucket
bucket := hash & bucketMask(h.B)

// 当前的map正在重建，则会优先完成重建过程
if h.growing() {
    growWork(t, h, bucket)
}

// 计算出存储的 bucket 的内存位置
b := (*bmap)(add(h.buckets, bucket*uintptr(t.bucketsize)))

// 计算tophash 
top := tophash(hash)

通过遍历比较桶(包括溢出桶)中存储的 tophash 和键的哈希，如果找到了相同结果就会返回目标位置的地址。

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
var inserti *uint8	// 目标元素的在桶中的索引
var insertk unsafe.Pointer	// insertk 和 elem 分别表示键值对的地址，获得目标地址之后会通过算术计算寻址获得键值对 k 和 val：
var elem unsafe.Pointer
bucketloop:
for {
    for i := uintptr(0); i < bucketCnt; i++ {
        if b.tophash[i] != top {
            // 如果这个槽位没有被占，说明可以往这里塞 key 和 value
            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))
        }
        
        // 上面是在比较tophash，这个地方应该是比较key
        if !t.key.equal(key, k) {
            continue
        }
        // 对应的位置已经有 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
    }
    // bucket 的 8 个槽没有满足条件的能插入或者能更新的，去 overflow 里继续找
    ovf := b.overflow(t)
    if ovf == nil {
        break
    }
    b = ovf
}

没有找到 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
40
// 如果触发了最大的 load factor，或者已经有太多 overflow buckets
// 并且这个时刻没有在进行 growing 的途中，那么就开始 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
}

// 前面在桶里找的时候，没有找到能塞这个 tophash 的位置
// 说明当前所有 buckets 都是满的，分配一个新的 bucket
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))
}

// 把新的 key 和 value 存储到应插入的位置
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

函数只会返回内存地址，真正的赋值操作是在编译期间插入的

Map的扩容

为什么要进行扩容

随着向 map 中添加的 key 越来越多，key 发生碰撞的概率也越来越大。bucket 中的 8 个 cell 会被逐渐塞满，查找、插入、删除 key 的效率也会越来越低，这个时候就很有必要进行扩容来提升操作map的效率。

扩容进行的条件

1
2
3
4
1. 负载因为≥6.5
2. 溢出桶太多
    a. buckets的个数<2^15的时候，如果溢出桶的个数大于bucket的个数，就认为溢出桶太多
    b. bucket的个数>2^15的时候，如果溢出桶的个数大于2^15的时候，就认为溢出桶太多

扩容的方式

1
2
1. 负载因子≥6.5的情况（这种情况反应的是桶里的8个元素都快满了），会把hmap中的B加1
2. 溢出桶太多的情况，会进行重新hash，让元素更紧密

扩容相关的源码

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

    flags := h.flags &^ (iterator | oldIterator)
    if h.flags&iterator != 0 {
        flags |= oldIterator
    }
    
    // 提交扩容结果
    h.B += bigger
    h.flags = flags
    h.oldbuckets = oldbuckets
    h.buckets = newbuckets
    h.nevacuate = 0
    h.noverflow = 0

    if h.extra != nil && h.extra.overflow != nil {
        // 把当前的 overflow 赋值给 oldoverflow
        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
    }

	// 实际的哈希表元素的拷贝工作是在 growWork 和 evacuate 中增量慢慢地进行的
}
1
2
3
4
5
6
7
8
9
func growWork(t *maptype, h *hmap, bucket uintptr) {
    // 确保我们移动的 oldbucket 对应的是我们马上就要用到的那一个
    evacuate(t, h, bucket&h.oldbucketmask())

    // 如果还是扩容中，再迁移一个
    if h.growing() {
        evacuate(t, h, h.nevacuate)
    }
}
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
func evacuate(t *maptype, h *hmap, oldbucket uintptr) {
    b := (*bmap)(add(h.oldbuckets, oldbucket*uintptr(t.bucketsize)))
    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() {
            // 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) {
            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() {
                    // 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.
        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)
    }
}
  1. Map的键类型会受到那些限制
  2. 优先考虑哪些类型作为Map的键类型
  3. 在值为nil的Map上执行读写操作会发生什么
  4. Map的底层数据结构
  5. Map原理图解
  6. 初始化
    1. make方式初始化
    2. 字面量初始化
  7. Map访问原理
  8. Map赋值原理
  9. Map的扩容
    1. 为什么要进行扩容
    2. 扩容进行的条件
    3. 扩容的方式
    4. 扩容相关的源码