注：权作为学习笔记，基于version: 1.14
内容
一 map
1.1 数据结构
1.2 写入
1.3 查找
1.4 扩容
1.5 注意点
二 sync.map
2.1 基本使用
2.2 实现原理
一 map
1.1 数据结构
学习go中map的数据结构，可以对比着java中的hashmap实现来一起对比学习，java 中map是采用拉链罚来解决hash冲突，基本数据结构是数组+链表的hash表形式；而go map并没有采取这种形式，go中采取buckets的形式，每个bucket在固定了可以存储8对键/值，总体数据结构大体如下图这个样子：
image.png
源码长这个样子：
// src/runtime/map.go
type hmap struct {
count int /* Map中元素数量 */
flags int8 /* 相关标志位 */
B int8 /* （1<< B * 6.5）为最多元素的数量 ; 代表bucket的个数，不是直接B个桶，是当前map有2^B个桶；*/
noverflow int16 /* 溢出桶的数量 */
hash0 uint32 /* 哈希种子 */
buckets unsafe.Pointer /* 桶指针 */
oldbuckets unsafe.Pointer /* 桶指针（只有扩容的时候才使用，指向旧的桶） */
nevacuate uintptr /* 用于桶搬迁 */
extra *mapextra /* 当key/value非指针时使用 */
}
type mapextra struct {
overflow *[]*bmap /* 溢出桶的指针 */
oldoverflow *[]*bmap
nextOverflow *bmap
}
type bmap struct {
tophash [bucketCnt]uint8 /* bucketCnt=8，一个桶只能存放8对k/v, 低B位用来寻找桶，高8位用来寻找元素 */
}
/* 当kev/value不为指针时，溢出桶存放到mapextra结构中，overflow存放buckets中的溢出
桶，oldoverflow存放oldbuckets中的溢出桶，nextOverflow预分配溢出桶空间 */
type mapextra struct {
overflow *[]*bmap /* 以切片形式存放buckets中的每个溢出桶 */
oldoverflow *[]*bmap /* 以切片形式存放oldbuckets中的每个溢出桶*/
nextOverflow *bmap
}
/* map标志位 */
iterator 1 /* 迭代器buckets桶的标志位，为1表示正在使用buckets*/
oldIterator 2 /* 迭代器oldbuckets桶的标志位 ，为1表示正在使用oldbuckets*/
hashWriting 3 /* 并发写标志位，为1表示有goroutine正在写map */
sameSizeGrow 4 /* 等量扩容标志，表示申请的桶数量和原来一样 */
总体来说：
- go的map使用2^B个桶来装数据，每个桶固定存储8对键值对，每个bucket是一个bmap类型，bmap 结构体里有个字段tophash，是一个数组，这个数组存放了bmap里各个key的hash的前8位，用来快速对比key是否相等，如果一个key的前8位都不相等，就没有必要再往下对比了；
-
除了buckets， hmap还要个关键的东西，就是overflow，这个是一个bmap类型的指针数组，存放的是指向溢出桶的指针；溢出桶是用来存放，当一个key hash 后，用key hash的后B位计算出在那个桶，然后遍历桶是否有空位置，如果当前桶没有空位置了，那么会在当前桶后面连续的内存位置开辟一个新 bucket来存放，这个新的bucket就是溢出桶
类似这样的结构：
image.png
1.2 写入
put的大体步骤是：
- 1 根据key 计算hash值
- 2 根据B的值，得到key hash值的后B位，这个就是会存于那个桶
- 3 遍历桶，找到一个空位置，然后存入到空位置；
- 4 如果当前桶全满，如果有溢出桶，则遍历溢出桶，存到溢出桶的空位置；如果没有溢出桶则新建一个溢出桶存放key
1.3 查找
查找和写入步骤很类似，查找时会利用 bmap的tophash快速对比，如果key的前8位和和tophash里的值都不一样，那证明不在当前桶，可能在溢出桶里，加快遍历速度
1.4 扩容
当满足一下任何一个条件时，会发生扩容：
- 1 装载因子>6.5时，hmap中元素太多了；其中，装载因子=count/2^B
- 2 hmap中溢出桶太多了，当 B 小于 15，也就是 bucket 总数 2^B 小于 2^15 时，如果 overflow 的 bucket 数量超过 2^B；当 B >= 15，也就是 bucket 总数 2^B 大于等于 2^15，如果 overflow 的 bucket 数量超过 2^15。
扩容方式： - 1 溢出桶太多，即上述条件2，此时是 等量扩容， 即整理桶中个数据，将分散的数据进行搬移整理到一块；
- 2 当装载因子>6.6, 增量扩容（2倍扩容）；
1.5 注意点
- 1 go map不是并发安全的
- 2 如果只是声明了map, 而没有初始化，是不能直接添加值的; 要区别slice， 如果声明一个slice, 是直接可以使用append添加元素的;
var map1 map[string]int
map1["ss"] = 1 // 直接panic, map1是nil
二 sync.map
map是非线程安全的，在go中如果想用线程安全的map, 一般有两种方式：
- 1 自己构造一个struct, struct里放一个RWMutex， 读时加读锁，写时加写锁, 类似这样的：
type SyncMap struct {
sync.RWMutex
m map[string]string
}
- 2 sync包下面的sync.map
2.1 基本使用
func main(){
var sm sync.Map
// 写入
sm.Store("a", 1)
sm.Store("b", 2)
sm.Store("c", 3)
// 取出
v, _ := sm.Load("a")
fmt.Println(v.(int))
// 删除
sm.Delete("b")
// 存在则获取 不存在则添加
sm.LoadOrStore("d", 4)
// 遍历
sm.Range(func(key, value interface{}) bool {
fmt.Println(key.(string), value.(int))
return true
})
}
2.2 基本原理
基本数据结构如下：
type Map struct {
mu Mutex
read atomic.Value // readOnly
dirty map[interface{}]*entry
misses int
}
type readOnly struct {
m map[interface{}]*entry
amended bool // true if the dirty map contains some key not in m.
}
- 关键的字段是：read和dirty， read属性是atomic.Value(原子的更新复杂类型，可以看做一个容器)，本质存储的是readOnly 结构体，可见read和dirty结构体都是一个简单的map，
- 通过一种空间换时间，通过双份的map来实现读不加锁，写加锁的思路进行优化
- read和dirty的map的value都是指向同一份的指针，所以双份的map的存储在空间上也做了很好的优化
- sync.map适合并发读多写少的场景，如果并发写远远大于并发读，第一种加读写锁的并发模式的速度要更好一些
详细理解：
- 深度解密Go语言之sync.map： https://qcrao.com/2020/05/06/dive-into-go-sync-map/
- 由浅入深聊聊Golang的sync.Map ：https://juejin.im/post/6844903895227957262#heading-4
引用：
1 Golang之Map源码解析：https://www.jianshu.com/p/17f49e562f7b
2 大话图解golang map https://studygolang.com/articles/21047?fr=sidebar
3 《go 语言设计与实现》
网友评论