一、Golang 中的map
1.1 map简介
1)计算机科学里的map简介
在计算机科学里,map 是由一组 key-value
键值对 组成的抽象数据结构,该数据结构一般使用 散列(Hash)技术 把 value 的存储位置 和 key 之间建立一个对应关系f,使得每个关键字key对应一个存储位置f(key),value 就存储在f(key)计算出的位置上,这个位置称之为 桶(bucket),这个对应关系 f 则称之为 散列函数,也叫做 哈希(Hash)函数 或 哈希算法,即哈希函数的作用是将key哈希到其对应的桶中。
采用散列技术将 key-value键值对 存储在一块连续的存储空间(bucket数组)中,这块连续存储空间称为 散列表 或 哈希表(Hash table)。
map 也被称为 相关数组
、映射
、符号表
或者 字典
,map 中同一个 key
只会出现一次。
hash冲突:又称 hash碰撞,是指不同的key经过hash计算得到一样hash值。
hash冲突的常见解决方法有两种:
1、开放寻址法
是指发生碰撞后,从发生冲突的那个单元起,按一定的次序,不断重复,从哈希表中寻找一个空闲的单元,将该键值对存储在该单元中。具体的实现方式包括线性探测法、平方探测法、随机探测法和双重哈希法等。开放寻址法需要的表长度要大于等于所需要存放的元素数量。
2、链地址法
基于数组 + 链表 实现哈希表,桶数组中每个元素都有一个桶指针(指向一个溢出桶),这样数组的每个元素都是一个指针链表,当哈希冲突发生时,新的键值对会按顺序添加到该桶对应的链表的尾部;在查找特定键值对时,可以遍历该链表以查找与之匹配的键值对。
3、两种方案的比较
内存利用率
对于链地址法,基于 数组 + 链表 进行存储,链表节点可以在需要时再创建,开放寻址法需要事先申请好足够内存,因此链地址法对内存的利用率高。
适用场景
链地址法对负载因子的容忍度会更高,适合存储大对象、大数据量的哈希表,而且相较于开放寻址法,它更加灵活,支持更多的优化策略,比如可采用红黑树代替链表。但是链地址法需要额外的空间来存储指针。
对于开放寻址法,它只有数组一种数据结构就可完成存储,继承了数组的优点,对CPU缓存友好,易于序列化操作,但是它对内存的利用率不高,且发生冲突时代价更高。当数据量明确、负载因子小,适合采用开放寻址法。
哈希算法 一般包括两步:
- 第一步,通过哈希算法计算 key 的哈希值,这个结果与 桶(bucket) 的数量无关,而且这个计算出的哈希值一般是离散的(很少重复)(好的哈希函数应该尽量避免 hash冲突 的发生,因为 hash冲突 的发生会降低map的查找性能。);
- 第二步,通过哈希值查找(可以使用一些算法)定位到key-value所在的 桶(bucket) 、再在哈希桶中查找定位具体存放位置;
map两个关键点:
- 是由 key-value 对组成的;
- key 只会出现一次,任何可比较的类型都可以用作 map 的 key;
Tips:
可比较的类型:所有简单的标量类型(布尔、整数、浮点、复数、字符串)、指针、通道、数组、接口、结构体(只有 hash 后的值相等以及字面值相等,才被认为是相同的 key);
不可比较的类型:切片、映射、函数;
map 的设计也被称为 “The dictionary problem(字典问题)”,它的任务是设计一种数据结构用来维护一个集合的数据,并且可以同时对集合进行增删查改的操作。
Tips: map 使用的最主要的数据结构有两种:
- 哈希表(Hash table):使用哈希函数将 key 分配到不同的桶(bucket,也就是数组的不同 index),开销主要在哈希函数的计算以及数组的常数访问时间,在很多场景下,哈希查找表的性能很高,平均查找效率是 O(1),最差是 O(N),如果哈希函数设计的很好,最坏的情况基本不会出现(哈希查找表是乱序的)。
- 搜索树(Search tree):搜索树一般采用自平衡搜索树,包括:AVL 树,红黑树等,自平衡搜索树 的最差搜索效率是 O(logN),遍历自平衡搜索树,返回的 key 序列,一般会按照从小到大的顺序。
2)Golang中map简介
Golang 中的 map 实现采用了 哈希表(Hash table)作为其底层数据结构,采用是用开放寻址法 + 链表法结合的方式解决 hash冲突。
Golang 中 map 是一个指针,占用 8 个字节,指向 底层的 hash表(map实现)。当使用 make 创建 map 时,根据指定的map元素个数,底层调用的是 makem_small() 或 makemap() 函数,函数返回的是一个指向底层hash表的指针,因为返回的是指针,所以 map 作为参数的时候,函数内部能修改map中的元素(key-value对)。
Golang中的 map默认是并发不安全(非线程安全)的,原因如下:
Go 官方在经过了长时间的讨论后,认为 Go map 更应适配典型使用场景(不需要从多个 goroutine 中进行安全访问),而不是为了小部分情况(并发访问),导致大部分程序付出加锁代价(性能),决定了不支持。
golang中在查找、赋值、遍历、删除map的过程中都会检测map的写标志(flag),一旦发现写标志置位(等于1),则直接 panic。赋值和删除函数在检测到写标志是复位(0)之后,先将写标志位置位(1),才会进行之后的操作,完成操作后还需进行置位(0)回复。
检测写标志:
1
2
3
|
if h.flags&hashWriting == 0 {
throw("concurrent map writes")
}
|
设置写标志:
Golang中如果想实现map线程安全,有两种方式:
- 方式一:使用读写锁 map + sync.RWMutex
- 方式二:使用golang提供的 sync.Map
Tips: sync.map是用读写分离实现的,其思想是空间换时间。和map+RWLock的实现方式相比,它做了一些优化:可以无锁访问read map,而且会优先操作read map,倘若只操作read map就可以满足要求(增删改查遍历),那就不用去操作write map(它的读写都要加锁),所以在某些特定场景中它发生锁竞争的频率会远远小于map+RWLock的实现方式。
1.2 map 常见声明和初始化方法
通常使用 make 创建map:
1
|
make(map[key-type]value-type, hint int)
|
make map函数会通过 fastrand 创建一个随机的哈希种子,然后根据传入的 hint 计算出需要的最小需要的桶的数量,最后再使用 makeBucketArray创建用于保存桶的数组,这个方法其实就是根据传入的 B 计算出的需要创建的桶数量,然后在内存中分配一片连续的空间用于存储数据,在创建桶的过程中还会额外创建一些用于保存溢出数据的桶,数量是 2^(B-4) 个。初始化完成后返回指向底层hmap节后的指针。
计算B的初始值: 找到一个 B,使得 map 的负载因子在正常范围内
1
2
3
4
5
6
7
8
9
10
|
B := uint8(0)
for overLoadFactor(hint, B) {
B++
}
h.B = B
// overLoadFactor reports whether count items placed in 1<<B buckets is over loadFactor.func
overLoadFactor(count int, B uint8) bool {
return count > bucketCnt && uintptr(count) > loadFactorNum*(bucketShift(B)/loadFactorDen)
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
// 声明的基本语法
var 变量名称 map[键类型]值类型
// golang中 map的类型可以是bool、数组、string、指针、channel、接口、结构体、map
// 直接声明map
var a map[string]string
var m map[string]map[string]string // map也可以以map作为key-value, 第二个map作为第一个map的value存在
a = make(map[string]string, 10) // 需要先给map声明一块内存空间才能使用,和切片一样使用make
// 10 是map的空间大小,如果不写默认是1
// 直接调用make创建map,
cities := make(map[string]string) //这样不设置元素大小,是可以自增长的
// 直接写入数据创建map, 底层调用 maplit 函数初始化函数实现
heroes := map[string]string{ // 直接在定义的时候赋值,就可以不需要make了,并且自增长
"hero1": "松江",
"hero2": "黄河",
"hero3": "长江", // 这里结尾也是要有逗号的
}
|
1.3 map的增删改查 及 排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
|
// 声明 并使用 make 创建map
var a map[string]string
a = make(map[string]string,10)
// map增加 和 更新
a["no1"] = "松江" // 增加
a["no0"] = "吴用"
a["no3"] = "武松"
a["no1"] = "武松" // 如果key不存在就会增加,如果存在则覆盖
// Go 语言中读取 map 有两种语法:
// 1. 带 comma。当要查询的 key 不在 map 里,带 comma 的用法会返回一个 bool 型变量提示 key 是否在 map 中;
// 2. 不带 comma 的语句则会返回一个 value 类型的零值。如果 map 中存储的 k-v对 有 v=0 的,则应该使用带comma的查询;
// 带 comma 的 map查询
value, ok :=a["no1"] //如果a这个map中存在"no1"的key,那么value会获取值, 而findRes会根据是否存在值,返回true或false
if ok { // 判断是否存在该值去输出
fmt.Println("Find key=no1, value=", value)
}else{
fmt.Println("Not find no1.")
}
// 带 comma 的 map查询
value1 := a["no4"]
fmt.Println("Find key=no4, value=", value) // 输出: Find key=no4, value=
// 遍历map: map 的遍历使用for-range,不能使用for循环
for k := range a{
fmt.Printf("k=%v v=%v\n",k, a[k])
}
for k, v := range a{
fmt.Printf("k=%v v=%v\n",k,v)
}
// map删除key
delete(a,"no1") // 通过delete(map,key名称)进行删除
// Golang中没有一个专门的方法一次删除map的所有key
// 如果要删除map的所有key,只能遍历map 一个一个删除 key 或者 map = make(...) make一个新的空间,让原来的变为垃圾,被gc回收
//直接make一个新的空间即可
a = make(map[string]string)
for k := range a{
delete(a, k)
}
// 统计map的key-values数量
mapSize = len(a) // 用len统计map有多少对key-value
// 排序: go 中map 默认是无序的,并且没有针对map key的排序
var keys []string // 定义一个切片
for k, _ := range a{ // 将map的key 循环出来存放到切片中
keys = append(keys,k)
}
sort.Ints(keys) // 通过sort模块的Ints对整数进行排序
fmt.Println(keys)
for _, k :=range keys{ //按照切片中key的顺序去取map的值
fmt.Printf("map[%v]=%v\n",k ,a[k])
}
|
1.4 如何比较两个map是否相等?
map 深度相等的条件:
- 都为 nil
- 非空、长度相等,指向同一个 map 实体对象
- 相应的 key 指向的 value “深度”相等
- 直接将使用 map1 == map2 是错误的,这种写法只能比较 map 是否为 nil;
- 比较两个非 nil 的 map 只能是遍历 map 的每个元素,比较元素是否都是深度相等(获取key 后 对key排序,依次比较key 及 key对应的value值)
二、map 的底层实现
2.1 map 的底层结构及实现分析
Golang 中 map 底层实现是基于 哈希表(Hash Table) 的数据结构,通过计算键(key)的哈希值(hashcode),然后根据哈希值计算出 bucket桶 编号,在bucket数组中找到对应编号的桶(bucket),最后在桶中进行操作(存储、删除 或 查找等)key-value对,使用了 拉链法解决hash冲突。
Golang 中的 map在语言底层编译是通过如下的抽象结构来表示的,结构如下:
1
2
3
4
5
6
7
8
9
10
|
// ${GPROOT}/src//cmd/compile/internal/types/type.go
// Map contains Type fields specific(特定于) to maps.
type Map struct {
Key *Type // Key type
Elem *Type // Val (elem) type
Bucket *Type // internal struct type representing a hash bucket
Hmap *Type // internal struct type representing the Hmap (map header object)
Hiter *Type // internal struct type representing hash iterator state
}
|
Key、Elem: 键和元素值所属得类型,由于 Golang中的 map 支持多种数据类型, go 会在编译期推断其具体的数据类型
Bucket: 哈希桶的内部结构类型,对应的运行时(runtime)结构体表示是 bmap 结构体
Hmap: hmap(map header对象)的内部结构类型,对应的运行时(runtiime)结构体表示是 hmap 结构体
Hiter: 哈希迭代器状态的内部结构类型,用作range map使用
Map
结构体 定义了Go语言中map的内部实现细节,包括哈希计算、键值对的存储、桶的处理以及迭代操作等。该结构体字段都是编译器在编译期间自动生成的,它允许访问底层结构体的字段,但它并不是公开可用的,无法直接在应用程序中使用,这是因为它属于Go语言的内部实现,通常由Go语言的运行时系统和编译器进行处理和管理。
通过Map
的结构体,可以得出,go语言的map实现重要的底层结构是:hmap
与 bmap
结构,分表代表着map的头部对象(hmap
用于管理 map 的整体状态和元信息)以及桶结构(bmap
存储具体的键值对数据,并处理哈希冲突)。
在 map 的实现中,hmap
是底层用于管理 map 的整体状态和元信息的结构体,key-value对 存储在 hmap
结构中的 bucktes
指针指向的 结构为 bmap
的 bucket 数组中(通过哈希函数计算键的哈希值,可以快速定位到对应的桶);bucket数组中的 每个 bucket元素(bmap
结构体类型)可以存储8个哈希值具有相同特征的 key-value键值对,当bucket数组的一个bucket元素存储的 哈希值具有相同特征的 key-value对 到达8个之后(hash冲突),会通过 bmap
结构中的 overflow
指针指向 一个新的bucket(bmap
结构体类型)称为 溢出桶(overflow bucket),从而形成一个链表(链表法) 解决hash冲突(存放更多的哈希值具有相同特征的key-value对)。
Tips: bucket数组的每一个元素都是一个链表。
通过哈希函数计算出 键(key)的哈希值,可以快速定位到 key 对应的桶 及 在桶 内的位置。
hmap 及相关的结构(源码位于 ${GOROOT}/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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
|
const {
...
// bucket
bucketCntBits = 3
bucketCnt = 1 << bucketCntBits // 一个桶最多8个位置
...
// flags
iterator = 1 // there may be an iterator using buckets
// 可能有迭代器(遍历)在使用buckets
oldIterator = 2 // there may be an iterator using oldbuckets
// 可能有迭代器(遍历)在使用oldbuckets,用于扩容期间
hashWriting = 4 // a goroutine is writing to the map
// 有一个 goroutine正在写入map操作,用于并发读写检测
sameSizeGrow = 8 // the current map growth is to a new map of the same size
// 表示正在进行相同大小的扩容,即 buckets 的数量不变,只是增加溢出桶的数量
...
}
type hmap struct {
// Note: the format of the hmap is also encoded in cmd/compile/internal/reflectdata/reflect.go.
// Make sure this stays in sync with the compiler's definition.
count int // map中元素(key-value对)的数量,调用len()直接返回此值
flags uint8 // buckets 桶数组 状态标识符(bit位操作)
B uint8 // map中桶数组个数的对数,len(buckets) == 2^B,
// 可以最多容纳 6.5 * 2 ^ B 个元素,6.5为负载因子
noverflow uint16 // 溢出桶的近似值,当B小于16时是准确值,大于等于16时是近似值;
// 当溢出的桶太多时,map 会进行 same-size map growth;
// 其实质是避免桶过大导致内存泄露
hash0 uint32 // 哈希种子,用于计算哈希值,为哈希函数的结果引入一定的随机性
buckets unsafe.Pointer // 指向 hash 常规桶数组,常规桶数组长度为 2^B ,存储实际的键值对数据,
// 每个桶存储一组具有相同哈希值的键值对,如果元素个数为0,就为 nil
oldbuckets unsafe.Pointer // 在 map 扩容时,用于临时存储旧的桶数组;
// 扩容过程中会逐渐将键值对从旧的桶迁移到新的桶;
// 如果发生扩容, oldbuckets是指向老的buckets数组的指针,
// 老的buckets数组大小是新的buckets的1/2,
// 当所有旧桶中的数据都已经转移到了新桶(buckets指向的hash桶数组)中时,
// 则清空该指针指向的 旧hash桶数组;
// 非扩容状态下, 它为nil;
// 它是判断是否处于扩容状态的标识
nevacuate uintptr // 用来记录渐进式扩容阶段下一个要迁移的旧桶编号;
// 当 map 的负载因子超过一定阈值时,会触发扩容操作,
// 此时会分配新的 buckets 数组,并将旧的 buckets 数组保存在 oldbuckets 字段中;
// 为了避免一次性搬迁所有的键值对,造成性能下降,Go 语言采用了渐进式扩容的方式,
// 即每次插入或删除键值对时,都会尝试搬迁部分旧桶到新桶中;
// hmap.nevacuate 就是用来指示下一次搬迁的旧桶的索引,它的初始值为 0,
// 每次搬迁后会递增,直到等于旧桶的数量,表示扩容完成。
extra *mapextra // 可选字段,指向 mapextra 结构体的指针,存储额外的位标志,如迭代器状态和特殊标志等;
// 这个字段是为了优化GC扫描而设计的。
}
// 记录 map 溢出桶的信息
type mapextra struct {
// 如果 key 和 value 都不包含指针,并且可以被 inline(<=128 字节)
// 就使用 hmap的extra字段 来存储 overflow buckets,这样可以避免 GC 扫描整个 map
// 然而 bmap.overflow 也是个指针,这时只能把这些 overflow 的指针
// 都放在 hmap.extra.overflow 和 hmap.extra.oldoverflow 中了
// overflow 包含的是 hmap.buckets 的 overflow 的 buckets
// oldoverflow 包含扩容时的 hmap.oldbuckets 的 overflow 的 bucket
overflow *[]*bmap // 指针数组,指向所有溢出桶
oldoverflow *[]*bmap // 指针数组,发生扩容时,指向所有旧的溢出桶
nextOverflow *bmap // 指向空闲的 overflow bucket 的指针
}
// A bucket for a Go map.
type bmap struct {
// tophash generally(通常) contains the top byte of the hash value
// for each key in this bucket. If tophash[0] < minTopHash,
// tophash[0] is a bucket evacuation state instead.
// 译:tophash 通常包含此 buckets 中每个键的哈希值的最高字节。 如果 tophash[0] < minTopHash,则 tophash[0] 是一个桶疏散状态。
tophash [bucketCnt]uint8 // bucketCnt = 8
// Followed by bucketCnt(8)keys and then bucketCnt(8)elems.
// NOTE: packing all the keys together and then all the elems together makes the
// code a bit(稍微) more complicated(复杂) than alternating(使交替) key/elem/key/elem/... but it allows
// us to eliminate padding(消除填充) which would be needed for, e.g., map[int64]int8.
// Followed by an overflow pointer.
}
|
hmap.buckets 是一个指向 bmap
(就是hash表中常说的 bucket桶)数组(也叫常规桶数组)的指针,常规桶数组的长度就是 2^hmap.B^,每个bucket桶 固定能存储 8个 key-value对,bucket元素 实现上是一个固定大小的连续内存块,分成四部分:tophash 值
、8个key值
、8个value值
、指向下一个bucket的指针
。
溢出桶与常规桶:
- 常规桶:也称作 基础桶,是指 hmap.buckets 指针指向的桶数组内的桶(数组元素 bmap结构);
- 溢出桶:是指 常规桶 的 overflow指针指向(链接)的链表元素(也是bmap结构);
Tips: 溢出桶与常规桶的内存布局(结构)是一样的,均为 bmap 结构。
Golang中 map 的哈希表中桶的真正结构(bmap)其实是在编译期间调用 MapBucketType函数 动态
创建的:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
|
// ${GOROOT}/src/cmd/compile/internal/reflectdata/reflect.go
func MapBucketType(t *types.Type) *types.Type {
// ...
// 获取 map 的键类型和值类型
keytype := t.Key()
elemtype := t.Elem()
// 计算键和值的大小
types.CalcSize(keytype)
types.CalcSize(elemtype)
// 如果键的大小超过了 MAXKEYSIZE,则将其变为指针类型
if keytype.Size() > MAXKEYSIZE {
keytype = types.NewPtr(keytype)
}
// 如果值的大小超过了 MAXELEMSIZE,则将其变为指针类型
if elemtype.Size() > MAXELEMSIZE {
elemtype = types.NewPtr(elemtype)
}
// 创建桶类型的字段
field := make([]*types.Field, 0, 5)
// 创建包含 topbits 的数组字段
arr := types.NewArray(types.Types[types.TUINT8], BUCKETSIZE)
field = append(field, makefield("topbits", arr))
// 创建包含键的数组字段
arr = types.NewArray(keytype, BUCKETSIZE)
arr.SetNoalg(true)
keys := makefield("keys", arr)
field = append(field, keys)
// 创建包含值的数组字段
arr = types.NewArray(elemtype, BUCKETSIZE)
arr.SetNoalg(true)
elems := makefield("elems", arr)
field = append(field, elems)
// 创建溢出字段,根据键和值是否有指针来确定类型
otyp := types.Types[types.TUNSAFEPTR]
if !elemtype.HasPointers() && !keytype.HasPointers() {
otyp = types.Types[types.TUINTPTR]
}
overflow := makefield("overflow", otyp)
field = append(field, overflow)
// 创建桶类型
bucket := types.NewStruct(types.NoPkg, field[:])
bucket.SetNoalg(true)
types.CalcSize(bucket)
// 将桶类型赋值给 map 类型的 Bucket 字段
t.MapType().Bucket = bucket
// 设置桶类型的 Map 字段为当前的 map 类型
bucket.StructType().Map = t
// 返回桶类型
return bucket
}
|
通过 MapBucketType函数 实现对结构体 bmap 进行重建为如下结构:
1
2
3
4
5
6
7
8
9
10
11
|
// 实际上编辑期间会动态生成一个新的 bmap 结构体
type bmap struct {
topbits [8]uint8 // 存放key哈希值的高8位,用于决定kv键值对放在桶内的哪个位置
keys [8]keytype // 存放key的数组
values [8]valuetype // 存放value的数组
pad uintptr // 用于对齐内存
overflow uintptr // 指向下一个桶,即溢出桶,拉链法解决hash冲突
// 当发生碰撞时,一个桶里最多放8个键值对。
// 当有第9个key被hash到该桶时,由于没有多余的位置,需要放到溢出桶
// overflow即为指向溢出桶的指针,溢出桶和桶的内部结构是一样的。
}
|
为何桶的个数是2的整数(hmap.B)次幂(2^hmap.B^)?
常用的哈希算法有两种,分别是 取模(%)法 和 与(&)运算法。
- 取模(%)法 就是用 key 计算出的hashcode值 和 bucket数组的长度 length 取模(%) 得到一个桶的编号(bucket数组下标),即:
index = key % length
- 与(&)运算法 就是用 key 计算出的hashcode值 和 bucket数组长度 length-1 进行 与(&) 计算得到一个桶的编号(bucket数组下标),即:
index = key & (length - 1)
在计算机内部,采用 与(&)运算 的速度会非常快,所以哈希函数通常采用 与(&)运算法。但是采用 与(&)运算法 时,桶数组长度必须是2的 整数(hmap.B) 次幂(2^hmap.B^),也即桶的个数必须是2的 整数(hmap.B) 次幂(2^hmap.B^),主要有以下两个原因:
- 不会出现空桶(主要原因):只有当桶的个数(桶数组长度)是2的 整数(hmap.B) 次幂(2^hmap.B^)时,桶数组长度length - 1 的二进制表示为
hmap.B
个 1,在和 hashcode 做 与运算 时不会出现低 hmap.B
位中某个位置恒为0的情况,不可能出现空桶;反之,当桶的个数(桶数组长度) 不是2的 整数(hmap.B) 次幂时,桶数组长度 length - 1 的二进制表示中,低 hmap.B
位必将会存在某些位为0的情况,在做与运算时必将会出现低 hmap.B
位中某些位恒为0的情况,必将出现空桶;
- key % length = key & (length-1):长度为2的 整数(hmap.B) 次幂时,模运算(%) 可以变换为按位 与(&)运算,与运算法其实就是取模法。
插入key-value时会使用哈希函数对key做哈希运算,获取一个hashcode,取高8位存放在 bmap.tophash
字段中。
桶里面最多会装 8 个 key,这些 key 之所以会落入同一个桶,是因为它们经过哈希计算后,哈希结果是 “同一类” 的hashcode(二进制的低 hmap.B 位值相同)。在桶内,又会根据 key 计算出来的 hashcode 值的高 8 位来决定 key 到底落入桶内的哪个位置(一个桶内最多有8个位置)。
如图,B=5 表示hmap的有2^5=32个bmap,buckets是一个指向bmap数组的指针,bmap数组长度为32,每个bmap有8个key。
桶结构中,之所以所有的key放一起,所有的value放一起,而不是key/value一对对的一起存放,目的便是在某些情况下可以省去pad字段,节省内存空间。由于内存对齐的原因,key0/value0/key1/value1… 这样的形式可能需要更多的补齐空间,比如 map[int64]int8 ,1字节的value后面需要补齐7个字节才能保证下一个key是 int64 对齐的。
golang中的map使用的内存会越用越多(即使delete key 后,不会回收内存), 只有每次等量扩容完成后GC掉旧的桶时才会释放回收部分内存。
每个 bucket 设计成最多只能放 8 个 key-value 对,如果有第 9 个 key-value 落入当前的 bucket,那就需要再构建一个溢出桶 bucket ,通过 桶的 overflow 指针连接起来。
Golang实现的 map 其散列函数采用 与(&)运算法,取 hash值的低 hmap.B
位表示桶的编号、高8位(tophash)为key在桶内的位置。
key定位过程:key 经过哈希计算后得到哈希值(hashcode),hashcode 共 64 个 bit 位(64位机),计算 key 到底该落在哪个桶(bucket数组的哪个元素)时,只会用到 hashcode 的二进制位的最低 hmap.B
个 bit 位(hashcode & (2^B^ -1)
,这个操作本质上就是取余操作,但是取余开销太大,所以代码实现上用的 &
位操作运算 代替) 作为 bucket数组的索引index编号(bucket编号);找到 hash桶 的编号后,再用哈希值的高 8 位,找到此 key 在 bucket 中的位置,这是在寻找已有的 key。最开始桶内还没有 key,新加入的 key 会找到第一个空位。
当两个不同的 key 落在同一个桶中,也就是发生了哈希冲突。冲突的解决手段是用开放寻址法 + 链表法结合的方式:在 bucket 中,从前往后找到第一个空位。这样,在查找某个 key 时,先找到对应的桶,再去遍历 bucket 中的 key(此为 开放寻址法)。
例如,当 hmap.B = 5,那么桶的数量(也就是 buckets 数组的长度)是 2^5^ = 32,现在有一个 key 经过哈希函数计算后,得到的哈希结果是:
1
|
10010111 | 000011110110110010001111001010100010010110010101010 │ 00110
|
上图中,假定 B = 5,所以 bucket 总数就是 2^5 = 32。首先计算出待查找 key 的哈希,使用低 5 位 00110,找到对应的 6 号 bucket,使用高 8 位 10010111,对应十进制 151,在 6 号 bucket 中寻找 tophash 值(HOB hash)为 151 的 key,找到了 2 号槽位,这样整个查找过程就结束了。
如果在 bucket 中没找到 hashcode 高 8 位对应的HOB Hash,并且 overflow 不为空,还要继续去 overflow bucket 中寻找,直到找到或是所有的 key 槽位都找遍了,包括所有的 overflow bucket(此为 链接发)。
查找某个 key 的底层函数是 mapacess 系列函数,函数的作用类似,先以mapacess1函数为例:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
|
// runtime/map.go
func mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
// ......
// 如果 *hmap大小为0,或地址为nil,返回零值
if h == nil || h.count == 0 {
if t.hashMightPanic() {
t.hasher(key, 0) // see issue 23734
}
return unsafe.Pointer(&zeroVal[0])
}
// 读写冲突
if h.flags&hashWriting != 0 {
throw("concurrent map read and map write")
}
// 计算哈希值,并且加入 hash0 引入随机性
hash := t.hasher(key, uintptr(h.hash0))
// 比如 B=5,那 m 就是31,二进制是全 1
// 求 bucket num 时,将 hash 与 m 相与,
// 达到 bucket num 由 hash 的低 8 位决定的效果
m := bucketMask(h.B)
// b 就是 bucket 的地址
b := (*bmap)(add(h.buckets, (hash&m)*uintptr(t.bucketsize)))
// oldbuckets 不为 nil,说明发生了扩容
if c := h.oldbuckets; c != nil {
// 如果不是同 size 扩容(看后面扩容的内容)
// 对应条件 1 的解决方案
if !h.sameSizeGrow() {
// 新 bucket 数量是老的 2 倍
m >>= 1
}
// 求出 key 在老的 map 中的 bucket 位置
oldb := (*bmap)(add(c, (hash&m)*uintptr(t.bucketsize)))
// 如果 oldb 没有搬迁到新的 bucket
// 那就在老的 bucket 中寻找
if !evacuated(oldb) {
b = oldb
}
}
// 计算出高 8 位的 hash
// 相当于右移 56 位,只取高8位
top := tophash(hash)
bucketloop:
// 遍历 bucket 的 8 个位置
// bucket 找完(还没找到),继续到 overflow bucket 里找
for ; b != nil; b = b.overflow(t) {
for i := uintptr(0); i < bucketCnt; i++ {
// tophash 不匹配,继续遍历
if b.tophash[i] != top {
if b.tophash[i] == emptyRest {
break bucketloop
}
continue
}
// tophash 匹配,定位到 key 的位置
k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
// key 是指针
if t.indirectkey() {
// 解引用
k = *((*unsafe.Pointer)(k))
}
// 如果 key 相等
if t.key.equal(key, k) {
// 定位到 value 的位置
e := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize))
// value 是指针
if t.indirectelem() {
// 解引用
e = *((*unsafe.Pointer)(e))
}
return e
}
}
}
// 返回零值
return unsafe.Pointer(&zeroVal[0])
}
func tophash(hash uintptr) uint8 {
top := uint8(hash >> (sys.PtrSize*8 - 8))
if top < minTopHash {
// 增加一个 minTopHash
top += minTopHash
}
return top
}
|
函数返回 h[key] 的指针,如果 h 中没有此 key,那就会返回一个 key 相应类型的零值,不会返回 nil。
源码中key定位公式为:
1
|
k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
|
源码中value定位公式为:
1
|
v := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.valuesize))
|
b
是 bmap 的地址,这里 bmap 还是源码里定义的结构体,只包含一个 tophash 数组,经编译器扩充之后的结构体才包含 key,value,overflow 这些字段。 dataOffset
是 key 相对于 bmap 起始地址的偏移:
1
2
3
4
|
dataOffset = unsafe.Offsetof(struct {
b bmap
v int64
}{}.v)
|
因此 bucket 里 key 的起始地址就是 unsafe.Pointer(b)+dataOffset。
第 i 个 key 的地址就要在此基础上跨过 i 个 key 的大小;
value 的地址是在所有 key 之后,因此第 i 个 value 的地址还需要加上所有 key 的偏移。
理解了这些,上面 key 和 value 的定位公式就很好理解了。
tophash 除了存储 hash值的高8字节值,还可以用来表示桶的疏散状态,当 tophash[i] > 5时,tophash[i] 为正常hash值的高8字节值,当 tophash[i] < 5 时, tophash[i]则为 bucket桶 的状态值:
桶的状态值有下列五种:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
// runtime/map.go
const (
...
// Possible tophash values. We reserve(保留) a few possibilities for special marks.
// Each bucket (including its overflow buckets, if any) will have either all or none of its
// entries in the evacuated(搬迁)* states (except during the evacuate() method, which only happens
// during map writes and thus no one else can observe(观察到) the map during that time).
emptyRest = 0 // this cell is empty, and there are no more non-empty cells at higher indexes or overflows. // 表示此桶单元为空(初始时 bucket 的状态),其更高索引或者溢出桶也为空,即后面没有任何键值对存储在此桶中;
emptyOne = 1 // this cell is empty // 表示此桶单元为空,但更高索引的单元可能不为空,即后面可能还有键值对存储在此桶中;
evacuatedX = 2 // key/elem is valid. Entry has been evacuated to first half of larger table. // 表示此桶单元已经被迁移,且迁移到新桶的前半段区间,即新桶的索引为旧桶索引左移一位;
evacuatedY = 3 // same as above, but evacuated to second half of larger table. // 表示此桶单元已经被迁移,且迁移到新桶的后半段区间,即新桶的索引为旧桶索引左移一位加一;
evacuatedEmpty = 4 // cell is empty, bucket is evacuated. //表示此桶单元已经被迁移,bucket的所有单元格都是空的,即没有任何键值对需要迁移;
minTopHash = 5 // minimum tophash for a normal filled cell. // 用来区分键的哈希值的高位和桶状态的标识位值
...
)
|
源码里判断一个 bucket 是否已经搬迁完毕,用到的函数:
1
2
3
4
|
func evacuated(b *bmap) bool {
h := b.tophash[0]
return h > emptyOne && h < minTopHash
}
|
这里只取了 tophash 数组的第一个值,判断它是否在 0 - 5 之间。对比上面的常量,当 top hash 是 emptyOne、evacuatedX、evacuatedY、evacuatedEmpty 这四个值之一,说明此 bucket 中的 key 全部被搬迁到了新 bucket。
Tips: 这个状态值是放在 tophash 数组里,为了和正常的哈希值区分开,会给 key 计算出来的哈希值一个增量:minTopHash。这样就能区分正常的 top hash 值和表示状态的哈希值。
noverflow 字段与extra字段(type mapextra struct)
hmap.noverflow:表示使用的溢出桶数量
在 Golang 中,**溢出桶(overflow bucket)**是指在处理哈希冲突时,当一个桶(bucket)已经达到一定容量限制后,无法再存储更多的键值对时,额外创建的桶。
Golang 中的 map hash表发生哈希冲突时,首先使用开放定址法(open addressing)的线性探测(linear probing)策略,在基础桶内的连续位置中寻找空闲的位置来存储新的键值对,当一个基础桶中的键值对数量超过了一定的阈值(在 Golang 的实现中通常为 8),此时为了解决冲突,Golang 就需要创建一个 溢出桶(overflow bucket)(一个额外的桶)用于存储基础桶中无法容纳的键值对。
在 Golang 中,溢出桶的实现是通过在基础桶类型(bmap)中添加一个名为 overflow
链表指针字段来实现的,而溢出桶的信息则在 hmap 中使用 mapextra
结构体来记录。mapextra
结构体定义如下:
1
2
3
4
5
6
7
8
9
10
11
|
type mapextra struct {
// 如果 key 和 value 都不包含指针,并且可以被 inline(<=128 字节)
// 就使用 hmap的extra字段 来存储 overflow buckets,这样可以避免 GC 扫描整个 map
// 然而 bmap.overflow 也是个指针,这时候只能把这些 overflow 的指针
// 都放在 hmap.extra.overflow 和 hmap.extra.oldoverflow 中了
// overflow 包含的是 hmap.buckets 的 overflow 的 buckets
// oldoverflow 包含扩容时的 hmap.oldbuckets 的 overflow 的 bucket
overflow *[]*bmap // 指针数组,指向所有溢出桶
oldoverflow *[]*bmap // 指针数组,发生扩容时,指向所有旧的溢出桶
nextOverflow *bmap // 指向空闲的 overflow bucket 的指针
}
|
overflow:溢出桶,和hmap.buckets的类型一样也是数组[]*bmap,当正常桶bmap存满了的时候就使用hmap.extra.overflow的bmap
oldoverflow:扩容时存放之前的overflow
nextOverflow:指向溢出桶里下一个可以使用的bmap
当创建 map底层结构时,如果B>4, 如B=5时,map有2^5^=32个常规桶,系统会认为哈希表用到溢出桶的概率比较大,因此会提前分配2^(B - 4) = 2个溢出桶,且溢出桶和常规桶在内存上是连续的。假设此时每个常规桶都没有满,所以溢出桶被使用的个数为0,即noverflow = 0,extra字段中的nextOverflow指向下个空闲溢出桶。如下图所示:
假设2号桶满了,又来了一个key,该key被hash到2号桶,因为2号桶满了,所以2号桶需要链接一个溢出桶。一个溢出桶被使用,所以noverflow = 1;预分配的溢出桶1被使用,所以extra的overflow字段指向预分配的溢出桶1;nextOverflow字段指向下一个空闲溢出桶,即预分配的溢出桶2,如下图所示:
总结起来说:
- hmap(hash map) 是 map 的头部结构体,用于存储 map 的元信息和管理桶(buckets);
- bmap(bucket map) 是哈希表中的一个桶(bucket),用于存储键值对;
- mapextra 是用于扩展 hmap 结构的辅助结构体;
这些结构体之间的关联如下:
- hmap 结构体中的 buckets 字段指向存储桶的内存区域,其中的每个桶都是一个 bmap 结构体;
- hmap 结构体中的 extra 字段指向存储额外溢出桶信息的 mapextra 结构体;
通过这种关联,hmap 结构体管理着整个哈希表的元信息,并且通过 buckets 字段引用了实际的存储桶。每个存储桶都是一个 bmap 结构体,用于存储键值对。如果发生扩容并产生了溢出桶,那么溢出桶的信息会存储在 mapextra 结构体中,并通过 extra 字段引用。这种组合的结构体设计使得 Golang 的 map 实现具备高效的查找和存储特性,并且能够动态调整容量以适应数据的变化。
2.2 map的初始化过程分析
1)运行时(make函数)创建map
map初始化有以下两种方式:
1
2
3
4
5
|
// 不指定初始化map大小
make(map[k]v)
// 指定初始化map大小为hint
make(map[k]v, hint)
|
对于这两种初始化方式在底层编译处理有什么不同,通过反汇编查看,如下列例子:
1
2
3
4
5
6
7
8
9
10
|
// main.go
package main
import "fmt"
func main() {
m := make(map[string]int, 2)
m1 := make(map[string]int, 8)
m2 := make(map[string]int, 9)
fmt.Println(m, m1, m2)
}
|
对例子执行 go build -gcflags=-S main.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
|
main.main STEXT size=185 args=0x0 locals=0x70 funcid=0x0 align=0x0
0x0000 00000 TEXT main.main(SB), ABIInternal, $112-0
0x0000 00000 CMPQ SP, 16(R14)
0x0004 00004 PCDATA $0, $-2
0x0004 00004 JLS 175
0x000a 00010 PCDATA $0, $-1
0x000a 00010 SUBQ $112, SP
0x000e 00014 MOVQ BP, 104(SP)
0x0013 00019 LEAQ 104(SP), BP
0x0018 00024 FUNCDATA $0, gclocals·ykHN0vawYuq1dUW4zEe2gA==(SB)
0x0018 00024 FUNCDATA $1, gclocals·I76sKbn5RubBl1jweLet5Q==(SB)
0x0018 00024 FUNCDATA $2, main.main.stkobj(SB)
0x0018 00024 PCDATA $1, $0
0x0018 00024 CALL runtime.makemap_small(SB)
0x001d 00029 MOVQ AX, main.m+48(SP)
0x0022 00034 PCDATA $1, $1
0x0022 00034 CALL runtime.makemap_small(SB)
0x0027 00039 MOVQ AX, main.m1+40(SP)
0x002c 00044 MOVL $9, BX
0x0031 00049 XORL CX, CX
0x0033 00051 LEAQ type:map[string]int(SB), AX
0x003a 00058 PCDATA $1, $2
0x003a 00058 CALL runtime.makemap(SB)
0x003f 00063 MOVUPS X15, main..autotmp_11+56(SP)
0x0045 00069 MOVUPS X15, main..autotmp_11+72(SP)
0x004b 00075 MOVUPS X15, main..autotmp_11+88(SP)
......
|
结合例子以及汇编代码,可以得出:
- 对于不指定初始化大小和初始化值hint<=8(bucketCnt)时,go会调用 makemap_small 函数,并直接从堆上进行分配;
- 对于 hint > 8 的情况,go 会调用 makemap函数 处理
makemap_small 函数源码如下:
1
2
3
4
5
6
|
// ${GOROOT}/src/runtime/map.go
func makemap_small() *hmap {
h := new(hmap)
h.hash0 = fastrand()
return h
}
|
makemap_small 函数是 Go 语言中用于创建小型 map 的内部函数。
该函数的作用是根据给定的键值对类型 maptype 和初始化大小 hint 创建一个 hmap 结构的实例,且该函数并不直接创建桶(bmap),当map中插入第一个键值对时,才会调用makemapbucket函数来创建第一个桶。
在Go 语言编译阶段,编译器还会使用如下方式快速初始化哈希,这也是编译器对小容量的哈希做的优化:
1
2
3
4
5
6
7
|
var h *hmap
var hv hmap
var bv bmap
h := &hv
b := &bv
h.buckets = b
h.hash0 = fashtrand0()
|
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
|
// ${GOROOT}/src/runtime/map.go
func makemap(t *maptype, hint int, h *hmap) *hmap {
// 计算需要分配的内存大小
mem, overflow := math.MulUintptr(uintptr(hint), t.bucket.size)
// 检查是否发生溢出或超过最大可分配内存
if overflow || mem > maxAlloc {
hint = 0
}
// 如果传入的 hmap 为空,则创建一个新的 hmap
if h == nil {
h = new(hmap)
}
// 初始化 hmap 的一些字段
h.hash0 = fastrand() // 设置 hash0 字段为一个随机数
B := uint8(0)
// 根据负载因子计算 B 值,用于确定桶的数量
for overLoadFactor(hint, B) {
B++
}
h.B = B // 设置 hmap 的 B 字段,即桶的数量
// 如果 B 不为 0,说明需要创建桶
if h.B != 0 {
var nextOverflow *bmap
// 创建存储桶的数组,并返回下一个溢出桶的指针
h.buckets, nextOverflow = makeBucketArray(t, h.B, nil)
// 如果有下一个溢出桶,创建 mapextra 结构体,并将其赋值给 hmap 的 extra 字段
if nextOverflow != nil {
h.extra = new(mapextra)
h.extra.nextOverflow = nextOverflow
}
}
return h // 返回创建或更新后的 hmap
}
|
该函数的主要流程可以概括如下:
- 计算需要分配的内存大小,如果溢出或超过最大可分配内存,则将 hint 设置为 0;
- 如果传入的 hmap 为空,则创建一个新的 hmap;
- 初始化 hmap 的 hash0 字段为一个随机数;
- 根据负载因子计算 B 值,用于确定桶的数量。通过循环逐步递增 B 值,直到满足负载因子条件;
- 设置 hmap 的 B 字段为计算得到的桶的数量;
- 如果 B 不为 0,说明需要创建桶;
- 创建存储桶的数组,并返回下一个溢出桶的指针;
- 如果存在下一个溢出桶,创建 mapextra 结构体,并将其赋值给 hmap 的 extra 字段;
- 返回创建或更新后的 hmap;
对makemap函数中出现的一些重要结构或者函数进行逐步分析:
1、 maptype
maptype 结构体用于描述 map 类型的元信息,它的作用是定义 map 类型的属性和行为,以及存储与 map 相关的类型信息。
定义如下:
1
2
3
4
5
6
7
8
9
10
11
12
13
|
// go 1.20.3 path:/runtiime/type.go
type maptype struct {
typ _type // 表示 map 类型本身的 _type 元信息,包括类型的名称、大小、对齐方式等
key *_type // 表示 map 的键类型的 _type 元信息
elem *_type // 表示 map 的值类型的 _type 元信息
bucket *_type // 表示内部表示哈希桶的 _type 元信息
hasher func(unsafe.Pointer, uintptr) uintptr // 是一个哈希函数,用于计算键的哈希值
keysize uint8 // 键的大小(以字节为单位)
elemsize uint8 // 值的大小(以字节为单位)
bucketsize uint16 // 哈希桶的大小(以字节为单位)
flags uint32 // 一些标志位,用于表示 map 的特性或配置
}
|
这个结构体主要用于编译器和运行时系统来处理 map 类型的创建、赋值、访问和操作等操作。它提供了 map 类型的元信息,以便在运行时正确地分配内存、计算哈希值、查找键值对等。在运行时,通过使用 maptype 结构体中的信息,可以实现对 map 类型的正确处理和操作。
在开发过程中,通常不需要直接使用或操作 maptype 结构体,而是通过 map 类型的声明和使用来间接使用这些信息。只有在需要深入了解 map 类型的底层实现或进行高级编程技巧时,才会涉及到对 maptype 结构体的直接操作和使用。
这里只是知道下这个结构体存在以及作用,更详细的后续会在接口单元进行细说。
2、overLoadFactor
overLoadFactor 函数用于判断给定的负载因子是否超过预定阈值。负载因子表示哈希表中已存储键值对的数量与哈希桶总数之间的比率,是用来判断一个map是否需要扩容的重要因素。
函数定义如下:
1
2
3
4
5
6
7
8
9
10
11
12
|
// go 1.20.3 path:/runtiime/map.go
const(
bucketCntBits = 3
bucketCnt = 1 << bucketCntBits
loadFactorNum = 13
loadFactorDen = 2
)
func overLoadFactor(count int, B uint8) bool {
return count > bucketCnt && uintptr(count) > loadFactorNum*(bucketShift(B)/loadFactorDen)
}
|
该函数判断条件有两个,必须同时满足:
- map 元素总数count需超过8(bucketCnt,即一个桶的数量),因为在map总元素数量少于等于8时,会调用 makemap_small函数,该函数只初始创建了一个hmap结构,并未创建桶空间;
- map 元素总数count与桶的数量的除法结果大于负载因子,即count/bucketShift(B) > loadFactorNum/loadFactorDen ; 其中负载因子相关的常量:loadFactorNum 和 loadFactorDen,loadFactorNum/loadFactorDen 的结果就是触发扩容的阈值负载因子,当前版本中负载因子为 13/2 = 6.5
在这里顺带给出bucketShift函数代码,该函数是根据桶指数b,计算总桶数2^b^的方法:
1
2
3
|
func bucketShift(b uint8) uintptr {
return uintptr(1) << (b & (goarch.PtrSize*8 - 1))
}
|
3、makeBucketArray
runtime.makeBucketArray 的主要作用是创建存储桶的数组,并为每个桶分配内存和初始化状态。这是 map 实现中关键的一步,用于支持哈希表的基本功能。
runtime.makeBucketArray源码如下:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
|
// go 1.20.3 path:/runtiime/map.go
/**
* @Description: 通过make创建map
* @param t map的元类型
* @param b map的哈希桶的数量的log2值
* @param dirtyalloc 可选参数,表示存放桶的内存地址
*/
func makeBucketArray(t *maptype, b uint8, dirtyalloc unsafe.Pointer) (buckets unsafe.Pointer, nextOverflow *bmap) {
//计算常规桶数量,即2^b
base := bucketShift(b)
//将常规桶的数量赋值给nbuckets
nbuckets := base
//如果b>=4,即桶的数量大于等于16,则nbuckets数量加上2^(b-4)个,多加的桶作为溢出桶使用
if b >= 4 {
//则nbuckets数量加上2^(b-4)个,多加的桶作为溢出桶使用
nbuckets += bucketShift(b - 4)
//计算创建nbuckets个桶所需的内存大小
sz := t.bucket.size * nbuckets
//取整对齐内存
up := roundupsize(sz)
if up != sz {
nbuckets = up / t.bucket.size
}
}
/**
如果dirtyalloc为空,则分配新的内存;否则表示内存已经分配好了,直接使用并内存清零
*/
if dirtyalloc == nil {
//调用newarray函数分配一个新的数组作为桶的内存
buckets = newarray(t.bucket, int(nbuckets))
} else {
//直接使用dirtyalloc作为桶的内存
buckets = dirtyalloc
//计算所有桶所需要的内存大小
size := t.bucket.size * nbuckets
if t.bucket.ptrdata != 0 {
//如果桶的元素有指针,则调用memclrHasPointers函数将桶的内存清零
memclrHasPointers(buckets, size)
} else {
//如果桶的元素没有指针,则调用memclrNoHeapPointers函数将桶的内存清零
memclrNoHeapPointers(buckets, size)
}
}
//如果base不等于nbuckets,说明分配了多余的桶作为溢出桶
if base != nbuckets {
//计算溢出桶的位置和设置溢出桶的链接
nextOverflow = (*bmap)(add(buckets, base*uintptr(t.bucketsize)))
last := (*bmap)(add(buckets, (nbuckets-1)*uintptr(t.bucketsize)))
last.setoverflow(t, (*bmap)(buckets))
}
//返回桶的内存地址和溢出桶的地址
return buckets, nextOverflow
}
|
函数的重要流程如下:
- 根据输入的桶数量 b,计算常规桶数量 base(2b);在桶数组的指数 b >= 4时,则需要提前创建好 2(b-4) 个溢出桶;常规桶+溢出桶相加从而得到总桶数量 nbuckets;
Tips: 实际上,如果B大于4,那么哈希表需要分配的桶的个数其实大于2^4。因为当B>4时,系统会认为哈希表用到溢出桶的概率很大,系统会提前预分配2^(B - 4)个溢出桶备用,这些溢出桶与常规的桶在内存上是连续的,只是常规桶当作常规桶使用,溢出桶在常规桶满时,链接在常规桶后边。
- 根据总桶数nbuckets计算出所需内存大小,分配内存并将桶的内存清零。内存分配步骤如下:
- 提供了已分配的内存 dirtyalloc,则使用该内存,
- 否则调用newarray分配新的数组内存,由此也可以知道nbuckets对应的是一个数组指针
- 如果存在溢出桶(base != nbuckets),计算溢出桶的位置和设置溢出桶的链接;
- 返回桶的内存地址和溢出桶的地址。
2)字面量创建map
现代编程语言基本都支持使用字面量的方式初始化哈希,一般都会使用 key: value 的语法来表示键值对,Go 语言中也不例外:
1
2
3
4
5
|
hash := map[string]int{
"1": 2,
"3": 4,
"5": 6,
}
|
在初始化哈希时声明键值对的类型,这种使用字面量初始化的方式最终都会通过 maplit 函数初始化,该函数初始化哈希的过程(实现)如下:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
|
// go 1.20.3 path:/src/cmd/compile/internal/walk/complit.go
func maplit(n *ir.CompLitExpr, m ir.Node, init *ir.Nodes) {
......
//如果字面量超过25个
if len(entries) > 25 {
//根据 n 的键类型和值类型,创建键类型数组 tk 和值类型数组 te,数组长度为 entries 的长度
tk := types.NewArray(n.Type().Key(), int64(len(entries)))
te := types.NewArray(n.Type().Elem(), int64(len(entries)))
//调用 types.CalcSize 计算键类型数组和值类型数组的大小
types.CalcSize(tk)
types.CalcSize(te)
//创建用于存储静态数组,变量名为 vstatk 和 vstate
vstatk := readonlystaticname(tk)
vstate := readonlystaticname(te)
//创建两个空的 ir.CompLitExpr 表达式 datak 和 datae,表示键类型和值类型的静态数组
datak := ir.NewCompLitExpr(base.Pos, ir.OARRAYLIT, nil, nil)
datae := ir.NewCompLitExpr(base.Pos, ir.OARRAYLIT, nil, nil)
//遍历 entries,将每个键和值表达式添加到对应的静态数组中
for _, r := range entries {
r := r.(*ir.KeyExpr)
datak.List.Append(r.Key)
datae.List.Append(r.Value)
}
//使用 fixedlit 函数将键类型和值类型的静态数组转化为静态初始值,并将其赋值给对应的静态变量 vstatk 和 vstate
//最终将静态初始值的设置添加到 init 列表中
fixedlit(inInitFunction, initKindStatic, datak, vstatk, init)
fixedlit(inInitFunction, initKindStatic, datae, vstate, init)
......
return
}
tmpkey := typecheck.Temp(m.Type().Key()) // 创建临时变量 tmpkey,用于存储键的值
tmpelem := typecheck.Temp(m.Type().Elem()) // 创建临时变量 tmpelem,用于存储值的值
// 遍历 entries 中的键值对
for _, r := range entries {
r := r.(*ir.KeyExpr)
index, elem := r.Key, r.Value
ir.SetPos(index) // 设置当前位置为键表达式的位置
appendWalkStmt(init, ir.NewAssignStmt(base.Pos, tmpkey, index)) // 构造赋值语句,将键的值赋给临时变量 tmpkey
ir.SetPos(elem) // 设置当前位置为值表达式的位置
appendWalkStmt(init, ir.NewAssignStmt(base.Pos, tmpelem, elem)) // 构造赋值语句,将值的值赋给临时变量 tmpelem
ir.SetPos(tmpelem)
// 类型检查器将 OINDEX 重写为 OINDEXMAP
lhs := typecheck.AssignExpr(ir.NewIndexExpr(base.Pos, m, tmpkey)).(*ir.IndexExpr)
base.AssertfAt(lhs.Op() == ir.OINDEXMAP, lhs.Pos(), "want OINDEXMAP, have %+v", lhs)
lhs.RType = n.RType
// 构造赋值语句,将键值对存入 map
var a ir.Node = ir.NewAssignStmt(base.Pos, lhs, tmpelem)
a = typecheck.Stmt(a) // 进行类型检查
a = orderStmtInPlace(a, map[string][]*ir.Name{}) // 进行语句排序
appendWalkStmt(init, a) // 将赋值语句添加到初始化语句列表 init 中
}
......
}
|
当哈希表中的元素数量少于或者等于 25 个时,编译器会将字面量初始化的结构体转换成以下的代码,将所有的键值对一次加入到哈希表中:
1
2
3
4
|
hash := make(map[string]int, 3)
hash["1"] = 2
hash["3"] = 4
hash["5"] = 6
|
这种初始化的方式与的数组和切片几乎完全相同,由此看来集合类型的初始化在 Go 语言中有着相同的处理逻辑。
一旦哈希表中元素的数量超过了 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]
}
|
这里展开的两个切片 vstatk 和 vstatv 还会被编辑器继续展开,不过无论使用哪种方法,使用字面量初始化的过程都会使用 Go 语言中的关键字 make 来创建新的哈希并通过最原始的 [] 语法向哈希追加元素。
2.3 map的读取过程分析
map 查询元素值有下面两种写法:
1
2
|
v := m[key]
v, ok := m[key]
|
通过一个例子,通过反汇编,看看对于这两种不同的写法,编译器是如何工作的:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
import (
"fmt"
"time"
)
type TimeStruct struct {
Date time.Time
Id int64
}
func main() {
dat, _ := time.Parse("2006-01-02", "2019-01-01")
m := map[string]int{"one": 1, "two": 2, "three": 3}
m2 := map[TimeStruct]int{TimeStruct{Date: dat, Id: 1}: 1, TimeStruct{Date: dat, Id: 2}: 2, TimeStruct{Date: dat, Id: 3}: 3}
v1 := m["two"]
v2, ok := m["two"]
v3 := m2[TimeStruct{Date: dat, Id: 2}]
fmt.Println(v1, v2, v3, ok)
}
|
执行 go build -gcflags=-S main.go >& 1.txt,得到汇编代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
|
# command-line-arguments
main.main STEXT size=1002 args=0x0 locals=0x348 funcid=0x0 align=0x0
......
0x025b 00603 LEAQ type:map[string]int(SB), AX
0x0262 00610 LEAQ main..autotmp_22+176(SP), BX
0x026a 00618 LEAQ go:string."two"(SB), CX
0x0271 00625 MOVL $3, DI
0x0276 00630 CALL runtime.mapaccess1_faststr(SB)
0x027b 00635 MOVQ (AX), DX
0x027e 00638 MOVQ DX, main.v1+64(SP)
0x0283 00643 LEAQ type:map[string]int(SB), AX
0x028a 00650 LEAQ main..autotmp_22+176(SP), BX
0x0292 00658 LEAQ go:string."two"(SB), CX
0x0299 00665 MOVL $3, DI
0x029e 00670 PCDATA $1, $3
0x029e 00670 NOP
0x02a0 00672 CALL runtime.mapaccess2_faststr(SB)
0x02a5 00677 MOVB BL, main.ok+47(SP)
0x02a9 00681 MOVQ (AX), DX
0x02ac 00684 MOVQ DX, main.v2+56(SP)
0x02b1 00689 MOVQ main..autotmp_55+80(SP), SI
0x02b6 00694 MOVQ SI, main..autotmp_19+96(SP)
0x02bb 00699 MOVQ main..autotmp_56+72(SP), SI
0x02c0 00704 MOVQ SI, main..autotmp_19+104(SP)
0x02c5 00709 MOVQ main..autotmp_57+88(SP), SI
0x02ca 00714 MOVQ SI, main..autotmp_19+112(SP)
0x02cf 00719 MOVQ $2, main..autotmp_19+120(SP)
0x02d8 00728 LEAQ type:map[main.TimeStruct]int(SB), AX
0x02df 00735 LEAQ main..autotmp_19+96(SP), CX
0x02e4 00740 LEAQ main..autotmp_31+128(SP), BX
0x02ec 00748 PCDATA $1, $0
0x02ec 00748 CALL runtime.mapaccess1(SB)
0x02f1 00753 MOVQ (AX), DX
0x02f4 00756 MOVQ DX, main.v3+48(SP)
0x02f9 00761 MOVUPS X15, main..autotmp_45+224(SP)
0x0302 00770 MOVUPS X15, main..autotmp_45+240(SP)
......
|
过汇编代码,可以看出针对不同的写法,在运行时调用不同的函数:
1
2
3
4
5
6
7
8
9
10
11
12
|
//go 1.20.3 path:/src/cmd/complie/internal/typecheck/_builtin/runtime.go
func mapaccess1(mapType *byte, hmap map[any]any, key *any) (val *any)
func mapaccess1_fast32(mapType *byte, hmap map[any]any, key uint32) (val *any)
func mapaccess1_fast64(mapType *byte, hmap map[any]any, key uint64) (val *any)
func mapaccess1_faststr(mapType *byte, hmap map[any]any, key string) (val *any)
func mapaccess1_fat(mapType *byte, hmap map[any]any, key *any, zero *byte) (val *any)
func mapaccess2(mapType *byte, hmap map[any]any, key *any) (val *any, pres bool)
func mapaccess2_fast32(mapType *byte, hmap map[any]any, key uint32) (val *any, pres bool)
func mapaccess2_fast64(mapType *byte, hmap map[any]any, key uint64) (val *any, pres bool)
func mapaccess2_faststr(mapType *byte, hmap map[any]any, key string) (val *any, pres bool)
func mapaccess2_fat(mapType *byte, hmap map[any]any, key *any, zero *byte) (val *any, pres bool)
|
赋值语句左侧接受参数的个数会决定使用的运行时方法:
- 当接受一个参数时(v := m[key]),编译器会根据会使用不同键值类型调用不同函数,该函数仅会返回一个指向目标值的指针,调用函数情况如下:
- mapaccess1 是一个通用的 map 访问函数,适用于任意键类型的 map。它会进行动态的类型检查和键比较操作,以确保正确地访问和返回对应的值;
- mapaccess1_fast32 和 mapaccess1_fast64 是用于在键类型为 int32 和 int64 的 map 中进行快速访问的函数。它们在内部会对键进行哈希计算,并使用快速路径进行查找;
- mapaccess1_faststr 是用于在键类型为 string 的 map 中进行快速访问的函数。它在内部会对键进行哈希计算,并使用快速路径进行查找;
- mapaccess1_fat 是一个通用的 map 访问函数,与 mapaccess1 类似,但处理更复杂的键类型。它针对键类型具有指针或包含指针的结构体时的情况进行了优化;
- 当接受两个参数时(v, ok := m[key]),编译器会调用mapaccess2以及mapaccess2_*** 系列函数,除了返回目标值之外,它还会返回一个用于表示当前键对应的值是否存在的 bool 值,调用函数情况参考mapaccess1以及系列。
对于map的元素读取查找,选用 mapaccess1源码作为标准分析,其他函数流程都类似,不一一解析源码。
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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
|
// go 1.20.3 path:/runtiime/map.go
func mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
//如果哈希表为空,或者哈希表的元素个数为0,那么直接零值对应的指针
if h == nil || h.count == 0 {
// 根据 Go 语言规范,传入非 comparable 类型时候,应该 panic,而不是返回空值
if t.hashMightPanic() {
t.hasher(key, 0) // see issue 23734
}
return unsafe.Pointer(&zeroVal[0])
}
//如果正在进行并发读写操作,那么直接报错
if h.flags&hashWriting != 0 {
throw("concurrent map read and map write")
}
//根据key计算哈希值
hash := t.hasher(key, uintptr(h.hash0))
//计算哈希值对应的桶的最大索引
m := bucketMask(h.B)
//计算哈希值对应的桶的地址
b := (*bmap)(add(h.buckets, (hash&m)*uintptr(t.bucketsize)))
/**
如果 oldbuckets 不为空, 说明那么map发生了扩容,
如果有扩容发生,老的buckets中的数据可能还未搬迁至新的buckets里
所以需要先在老的buckets中找
*/
if c := h.oldbuckets; c != nil {
/**
如果当前不是等大扩容(后面扩容部分会详细介绍),就是桶的数量增加了一倍,这里直接除 2 (即 >> 1)缩小回来,就能对应到在老 bucket 中的位置
*/
if !h.sameSizeGrow() {
m >>= 1
}
// 计算老的 bucket 的地址
oldb := (*bmap)(add(c, (hash&m)*uintptr(t.bucketsize)))
/**
判断 bucket 是否已经迁移
如果在oldbuckets中tophash[0]的值,为evacuatedX、evacuatedY,evacuatedEmpty其中之一,则evacuated()返回为true,代表搬迁完成
因此,只有当搬迁未完成时,才会从此oldbucket中遍历
*/
if !evacuated(oldb) {
b = oldb
}
}
//获取哈希值对应桶中的tophash,桶内的 hash定位仅使用 hash的高 8 位
top := tophash(hash)
/**
下面这个循环会遍历 key 对应的所有桶中的数据。一次循环找一个桶,找不到就沿着 overflow 指针找下一个溢出桶
双重循环遍历:外层循环是从桶到溢出桶遍历;内层是桶中的cell遍历
跳出循环的条件有三种:
第一种是已经找到key值;
第二种是当前桶再无溢出桶;
第三种是当前桶中有cell位的tophash值是emptyRest,这个值在前面解释过,它代表此时的桶后面的cell还未利用,所以无需再继续遍历。
*/
bucketloop:
for ; b != nil; b = b.overflow(t) {
for i := uintptr(0); i < bucketCnt; i++ {
// 通过对比 tophash 来做初步定位
if b.tophash[i] != top {
/**
emptyRest 是特殊的 tophash,该值表明该位置为空,且后面也为空,无需再向后找。
*/
if b.tophash[i] == emptyRest {
break bucketloop
}
continue
}
// 直接计算偏移量找到 key 的地址
//因为在bucket中key是用连续的存储空间存储的,因此可以通过bucket地址+数据偏移量(bmap结构体的大小)+ keysize的大小,得到k的地址
k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
//如果key值是间接引用的,那么就获取实际key值指针
if t.indirectkey() {
k = *((*unsafe.Pointer)(k))
}
//tophash相同也可能是hash碰撞,因此这里要确定当前键值与目标键值相等,如果相同则表示找到了
if t.key.equal(key, k) {
// 和找 key 一样,直接计算偏移量找到 value
e := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize))
//如果value值是间接引用的,那么就获取实际value值指针
if t.indirectelem() {
e = *((*unsafe.Pointer)(e))
}
//返回value值指针
return e
}
}
}
// 没找到的情况下,返回类型零值
return unsafe.Pointer(&zeroVal[0])
}
|
根据上面代码可以梳理出 map 定位元素的逻辑大概是这样:
- 计算 hash 值,获取相应的桶索引和地址;
- 如果当前桶正在扩容,判断桶是否已经迁移,从而判断应该在哪个桶中查询
- 如果当前旧桶中不为空,并且迁移并未完成,则计算旧桶的地址,从旧桶开始查询
其他情况下,从当前的桶开始查询
- 使用 hash 的高 8 位,在桶中依次和 tophash 的元素对比,如果遇到相同的 tophash,取出 key 进行二次确认,如果命中就返回,没有命中继续比完;
- 桶中元素都遍历后,如果还没找到,就在接着溢出桶指针找链接的溢出桶,直到再无溢出桶或者当前桶中有cell位的tophash值是emptyRest为止。
mapaccess2 等的逻辑类似,这里不再解释。
下面对mapaccess1 函数中涉及到一些函数或者技术问题点进行单独分析。
问题一: 知道hmap.B,求map中拥有的bucket的数量以及bucket的索引取值范围?
这个可以使用函数 bucketShift来处理:
1
2
3
|
func bucketShift(b uint8) uintptr {
return uintptr(1) << (b & (goarch.PtrSize*8 - 1))
}
|
- 对于 32 位系统,goarch.PtrSize 为 4,因此表达式简化为 uintptr(1) « (b & 31) ,即 2^(b & 31)^。
- 对于 64 位系统,goarch.PtrSize 为 8,因此表达式简化为 uintptr(1) « (b & 63),即 2^(b & 63)^。
而 bucket 的最大索引则可以使用函数bucketMask:
1
2
3
|
func bucketMask(b uint8) uintptr {
return bucketShift(b) - 1
}
|
这样就可以得到 bucket的索引取值范围: [0, bucketMask(b)]
问题二: 知道hmap.B以及hash值,求此hash所在bucket的索引?
这个问题,来看看 mapaccess1 函数中是怎么做的,代码如下:
1
2
3
|
hash := t.hasher(key, uintptr(h.hash0))
m := bucketMask(h.B)
b := (*bmap)(add(h.buckets, (hash&m)*uintptr(t.bucketsize)))
|
关键的代码是: hash&m,看到这个想起来了没,这就是与运算法,与运算法的公式就是: hash(key)&(bucket_nums - 1)。
与运算法其实就是将 hash值的低hmap.B位与bucket的最大索引进行&运算,例如hmap.B = 5, hash值为: 1001011100001111011011001000111100101010001001011001010101001010 ,可以得出,该map的bucket最大索引为31(可使用bucketMask函数得出), 则所落入的桶索引为:
与运算法其实就是将 hash值的低hmap.B位与bucket的最大索引进行&运算,例如hmap.B = 5, hash值为: 1001011100001111011011001000111100101010001001011001010101001010 ,可以得出,该map的bucket最大索引为31(可使用bucketMask函数得出), 则所落入的桶索引为:
1
2
3
4
|
hash值: 10010111000011110110110010001111001010100010010110010101010 01010
bucket最大索引: & 11111
----------------------------------------------------------------------------------------
01010 = 10
|
最终该hash会落入10号bucket。
问题三: 知道hash值,求此hash的 tophash 数组值?
前面讲述过,tophash数组存储的元素是key键值hash后的哈希值的高8字节,例如hash值为:1001011100001111011011001000111100101010001001011001010101001010 ,可以得出该hash值的tophash存储值为该hash高8位:10010111。
最后总结下mapaccess1 函数基本流程,如下图:
2.4 map的写入过程分析
Map 的赋值操作会被编译成不同函数调用,函数列表如下:
1
2
3
4
5
6
7
|
//go 1.20.3 path:/src/cmd/complie/internal/typecheck/_builtin/runtime.go
func mapassign(mapType *byte, hmap map[any]any, key *any) (val *any)
func mapassign_fast32(mapType *byte, hmap map[any]any, key uint32) (val *any)
func mapassign_fast32ptr(mapType *byte, hmap map[any]any, key unsafe.Pointer) (val *any)
func mapassign_fast64(mapType *byte, hmap map[any]any, key uint64) (val *any)
func mapassign_fast64ptr(mapType *byte, hmap map[any]any, key unsafe.Pointer) (val *any)
func mapassign_faststr(mapType *byte, hmap map[any]any, key string) (val *any)
|
编译器根据与不同类型调用不同函数,这里只用研究最一般的赋值函数 mapassign,其它函数大致流程一致。
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
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
|
//go 1.20.3 path: /src/runtime/map.go
//根据key值寻找一个用于存放 value 的内存地址
func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
//h 为 nil,则panic返回,因为后续涉及存储以及操作,必须保证map已经初始化
if h == nil {
panic(plainError("assignment to entry in nil map"))
}
//hashWriting 是个 flag 位,如果为 1 表示当前有一个 goroutine 正在写入,这是个 unrecoverable 的错误,读取时候如果遇到该状态,会直接崩
if h.flags&hashWriting != 0 {
throw("concurrent map writes")
}
//计算hash
hash := t.hasher(key, uintptr(h.hash0))
//将h.flags设置 hashWriting 以标识当前正在写入
h.flags ^= hashWriting
//假如桶空间为nil,则初始化桶空间
if h.buckets == nil {
// 因为只有 B=0 时候会懒加载,所以这里值仅请了一个桶的空间
h.buckets = newobject(t.bucket) // newarray(t.bucket, 1)
}
again:
//根据与运算计算得出桶的index
bucket := hash & bucketMask(h.B)
// 如果当前正在扩容,那么就负责将当前命中的桶迁移掉,后面扩容部分详细介绍
if h.growing() {
growWork(t, h, bucket)
}
//计算出当前桶的地址
b := (*bmap)(add(h.buckets, bucket*uintptr(t.bucketsize)))
//获取 hash 的高 8 位
top := tophash(hash)
var inserti *uint8 // 记录 tophash 地址,判断空槽等使用
var insertk unsafe.Pointer // 记录 key 地址
var elem unsafe.Pointer //记录 value 地址
bucketloop:
for {
// 遍历 bucket 中的空位
for i := uintptr(0); i < bucketCnt; i++ {
//当前tophash不等于查询的tophash
if b.tophash[i] != top {
//如果当前槽位的tophash经过isEmpty判断返回emptyOne 或 emptyRest 并且 inserti == nil,则当前槽位为空槽位
if isEmpty(b.tophash[i]) && inserti == nil {
inserti = &b.tophash[i] //记录tophash
insertk = add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize)) //记录 key 地址
elem = add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize)) //记录 value 地址
}
// emptyRest 是特殊的 tophash,该值表明该位置为空,且后面也为空,可以拿来直接用
if b.tophash[i] == emptyRest {
//跳出bucketloop, goto done
break bucketloop
}
continue
}
//获取key,走到这里说明 tophash 已经找到, 那就把 key 拿出来确认下
k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
// 存储时候被转成指针存储的数据,需要取出指向的数据
if t.indirectkey() {
k = *((*unsafe.Pointer)(k))
}
//对比key值是否相等,如果不相等就跳出本次循环,进入下一个槽点
if !t.key.equal(key, k) {
continue
}
//key 原本就已经存在,判断下是否要更新 key,需要的话更新一下
if t.needkeyupdate() {
typedmemmove(t.key, k, key)
}
//计算出value的地址
elem = add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize))
goto done
}
//当前桶未找到相关key,则获取溢出桶,从溢出桶中查找
ovf := b.overflow(t)
if ovf == nil {
break
}
b = ovf
}
/**
到达此处,说明未找到空桶并且没找到相关key值一致的相关槽点,需要新增元素
判断新增元素会触发扩容机制,扩容机制需要满足下列条件:
1. 当前map未在扩容中
2. 当前map的负载因子是否达到设定的6.5阈值或者当前map的溢出桶数量是否过多
如果满足扩容条件,进行扩容并且跳转到again处,重新尝试一次前面的查找流程
*/
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 {
// 创建新的溢出桶
newb := h.newoverflow(t, b)
//获取新溢出桶的 tophash 数组的起始地址
inserti = &newb.tophash[0]
//获取新溢出桶的键的起始地址
insertk = add(unsafe.Pointer(newb), dataOffset)
// 获取新溢出桶的值的起始地址
elem = add(insertk, bucketCnt*uintptr(t.keysize))
}
// 如果键是指针类型,需要为键分配内存,并将指针存储到 insertk 中
if t.indirectkey() {
kmem := newobject(t.key)
*(*unsafe.Pointer)(insertk) = kmem
insertk = kmem
}
// 如果值是指针类型,需要为值分配内存,并将指针存储到 elem 中
if t.indirectelem() {
vmem := newobject(t.elem)
*(*unsafe.Pointer)(elem) = vmem
}
// 将 key 复制到 insertk 中
typedmemmove(t.key, insertk, key)
//将 tophash 值设置为 top
*inserti = top
// 更新 hmap 的键值对数量加一
h.count++
done:
// 如果当前哈希表没有正在进行写操作,抛出致命错误
if h.flags&hashWriting == 0 {
throw("concurrent map writes")
}
// 清除 hashWriting 标志位,表示写操作结束
h.flags &^= hashWriting
if t.indirectelem() {
// 如果值是指针类型,需要解引用获取真实的值
elem = *((*unsafe.Pointer)(elem))
}
// 返回最终的值
return elem
}
|
Tips: mapassign 的代码当中, 没有直接将 value 写入内存, 而是将 value 在内存当中的对应地址返回, 后续对内存地址写入 进行操作
根据上面代码其这里总结一下流程:
- 检查哈希表是否为空。如果为空,抛出一个错误;
- 检查哈希表是否正在进行写操作。如果是,并发写操作将导致致命错误;
- 使用键值 key 计算哈希值;
- 切换哈希表的写操作标志;
- 如果哈希表的桶为空,分配一个新的桶;
- 循环遍历桶和溢出桶,查找匹配的键值对;
- 如果找到匹配的键值对,更新对应的值并返回;
- 如果遇到空槽,准备插入新的键值对;
- 检查是否需要进行哈希表的扩容操作,如果需要,则执行扩容操作,并重新开始整个过程;
- 如果是没有找到插入位置,则说明需要创建溢出桶,插入新的键值对并分配内存并复制键值到对应的位置;
- 如果需要间接引用键或值,分配内存并将值写入对应的指针;
- 将新的键值对写入桶;
- 增加哈希表的计数;
- 检查哈希表的写操作标志,并取消标记;
- 如果需要,返回键对应的值;
下面对mapassign函数代码中涉及到一些辅助函数以及技术点进行分析;
辅助函数:isEmpty函数
1
2
3
|
func isEmpty(x uint8) bool {
return x <= emptyOne
}
|
isEmpty 函数用来判断map桶中的cell的元素是否为空,利用比较运算符 <= 来判断可以将条件判断简化为一行代码,并提高代码的可读性和简洁性。
辅助函数:needkeyupdate函数
1
2
3
4
5
6
7
|
if t.needkeyupdate() {
typedmemmove(t.key, k, key)
}
func (mt *maptype) needkeyupdate() bool {
return mt.flags&8 != 0
}
|
在对map做插入时,当发现插入的key已经存在时,正常流程只需要更新value的值,但当needkeyupdate函数返回为true时,还需要更新key的值,这是为什么呢?
在 Go 语言中,当使用非指针类型作为 map 的键时,键的值通常用于计算哈希值和进行键的比较操作。如果允许直接修改键的值,那么在修改后的值与原来的值不同时,就会导致哈希值和比较结果的不一致,进而破坏了 map 的内部数据结构的一致性。
为了避免这种情况发生,非指针类型的键被设计为不可变的。这意味着一旦创建了一个键值对并将其插入到 map 中,就不应该再修改键的值。如果需要更新键的值,通常的做法是创建一个新的键值对,使用新的键值对替换原来的键值对。
通过将非指针类型的键设计为不可变,可以确保 map 在进行哈希计算和键的比较时始终使用一致的值,从而保持 map 的正确性和一致性。此外,这也提醒了开发者在使用 map 时需要注意键的不可变性,避免可能的错误和意外行为。
辅助函数: map扩容条件判断
1
2
3
4
|
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
}
|
从此代码可以看到,触发扩容有2种情况: overLoadFactor(h.count+1, h.B) == true 或者 tooManyOverflowBuckets(h.noverflow, h.B)) == true ,这分别对应下列两种情况:
1、负载因子超标
负载因子超标主要使用函数 overLoadFactor进行判断,该函数在【初始化】章节中已经详细分析过,可以回头看看,再次不再重复。
2、使用溢出桶过多
溢出桶过多,主要判断的函数tooManyOverflowBuckets,源码如下:
1
2
3
4
5
6
7
|
//go 1.20.3 path: /src/runtime/map.go
func tooManyOverflowBuckets(noverflow uint16, B uint8) bool {
if B > 15 {
B = 15
}
return noverflow >= uint16(1)<<(B&15)
}
|
从代码判断溢出桶是否太多的规则如下:
- 当桶总数 < 2^15^ 时,如果溢出桶总数 >= 桶总数,则认为溢出桶过多。
- 当桶总数 >= 2 ^15^ 时,直接与 2^15^ 比较,当溢出桶总数 >= 2^15^ 时,即认为溢出桶太多了
其实 使用溢出桶过多 这个条件是对 负载因子超标 条件的补充,因为在负载因子比较小的情况下,有可能 map 的查找和插入效率也很低,而 负载因子超标条件 无法识别不出来这种情况。表面现象就是计算负载因子的分子比较小,即 map 里元素总数少,但是桶数量多(真实分配的桶数量多,包括大量的溢出桶),什么操作才会产生这种现象呢?不断的增删,这样会造成overflow的bucket数量增多,但负载因子又不高,未达到 负载因子超标 临界值,就不能触发扩容来缓解这种情况,这样会造成桶的使用率不高,值存储得比较稀疏,查找插入效率会变得非常低,因此有了 使用溢出桶过多判断 指标。这就像是一座空城,房子很多,但是住户很少,都分散了,找起人来很困难。
辅助函数: 溢出桶的函数
overflow以及setoverflow函数:
1
2
3
4
5
6
7
8
9
10
11
|
//go 1.20.3 path: /src/runtime/map.go
//bmap的溢出桶的指针定位
func (b *bmap) overflow(t *maptype) *bmap {
return *(**bmap)(add(unsafe.Pointer(b), uintptr(t.bucketsize)-goarch.PtrSize))
}
//bmap的溢出桶的指针设置
func (b *bmap) setoverflow(t *maptype, ovf *bmap) {
*(**bmap)(add(unsafe.Pointer(b), uintptr(t.bucketsize)-goarch.PtrSize)) = ovf
}
|
overflow 方法接收一个 maptype 参数,用于确定桶的大小,并返回当前桶的溢出桶指针。它通过将当前桶的地址加上桶的大小减去指针大小的偏移量,然后通过类型转换来获取溢出桶的指针。这个函数在遍历桶时,可以使用该方法获取当前桶的溢出桶。
setoverflow 方法接收一个 maptype 参数和一个溢出桶指针 ovf,用于设置当前桶的溢出桶指针。它通过将当前桶的地址加上桶的大小减去指针大小的偏移量,然后通过类型转换来设置溢出桶的指针。这个函数在创建新的溢出桶并将其链接到当前桶时使用。
这两个方法通过指针操作实现了溢出桶的获取和设置,用于在哈希表中处理溢出桶的相关操作。
createOverflow函数:
1
2
3
4
5
6
7
8
9
10
11
|
//go 1.20.3 path: /src/runtime/map.go
//创建hmap.extra结构
func (h *hmap) createOverflow() {
if h.extra == nil {
h.extra = new(mapextra)
}
if h.extra.overflow == nil {
h.extra.overflow = new([]*bmap)
}
}
|
这个函数的主要作用是创建 hmap.extra的结构,结构的创建目的是确保在需要创建溢出桶时,哈希表的 extra 字段和 overflow 字段都被正确地初始化。这样,在需要使用溢出桶时,可以直接使用 extra 和 overflow 字段来操作溢出桶的相关信息。
incrnoverflow函数:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
//go 1.20.3 path: /src/runtime/map.go
//根据一定规则增加哈希表 hmap 的溢出桶计数, noverflow是一个近似计数
func (h *hmap) incrnoverflow() {
if h.B < 16 {
// 如果桶数小于16,则每次调用都增加溢出桶计数
h.noverflow++
return
}
// 计算掩码,用于确定是否增加溢出桶计数
mask := uint32(1)<<(h.B-15) - 1
// 通过与掩码进行按位与运算来决定是否增加溢出桶计数
if fastrand()&mask == 0 {
h.noverflow++
}
}
|
该函数的作用是根据一定规则增加哈希表 hmap 的溢出桶计数。
在 h.B < 16 的情况下,每次调用函数 incrnoverflow() 都会增加溢出桶计数 h.noverflow 的值。
在 h.B >= 16 的情况下,根据掩码 mask 和随机数的按位与运算结果,决定是否增加溢出桶计数。掩码 mask 是根据桶数 B 计算得到的,它具有以下特点:
- mask 在二进制表示中,第 B-15 位之前都为 1,之后都为 0。
- 例如,当 B 为 16 时,掩码 mask 的二进制表示为 1111111111111110。
函数会调用 fastrand() 生成一个随机数,并与掩码 mask 进行按位与运算。按位与运算的结果为 0,表示随机数的二进制表示的第 B-15 位之前都为 0。
通过这种机制,当桶数较大时,每次调用函数 incrnoverflow() 增加溢出桶计数的概率较小。这样可以在一定程度上控制溢出桶的数量,以保持哈希表的负载均衡和性能。具体的规律是根据掩码和随机数的按位与运算结果决定的,这取决于具体的随机数生成算法和掩码的设置。
newoverflow函数:
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 1.20.3 path: /src/runtime/map.go
func (h *hmap) newoverflow(t *maptype, b *bmap) *bmap {
var ovf *bmap
// 检查是否存在额外的溢出桶列表
if h.extra != nil && h.extra.nextOverflow != nil {
ovf = h.extra.nextOverflow
// 如果当前溢出桶的下一个溢出桶为空,则将下一个溢出桶设置为当前溢出桶之后的地址
// 否则,将当前溢出桶的下一个溢出桶设为nil,并重置下一个溢出桶为nil
if ovf.overflow(t) == nil {
h.extra.nextOverflow = (*bmap)(add(unsafe.Pointer(ovf), uintptr(t.bucketsize)))
} else {
ovf.setoverflow(t, nil)
h.extra.nextOverflow = nil
}
} else {
// 创建新的溢出桶
ovf = (*bmap)(newobject(t.bucket))
}
// 增加溢出桶计数
h.incrnoverflow()
// 如果桶中的键值对不包含指针数据,则需要创建溢出桶列表
if t.bucket.ptrdata == 0 {
h.createOverflow()
*h.extra.overflow = append(*h.extra.overflow, ovf)
}
// 设置桶的溢出指针为新的溢出桶
b.setoverflow(t, ovf)
return ovf
}
|
该函数的目的是管理哈希表中的溢出桶,确保当哈希表中的键值对数量超过桶的容量时,能够动态地创建新的溢出桶,并将其链接到正确的位置,以保持哈希表的正确性和性能。
技术点:
关于h.flags的位运算,在mapassign 函数中涉及到的代码如下:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
// flags
const = (
iterator = 1 // there may be an iterator using buckets
oldIterator = 2 // there may be an iterator using oldbuckets
hashWriting = 4 // a goroutine is writing to the map
sameSizeGrow = 8 // the current map growth is to a new map of the same
)
//与运算
if h.flags&hashWriting != 0 {
fatal("concurrent map writes")
}
//异或运算
h.flags ^= hashWriting
|
代码中关于 h.flags值有四种,转换成二进制如下:
1
2
3
|
flags: 1 2 4 8
二进制: 0001 0010 0100 1000
------------------------------------------------
|
从转换的对比可以看出,h.flags取值为了方便位运算,采取了不同二进制位上取1,其余位置取0后的结果。
对于 h.flags 这个表达式来说,& 和 ^ 的作用如下:
- h.flags & hashWriting 会将 h.flags 的值与 hashWriting 进行按位与操作,得到的结果是 h.flags 中只保留与 hashWriting 相对应的位的值,其它位都被清零。在mapassign 函数中主要用来判断h.flags是否处于Writing状态。
- h.flags ^= hashWriting 会将 h.flags 的值与 hashWriting 进行按位异或操作,得到的结果是 h.flags 中与 hashWriting 相对应的位取反,其它位保持不变。在mapassign 函数中主要用来将h.flags值的状态更改为非Writing状态。
总结下mapassign 函数相关流程,如下图:
2.5 map 的扩容过程分析
触发扩容的时机代码:
1
2
3
4
|
if !h.growing() && (overLoadFactor(h.count+1, h.B) || tooManyOverflowBuckets(h.noverflow, h.B)) {
hashGrow(t, h)
......
}
|
从此代码可以看到,触发扩容有2种情况: overLoadFactor(h.count+1, h.B) == true
或者 tooManyOverflowBuckets(h.noverflow, h.B)) == true
,这分别对应下列两种情况:
触发 map 扩容的时机(插入、删除key):
- 当负载因子超过6.5时,扩容一倍,属于增量扩容;
- 当使用的溢出桶过多时,重新分配一样大的内存空间,属于等量扩容(实际上没有扩容,主要是为了回收空闲的溢出桶,节省空间,提高 map 的查找和插入效率);
针对触发扩容有两种情况,扩容算法根据这两种情况也做了区分:
- 针对 负载因子超标,将 B + 1,新建一个buckets数组,新的buckets大小是原来的2倍,然后旧buckets数据搬迁到新的buckets。该方法称之为 增量扩容。
- 针对 使用溢出桶过多,并不扩大容量,buckets数量维持不变,重新做一遍类似增量扩容的搬迁动作,把松散的键值对重新排列一次,以使bucket的使用率更高,进而保证更快的存取。该方法称之为 等量扩容。
Tips:
- 其实存在一个极端的情况:如果插入 map 的 key 哈希都一样(二进制的低 hmap.B 位相同),那么它们就会落到同一个 bucket 里,超过 8 个就会产生 overflow bucket,结果也会造成 overflow bucket 数过多。移动元素其实解决不了问题,因为这时整个哈希表已经退化成了一个链表,操作效率变成了 O(n)。但 Go 的每一个 map 都会在初始化阶段的 makemap时定一个随机的哈希种子,所以要构造这种冲突是没那么容易的。
- 为什么会出现溢出桶过多这种情况?
这种情况可能是因为map删除的特性导致的。当不断向哈希表中插入数据,并且将它们又全部删除时,map内存占用并不会减少,因为删除只是将桶对应位置的tophash置nil而已。这种情况下,就会不断的积累溢出桶造成内存泄露,为了解决这种情况,采用了等量扩容的机制,一旦哈希表中出现了过多的溢出桶,会创建新桶保存数据,gc会清理掉老的溢出桶,从而避免内存泄露。
1)map的负载因子
负载因子 也称为 装载因子,是指map中平均每个桶存储的元素个数,Go的负载因子阈值常量:6.5,map 最多可容纳 6.5*2^B^ 个元素。
负载因子 等于 map中元素的个数(hmap.count) 除与 map的容量(2^hmap.B^),即: len(map) / 2^B^。负载因子用来表示空闲位置的情况,负载因子越大,表明空闲位置越少,冲突也越多。随着负载因子的增大,哈希表线性探测的平均用时就会增加,这会影响哈希表的性能,当负载因子大于70%,哈希表的性能就会急剧下降,当负载因子达到100%,整个哈希表就会完全失效,这个时候,查找和插入任意元素的复杂度都是O(N),因为需要遍历所有元素。
另外负载因子与扩容、迁移等重新散列(rehash) 行为有直接关系:
- 在程序运行时,会不断地进行插入、删除等,会导致 bucket 不均,内存利用率低,这是就需要迁移;
- 在程序运行时,出现负载因子过大,需要做扩容,解决 bucket 过大的问题;
负载因子是哈希表中的一个重要指标,主要目的是为了平衡 buckets 的存储空间大小和查找元素时的性能高低。实际上这是 Go 官方的经过认真的测试得出的数字,一起来看看官方的这份测试报告。
- loadFactor:负载因子,也叫负载因子;
- %overflow:溢出率,有溢出 bukcet 的百分比;
- bytes/entry:平均每对 key/alue 的开销字节数;
- hitprobe:查找一个存在的 key 时,要查找的平均个数;
- missprobe:查找一个不存在的 key 时,要查找的平均个数;
Go 官方发现:负载因子越大,填入的元素越多,空间利用率就越高,但发生冲突的几率就变大;反之,装数因子越小,填入的元素越少,冲突发生的几率减小,但空间利用率低,而且还会提高扩容操作的次数。
根据这份测试结果和讨论,Go 官方取了一个相对适中的值,把 Go 中的 map 的负数因子硬编码为 6.5,这就是 6.5 的选择缘由。这意味着在 Go 语言中,当 map存储的元素个数大于或等于 6.5*桶个数 时,就会发扩容行为。
2)如何定义溢出桶是否太多需要等量扩容呢?两种情况:
- 当B小于15时,溢出桶的数量超过2^B,属于溢出桶数量太多,需要等量扩容;
- 当B大于等于15时,溢出桶数量超过2^15,属于溢出桶数量太多,需要等量扩容。
扩容策略(怎么扩容?):
Go 会创建一个新的 buckets 数组,新的 buckets 数组的容量是旧buckets数组的两倍(或者和旧桶容量相同),将原始桶数组中的所有元素重新散列到新的桶数组中。这样做的目的是为了使每个桶中的元素数量尽可能平均分布,以提高查询效率。旧的buckets数组不会被直接删除,而是会把原来对旧数组的引用去掉,让GC来清除内存。
在map进行扩容迁移的期间,不会触发第二次扩容。只有在前一个扩容迁移工作完成后,map才能进行下一次扩容操作。
搬迁策略:
由于map扩容需要将原有的kv键值对搬迁到新的内存地址,如果一下子全部搬完,会非常的影响性能。go 中 map 的扩容采用渐进式的搬迁策略,原有的 key 并不会一次性搬迁完毕,一次性搬迁会造成比较大的延时,每次最多只会搬迁 2 个 bucket,将搬迁的O(N)开销均摊到O(1)的赋值和删除操作上。
搬迁相关的 oldbuckets字段和nevacuate字段
如果一个map中的键值对数量较多,在扩容时一次性迁移所有桶花费的时间是比较显著的。一种可行的办法是当需要扩容时,先分配足够多的新桶,在每次执行map的读写操作时,分批将旧桶中的所有元素迁徙到新桶中。所以需要 oldbuckets 来记录旧桶所在的位置,需要 nevacuate 来指示当前的扩容进度。当执行map读写操作时,如果监测到当前属于扩容阶段,会根据oldbuckets和nevacuate迁徙一部分旧桶中的元素至新桶,直到多次分批迁徙完毕。这种分批迁徙的方式称之为“渐进式扩容”,渐进式扩容可以避免一次性迁移花费过多时间所带来的性能抖动。
举个例子,帮助理解oldbuckets字段和nevacuate字段。
假设现在有一个map,该map只有1个桶,桶里的元素是7个,达到了翻倍扩容条件(平均每个桶里的元素个数超过负载因子loadFactor),那么在扩容前,内存布局如下:
扩容后,系统新分配两个桶给该map,buckets则指向新被分配的两个桶,oldbuckets指向原先的桶。nevacuate的值为0,表示接下来迁移编号为0的旧桶。内存布局如下所示:
接下来的每次读写,会分批将旧桶中的7个元素迁移至两个新桶中,直到迁移完毕,oldbuckets指向nil。
在源码中,扩容相关的主要是 hashGrow() 函数与 growWork()函数。
扩容的开始逻辑在 runtime.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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
|
//go 1.20.3 path: /src/runtime/map.go
//分配内存地址,做好了迁移准备,并没有真正迁移数据
func hashGrow(t *maptype, h *hmap) {
/**
bigger 保存了本次操作 B 的增量,等量扩容设置为 0,增量扩容设置为 1
下面判断是否负载因子超标,如果超标则使用增量扩容,未超标则使用等量扩容,并标注h.flags
*/
bigger := uint8(1)
//map元素比例并未超过负载因子,做等量扩容
if !overLoadFactor(h.count+1, h.B) {
//则将 `bigger` 设置为 0,表示不增加桶的数量,并标记哈希表为 `sameSizeGrow`,表示扩容后的桶数量与原桶数量相同
bigger = 0
h.flags |= sameSizeGrow
}
/**
将当前buckets地址赋值给oldbuckets
调用 `makeBucketArray` 函数创建新的桶数组,并计算下一个溢出桶
*/
oldbuckets := h.buckets
newbuckets, nextOverflow := makeBucketArray(t, h.B+bigger, nil)
//将哈希表的标志位中的 iterator 和 oldIterator 标记清除
flags := h.flags &^ (iterator | oldIterator)
// 如果哈希表正在进行迭代操作,则保留 `iterator` 和 `oldIterator` 的标记
if h.flags&iterator != 0 {
flags |= oldIterator
}
//更新哈希表的桶数量和标志位
h.B += bigger
h.flags = flags
h.oldbuckets = oldbuckets
h.buckets = newbuckets // 换桶
h.nevacuate = 0 //迁移进度为0
h.noverflow = 0 //溢出桶数量为0
// 处理额外的溢出桶
if h.extra != nil && h.extra.overflow != nil {
// 如果旧的溢出桶不为空,抛出异常,表示不应该存在旧的溢出桶
if h.extra.oldoverflow != nil {
throw("oldoverflow is not nil")
}
// 将当前的溢出桶作为旧的溢出桶,并清空当前溢出桶
h.extra.oldoverflow = h.extra.overflow
h.extra.overflow = nil
}
//如果 makeBucketArray 函数创建了新的溢出桶,将下一个溢出桶设置为新的溢出桶
if nextOverflow != nil {
if h.extra == nil {
h.extra = new(mapextra)
}
h.extra.nextOverflow = nextOverflow
}
}
|
函数的主要流程:
- 判断是否需要增大哈希表的大小:
- 如果当前哈希表的负载因子不超过阈值,则不需要增大大小,将 bigger 设置为 0,同时将 sameSizeGrow 标志位置为 1。
- 否则,需要增大双倍大小,将 bigger 设置为 1,同时清除 sameSizeGrow 标志位。
- 保存旧的桶数组和迁移溢出桶:
- 将旧的桶数组保存在 oldbuckets 变量中。
- 调用 makeBucketArray 函数创建新的桶数组 newbuckets(桶数组大小根据bigger 决定,如果bigger 为1则新桶数组为原来桶数组2倍,否则等于原桶数组长度),并返回下一个迁移的溢出桶。
- 更新哈希表的相关字段:B 值增加 bigger,更新标志位 flags,将 oldbuckets 设置为保存的旧桶数组,将 buckets 设置为新的桶数组,将 nevacuate 和 noverflow 重置为 0。
- 处理额外的溢出桶:
- 如果存在额外的溢出桶,并且旧的溢出桶为空,将旧的溢出桶设置为当前溢出桶,并清空当前溢出桶。
- 如果存在下一个迁移的溢出桶,则创建新的 mapextra 结构,并将其设置为哈希表的 extra 字段,将下一个迁移的溢出桶链接到 extra 的 nextOverflow 字段。
hashGrow() 函数实际上并没有真正地“搬迁”,它只是分配好了新的 buckets,并将老的 buckets 挂到了 oldbuckets 字段上。因为map 采用的是渐进扩容的方式,避免因为一次性的全量数据迁移引发性能抖动。
真正搬迁 buckets 的动作在 growWork() 函数中,而调用 growWork() 函数的动作是在 mapassign() 和 mapdelete() 函数中。也就是插入(包括修改)、删除 key 的时候,都会尝试进行搬迁 buckets 的工作。
growWork 函数的调用:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
//go 1.20.3 path: /src/runtime/map.go
func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
......
bucket := hash & bucketMask(h.B)
if h.growing() {
growWork(t, h, bucket)
}
......
}
func mapdelete(t *maptype, h *hmap, key unsafe.Pointer) {
......
bucket := hash & bucketMask(h.B)
if h.growing() {
growWork(t, h, bucket)
}
......
}
|
growWork 函数源码如下:
1
2
3
4
5
6
7
8
9
10
11
12
|
func growWork(t *maptype, h *hmap, bucket uintptr) {
/**
bucket 是新桶的位置
oldbucketmask 返回的是扩容之前的哈希掩码,而传入的 bucket 参数是新桶中的位置
bucket & oldbucketmask 算出了目标桶在旧桶中的位置
*/
evacuate(t, h, bucket&h.oldbucketmask())
//如果搬迁任务还没完成,需要肩负额外迁移一个 bucket 的任务,以加快进度
if h.growing() {
evacuate(t, h, h.nevacuate)
}
}
|
当每次触发写、删操作时,会先检查 oldbuckets 是否搬迁完毕(检查 oldbuckets 是否为 nil),再决定是否进行搬迁工作。搬迁也只会为处于扩容流程中的 map 最多完成两组桶的数据迁移:
- 一组桶是当前写、删操作所命中的桶;
- 另一组桶是,当前未迁移的桶中,索引最小的那个桶;
map中桶的实际迁移操作是调用 runtime.evacuate 来进行的,为了准备进行桶迁移操作,runtime.evacuate 会将一个旧桶中的数据分流到两个新桶,其中 x 表示主目标桶,y 表示备用目标,该步骤代码为:
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
|
//go 1.20.3 path: /src/runtime/map.go
func evacuate(t *maptype, h *hmap, oldbucket uintptr) {
//定位当前bucket在旧桶的起始地址
b := (*bmap)(add(h.oldbuckets, oldbucket*uintptr(t.bucketsize)))
//获取旧桶的数量
newbit := h.noldbuckets()
//如果b桶尚未被迁移过
if !evacuated(b) {
//声明一个长度为2的数组xy,数组元素为evacDst类型
var xy [2]evacDst
//x指向xy数组的第一个元素,用于存放旧桶迁移后的目标新桶
x := &xy[0]
//x.b指向当前bucket在新桶的起始地址
x.b = (*bmap)(add(h.buckets, oldbucket*uintptr(t.bucketsize)))
//x.k指向新桶键数组的起始地址
x.k = add(unsafe.Pointer(x.b), dataOffset)
//x.e指向新桶值数组的起始地址
x.e = add(x.k, bucketCnt*uintptr(t.keysize))
//如果当前bucket不是等量扩容,即新桶的大小不等于旧桶的大小,则需要为y分配新桶
if !h.sameSizeGrow() {
//y指向xy数组的第二个元素,属于扩容后旧桶需要迁移到的第二个目标新桶
y := &xy[1]
//y.b指向当前bucket在新桶的起始地址
y.b = (*bmap)(add(h.buckets, (oldbucket+newbit)*uintptr(t.bucketsize)))
//y.k指向新桶键数组的起始地址
y.k = add(unsafe.Pointer(y.b), dataOffset)
//y.e指向新桶值数组的起始地址
y.e = add(y.k, bucketCnt*uintptr(t.keysize))
}
......
}
|
该代码块的目的是为了进行桶迁移操作前做的准备,迁移过程中数据会根据情况分流到不同桶中,而迁移前需要确立数据被分流到哪个桶,就是这步骤做的工作。而记录分流桶信息,保存分配上下文的则用的是 evacDst结构体,上面说的 x和 y桶,就是属于evacDst结构,他们并不是真正用来存储数据的桶,而是记录分配信息的用来。
来看evacDst结构:
1
2
3
4
5
6
|
type evacDst struct {
b *bmap // 表示目标桶的指针。在哈希表的扩容过程中,旧桶中的元素需要被迁移到对应的目标桶中。
i int // 表示目标桶中元素的索引位置。通过索引位置可以确定元素在目标桶中的存储位置。
k unsafe.Pointer // 表示键(key)的指针。在迁移过程中,需要将元素的键从旧桶复制到目标桶的相应位置。
e unsafe.Pointer // 表示值(value)的指针。在迁移过程中,需要将元素的值从旧桶复制到目标桶的相应位置。
}
|
这个结构体用于记录迁移目标的信息,方便进行元素的复制和存储操作。通过 evacDst 结构体的实例,可以知道元素应该被迁移到哪个目标桶的哪个索引位置,并且可以获取键和值的指针,实现迁移操作。
再来说说分桶的算法策略:
- 如果map等量扩容,那么旧桶与新桶之间是一对一的关系,所以只会初始化x记录桶信息,成为x桶;
- 如果map增量扩容,那么每个旧桶的元素会可能会分流到新创建的两个桶中,初始化x和y记录桶信息,成为x桶和y桶。
举个例子说明下这两种算法策略:
等量扩容:这个很好理解,假如扩容前该key所在的是1号桶,那么扩容后,该key在新桶的位置不变,也是1号桶。这个没啥好解释,就是所属桶的索引不变。
增量扩容:假如有个hash值尾号为:xxxx00,旧桶数量是4个,新桶数量就是8个。
那么之前获取桶索引的方式如下:
1
2
3
4
|
hash值: xxxx00
桶索引最大值3: & 11
----------------------
00
|
这样的话原本这个 hash值的 key 就会存储到 0 号桶,扩容后新桶树变成8,获取桶索引的方式如下:
1
2
3
4
|
hash值: xxxx00
桶索引最大值7: & 111
----------------------
x00
|
得到的值x00,具体到底哪个桶,取决于x值:
- 如果hash的末尾三位是 000 ,则与运算值为000 ,则分配到0号桶;
- 如果hash的末尾三位是 100 ,则与运算值为100 ,则分配到4号桶;
增量扩容的原理就是: 扩容后,由于容量翻倍 B 会 +1,在做与运算定位时候,就会多释放出一位掩码,与运算的结果除了多释放出的这一位,其余位应该和元本意义,而多释放出的这一位,会用来决定元素放在 x,还是 y。直观的表示如下图:
继续往下看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
|
//go 1.20.3 path: /src/runtime/map.go
func evacuate(t *maptype, h *hmap, oldbucket uintptr) {
......
if !evacuated(b) {
......
//遍历旧桶以及溢出桶的每个元素
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)) {
//获取当前元素的tophash
top := b.tophash[i]
//如果当前元素的tophash为empty,则将当前元素的tophash设置为evacuatedEmpty(已搬迁空元素)
if isEmpty(top) {
b.tophash[i] = evacuatedEmpty
continue
}
//如果当当前元素tophash小于minTopHash,则抛出异常
if top < minTopHash {
throw("bad map state")
}
k2 := k
//如果键是间接存储的,则获取键的实际指针
if t.indirectkey() {
k2 = *((*unsafe.Pointer)(k2))
}
// 定义一个变量,用来表示当前键值对应该迁移到哪个新桶(x或y)
var useY uint8
//如果当前map为增量扩容
if !h.sameSizeGrow() {
//获取当前元素的hash值
hash := t.hasher(k2, uintptr(h.hash0))
// 如果有迭代器正在遍历,并且键不是自反的,并且键不相等,就需要保持原来的新桶位置
if h.flags&iterator != 0 && !t.reflexivekey() && !t.key.equal(k2, k2) {
/**
有一个特殊情况: 有一种 key, 每次对它计算 hash, 得到的结果都不一样.
这个 key 就是 math.NaN() 的结果, 它的含义是 not a number, 类型是 float64.
当它作为 map 的 key时, 会遇到一个问题: 再次计算它的哈希值和它当初插入 map 时的计算出来的哈希值不一样
这个 key 是永远不会被 Get 操作获取的! 当使用 m[math.NaN()] 语句的时候, 是查不出来结果的,这个 key 只有在遍历整个 map 的时候, 才能被找到
并且, 可以向一个 map 插入多个数量的 math.NaN() 作为 key, 它们并不会被互相覆盖
当搬迁碰到 math.NaN() 的 key 时, 只通过 tophash 的最低位决定分配到 X part 还 Y part (如果扩容后是原来 buckets 数量的 2 倍).
如果 tophash 的最低位是 0, 分配到 X part; 如果是 1, 则分配到 Y part.
*/
//取原来的哈希值高8位的最低位作为新桶位置
useY = top & 1
//更新哈希值高8位
top = tophash(hash)
} else {
// 否则根据哈希值的最高位来确定新桶位置
if hash&newbit != 0 {
//如果最高位为1,就迁移到y桶
useY = 1
}
}
}
// 检查迁移标记是否合法
if evacuatedX+1 != evacuatedY || evacuatedX^1 != evacuatedY {
throw("bad evacuatedN")
}
// 将当前键值对标记为已迁移,并记录新桶位置
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.e = add(dst.k, bucketCnt*uintptr(t.keysize))
}
// 将当前键值对的哈希值高8位写入新桶中
dst.b.tophash[dst.i&(bucketCnt-1)] = top
// 将当前键复制到新桶中,如果是间接存储的话,就复制指针,否则就复制实际数据
if t.indirectkey() {
*(*unsafe.Pointer)(dst.k) = k2
} else {
typedmemmove(t.key, dst.k, k)
}
// 将当前元素复制到新桶中,如果是间接存储的话,就复制指针,否则就复制实际数据
if t.indirectelem() {
*(*unsafe.Pointer)(dst.e) = *(*unsafe.Pointer)(e)
} else {
typedmemmove(t.elem, dst.e, e)
}
// 更新新桶的地址和索引,准备下一次迁移
dst.i++
dst.k = add(dst.k, uintptr(t.keysize))
dst.e = add(dst.e, uintptr(t.elemsize))
}
}
// 如果没有协程在使用老的桶, 就对老的桶进行清理, 用于帮助gc
if h.flags&oldIterator == 0 && t.bucket.ptrdata != 0 {
//定义变量 b,指向旧桶数组中的指定旧桶(根据 oldbucket 计算得到)
//这里的 b 是私有局部变量. 要和循环当中的 b 区别开来
b := add(h.oldbuckets, oldbucket*uintptr(t.bucketsize))
// 定义变量 ptr,指向旧桶中键值对数据的起始位置(偏移 dataOffset)
ptr := add(b, dataOffset)
// 计算需要清零的字节数,即桶中键值对数据的总大小减去偏移 dataOffset
// 只清除bucket 的 key,value 部分, 保留 top hash 部分, 指示搬迁状态
n := uintptr(t.bucketsize) - dataOffset
// 使用 memclrHasPointers 函数将 ptr 指向的内存区域清零,该内存区域包含指针数据
memclrHasPointers(ptr, n)
}
}
// 更新搬移进度
if oldbucket == h.nevacuate {
advanceEvacuationMark(h, t, newbit)
}
}
|
这块代码主要流程为:
- 遍历旧桶中的每个键值对,进行迁移操作:
- 如果键值对的 tophash 为 evacuatedEmpty,表示该位置的键值对已被迁移,无需处理,继续下一个位置。
- 否则,获取键的指针 k 和元素的指针 e。
- 判断桶的类型 t 是否为间接键类型,如果是,则从指针 k 中获取实际键的指针。
- 根据哈希值计算新桶的索引,并确定新桶中的位置信息。
- 将旧桶中的键值对迁移到新桶中的对应位置,并更新迁移后的 tophash 值。
- 更新新桶中位置信息的计数器,并移动指针 k 和 e 到下一个位置。
- 迁移完成后,更新哈希表 h 的相关状态:
- 清空旧桶中的键值对数据。
- 更新桶的数量和溢出桶的数量。
- 如果存在额外的溢出桶链表,则将其更新到哈希表的 extra 字段。
runtime.evacuate最后会调用runtime.advanceEvacuationMark 增加哈希的 nevacuate 计数器并在所有的旧桶都被分流后清空哈希的 oldbuckets 和 oldoverflow:
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
|
//go 1.20.3 path: /src/runtime/map.go
// 更新搬移进度
func advanceEvacuationMark(h *hmap, t *maptype, newbit uintptr) {
// 搬迁桶的进度加一
h.nevacuate++
// 实验表明, 1024至少会比newbit高出一个数量级 (newbit代表扩容之前老的bucket个数).
// 所以, 用当前进度加上1024用于确保O(1)行为.
stop := h.nevacuate + 1024
if stop > newbit {
stop = newbit
}
//bucketEvacuated 内部通过判断 tophash 是否在迁移标示的范围:tophash[0] > emptyOne && tophash[0] < minTopHash,来确定是否已经迁移过了
for h.nevacuate != stop && bucketEvacuated(t, h, h.nevacuate) {
h.nevacuate++
}
// 这个等式成立,表明已全部迁移,可以清理旧数据了
if h.nevacuate == newbit {
h.oldbuckets = nil
if h.extra != nil {
// 释放掉溢出桶的指针
h.extra.oldoverflow = nil
}
h.flags &^= sameSizeGrow
}
}
|
至此搬迁工作完成,流程基本上注释很明了,不多说了。
简单总结一下哈希表扩容的设计和原理,哈希在存储元素过多时会触发扩容操作,每次都会将桶的数量翻倍,扩容过程不是原子的,而是通过 runtime.growWork增量触发的,在扩容期间访问哈希表时会使用旧桶,向哈希表写入/删除数据时会触发旧桶元素的分流。除了这种正常的扩容之外,为了解决大量写入、删除造成的内存泄漏问题,哈希引入了 sameSizeGrow 这一机制,在出现较多溢出桶时会整理哈希的内存减少空间的占用。
2.6 map的删除过程分析
如果想要删除哈希中的元素,就需要使用 Go 语言中的 delete 关键字,这个关键字的唯一作用就是将某一个键对应的元素从哈希表中删除,无论是该键对应的值是否存在,这个内建的函数都不会返回任何的结果。
在编译期间,delete 关键字会被转换成操作为 ODELETE 的节点,会将 ODELETE 节点转换成 runtime.mapdelete函数簇中的一个,包括 runtime.mapdelete、mapdelete_faststr、mapdelete_fast32 和 mapdelete_fast64:
1
2
3
4
5
|
//go 1.20.3 path: /src/cmd/compile/internal/typecheck/_builtin/runtime.go
func mapdelete(mapType *byte, hmap map[any]any, key *any)
func mapdelete_fast32(mapType *byte, hmap map[any]any, key uint32)
func mapdelete_fast64(mapType *byte, hmap map[any]any, key uint64)
func mapdelete_faststr(mapType *byte, hmap map[any]any, key string)
|
这些函数的实现其实差不多,这里挑选其中的 runtime.mapdelete分析一下。哈希表的删除逻辑与写入逻辑很相似,只是触发哈希的删除需要使用关键字,如果在删除期间遇到了哈希表的扩容,就会分流桶中的元素,分流结束之后会找到桶中的目标元素完成键值对的删除工作。
看下 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
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
|
//go 1.20.3 path: /src/runtime/map.go
func mapdelete(t *maptype, h *hmap, key unsafe.Pointer) {
......
//如果哈希表为空或者没有元素,直接返回
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值
hash := t.hasher(key, uintptr(h.hash0))
//开启写保护
h.flags ^= hashWriting
//通过与运算计算bucket索引
bucket := hash & bucketMask(h.B)
// 如果哈希表正在扩容状态,执行扩容操作,负责该桶搬迁工作
if h.growing() {
growWork(t, h, bucket)
}
//找到对应的桶指针地址(bmap结构体)
b := (*bmap)(add(h.buckets, bucket*uintptr(t.bucketsize)))
bOrig := b
//获取hash的tophash值(高8位)
top := tophash(hash)
search:
//遍历b桶以及溢出桶
for ; b != nil; b = b.overflow(t) {
//遍历该桶的每个元素
for i := uintptr(0); i < bucketCnt; i++ {
/**
槽点tophash值不等于要删除的tophash值,进行下面操作:
1. 如果当前tophash值为emptyRest,则表示后续都是空槽点,跳出搜索
2. 否则跳出本次搜索,进行下一个槽点搜索
*/
if b.tophash[i] != top {
if b.tophash[i] == emptyRest {
break search
}
continue
}
//走到这里说明 tophash 是匹配的,取出 key 看看,计算得到该key的指针地址
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
}
// 如果键是间接存储的,将指针置为nil,否则,如果值包含指针,清除内存
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))
// 如果值是间接存储的,将指针置为nil,否则,如果值包含指针,清除内存
if t.indirectelem() {
*(*unsafe.Pointer)(e) = nil
} else if t.elem.ptrdata != 0 {
memclrHasPointers(e, t.elem.size)
} else {
memclrNoHeapPointers(e, t.elem.size)
}
//将桶哈希值置为emptyOne,表示已删除
b.tophash[i] = emptyOne
// 判断是否是桶中最后一个元素
if i == bucketCnt-1 {
// 如果有溢出桶,并且溢出桶不为空,说明不是最后一个元素,跳转到notLast
if b.overflow(t) != nil && b.overflow(t).tophash[0] != emptyRest {
goto notLast
}
} else {
//如果后面还有元素,说明不是最后一个元素,跳转到notLast
if b.tophash[i+1] != emptyRest {
goto notLast
}
}
/**
到此流程,说明该槽位后续槽位也是emptyRset值
此处是将一堆emptyOne状态结束的桶的槽位值更改为emptyRest状态
跳出本循环的两种情况:
1. 遇到桶内的第一个 bucket. 注意: 桶实质上就是一个单向的链表.
2. 遇到 cell 的 tophash 非删除状态(emptyOne)
*/
for {
b.tophash[i] = emptyRest
// 如果是桶的第一个元素,并且不是原始桶,回退到上一个桶
if i == 0 {
if b == bOrig {
break
}
c := b
//获取当前 bucket 的前面的 prev bucket(即 prev bucket 的 overflow 是当前 bucket)
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--
// 如果哈希表为空,重新生成哈希种子
if h.count == 0 {
h.hash0 = fastrand()
}
break search
}
}
//再次判断写屏障
if h.flags&hashWriting == 0 {
throw("concurrent map writes")
}
//去除写保护
h.flags &^= hashWriting
}
|
这个函数的流程大致如下:
- 检查哈希表是否为空或者没有元素,如果是,直接返回。
- 检查哈希表是否正在被写入,如果是,报错并退出。
- 计算键的哈希值,并根据哈希值找到对应的桶。
- 检查哈希表是否正在扩容,如果是,执行扩容操作。
- 在桶中查找键值对,如果找到,删除它们,并更新桶的顶部哈希值。
- 更新哈希表的元素个数和哈希种子。
- 清除哈希表的写入标志位。
2.6 map的遍历过程分析
遍历的过程,就是按顺序遍历 bucket,同时按顺序遍历 bucket 中的 key。
map遍历是无序的,它并不按照存入先后输出,而是随机输出的,这是为什么呢?
这是因为 map 在扩容后,会发生 key 的搬迁,原来落在同一个 bucket 中的 key,搬迁后,可能会落到其它bucket中。这样,遍历 map 的结果就不可能按原来的顺序了。
所以在遍历 go 中的 map 时,并不是固定地从 0 号 bucket 开始遍历,每次都是从一个随机值序号的 bucket 开始遍历,并且是从这个 bucket 的一个随机序号的 cell 开始遍历。这样,即使是一个写死的 map,仅仅只是遍历它,也不太可能会返回一个固定序列的 key/value 对了。
示例:
1
2
3
4
5
6
|
func main() {
m := map[int]int{1: 1, 2: 2, 3: 3}
for k, v := range m {
fmt.Println(k, v)
}
}
|
反编译代码 go build -gcflags=-S ,得到汇编代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
main.main STEXT size=497 args=0x0 locals=0x178 funcid=0x0 align=0x0
0x0000 00000 TEXT main.main(SB), ABIInternal, $376-0
......
0x0113 00275 LEAQ type:map[int]int(SB), AX
0x011a 00282 LEAQ main..autotmp_12+224(SP), BX
0x0122 00290 LEAQ main..autotmp_9+272(SP), CX
0x012a 00298 PCDATA $1, $2
0x012a 00298 CALL runtime.mapiterinit(SB)
0x012f 00303 JMP 454
0x0134 00308 MOVQ main..autotmp_9+280(SP), DX
0x013c 00316 MOVQ (CX), AX
0x013f 00319 MOVQ (DX), CX
0x0142 00322 MOVQ CX, main.v+40(SP)
0x0147 00327 MOVUPS X15, main..autotmp_22+192(SP)
0x0150 00336 MOVUPS X15, main..autotmp_22+208(SP)
......
|
从汇编代码上看,是runtime.mapiterinit 的作用:
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
|
func mapiterinit(t *maptype, h *hmap, it *hiter) {
// 将迭代器的类型和哈希表指针赋值。
it.t = t
// 如果哈希表为空或者没有元素,直接返回。
if h == nil || h.count == 0 {
return
}
// 检查迭代器结构体的大小是否正确。
if unsafe.Sizeof(hiter{})/goarch.PtrSize != 12 {
throw("hash_iter size incorrect")
}
it.h = h
// 将迭代器的桶数和桶数组指针赋值。
it.B = h.B
it.buckets = h.buckets
// 如果桶结构体不包含指针,创建溢出桶。
if t.bucket.ptrdata == 0 {
h.createOverflow()
// 将迭代器的溢出桶和旧溢出桶指针赋值。
it.overflow = h.extra.overflow
it.oldoverflow = h.extra.oldoverflow
}
// 生成一个随机数,用于确定迭代器的起始桶和偏移量。
var r uintptr
if h.B > 31-bucketCntBits {
r = uintptr(fastrand64())
} else {
r = uintptr(fastrand())
}
// 根据随机数和哈希表的桶数,计算起始桶的索引。
it.startBucket = r & bucketMask(h.B)
// 根据随机数和每个桶的元素个数,计算偏移量。
it.offset = uint8(r >> h.B & (bucketCnt - 1))
// 将迭代器的当前桶赋值为起始桶。
it.bucket = it.startBucket
// 如果哈希表的标志位没有表示有迭代器或者有旧迭代器,将其设置为有迭代器和有旧迭代器。
if old := h.flags; old&(iterator|oldIterator) != iterator|oldIterator {
atomic.Or8(&h.flags, iterator|oldIterator)
}
// 调用mapiternext函数,开始迭代哈希表。
mapiternext(it)
}
|
在代码中,系统生成一个随机数,用于确定迭代器的起始桶和偏移量,就是这个随机数,让map变成了无序。那为什么明明逻辑上可以有序,却要加入随机数?
其实主要是因为 map 在扩容后,可能会将部分 key 移至新内存(新的bucket),那么这一部分key实际上就已经是无序的了。而遍历的过程,其实就是按顺序遍历内存地址,同时按顺序遍历内存地址中的 key。因为可能因扩容导致前后两次遍历的结果顺序不一致。所以GO开发者 才在源码中加上随机的元素,将遍历 map 的顺序随机化(无序),用来防止使用者遍历时产生有序的错觉(而这是有风险的代码,在GO 的严格语法规则下,是坚决不提倡的)。
2.7 Go 语言中的 Map 的底层实现简要总结
- Map 是 Go 语言中的一种数据结构,用于存储键值对。它提供了高效的查找、插入和删除操作。
- Map 的底层实现是一个哈希表(Hash Table),也被称为散列表。哈希表基于键来进行快速查找和存储。
- 哈希表由一个桶(Bucket)数组组成,每个桶存储一个或多个键值对。
- 在哈希表中,键通过哈希函数转换为桶的索引位置。哈希函数将键的内容映射为一个整数值,用于确定键值对在桶数组中的位置。
- 如果多个键映射到相同的桶索引位置,称为哈希冲突。为了解决冲突,每个桶中使用了一个链表或者平衡树来存储具有相同桶索引的键值对。
- 为了提高性能,在桶数组大小和键值对数量之间保持一个负载因子(Load Factor)的阈值。当负载因子超过阈值时,哈希表会进行扩容操作,重新分配更大的桶数组,以减少哈希冲突并保持高效性能。
- 扩容操作涉及到重新哈希,即重新计算所有键的哈希值和桶索引。这可能会导致整个哈希表的重建,因此在扩容过程中需要重新分配内存和迁移键值对。
- Map 的迭代顺序是随机的,不保证顺序稳定性。如果需要按照特定顺序迭代 Map,可以使用额外的数据结构(如 Slice)来保存键,并根据需要进行排序。
- 在并发环境下使用 Map 需要采取适当的同步措施,例如使用互斥锁(Mutex)来保护对 Map 的并发访问。
- 总的来说,Map 是一种高效的键值对存储结构,基于哈希表实现。它提供了快速的查找和插入操作,并可以自动扩容以适应键值对的增长。使用 Map 时需要注意并发访问的安全性,以及迭代顺序的不确定性。