最近gap期，温故而知新，也是怕技术相关的慢慢生疏。结合近期面试的题目，整理学习的过程中，沉淀成文档，供大家交流。 From Moic
GoLang 数据结构
golang数据结构有很多种，分为三类基础数据类型，复合数据类型，其他数据类型。
基础数据类型
| Name | Type |
|---|---|
| 整数 | int, int8, int16, int32, int64, uint, uint8, uint16, uint32, uint64 |
| 浮点数 | float32, float64 |
| 复数 | complex64, complex128 |
| 布尔 | bool |
| 字符串 | string |
| 字符 | rune |
复合数据类型
| Name | Type | Init | More |
|---|---|---|---|
| 数组 | Array | var arr [3]int | 固定大小的元素序列 |
| 切片 | Slice | var slice []int | 动态大小的可以改变的序列 |
| 映射 | Map | var mp map[int]string | 无序的键值对集合 |
| 结构体 | Struct | type Item Struct { Name string} |
自定义的复合数据类型，可以包含不同类型字段 |
| 通道 | Channel | ch := make(chan int) | 用于在不同goroutine之间传输数据的通信机制 |
其他数据类型
| Name | Type | Example | More |
|---|---|---|---|
| 函数 | Function | func increase(a int) int { return a+1} | 可作为参数传递给其他函数 |
| 接口 | Interface | type Apple interface { Sum() int } | 用于定义方法集合，实现了这些方法集合的类型为该接口的实现 |
| 指针 | Pointer | var x int, ptr := &x | 用于存储变量的内存地址 |
Map的底层实现
Map底层结构
map的底层本质上是一个hmap类型的指针，通过哈希表进行存储键值对。哈希表有两种实现方式，开放寻址法和拉链法。golang map 使用的是拉链法。
golang map 的实现是在 runtime 下的 map.go
以下代码使用的 go version go1.17.6
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 // # live cells == size of map. Must be first (used by len() builtin)
flags uint8
B uint8 // log_2 of # of buckets (can hold up to loadFactor * 2^B items)
noverflow uint16 // approximate number of overflow buckets; see incrnoverflow for details
hash0 uint32 // hash seed
buckets unsafe.Pointer // array of 2^B Buckets. may be nil if count==0.
oldbuckets unsafe.Pointer // previous bucket array of half the size, non-nil only when growing
nevacuate uintptr // progress counter for evacuation (buckets less than this have been evacuated)
extra *mapextra // optional fields
}
image.png
由上图可以直观看到
map的底层是hmap结构体，其中包含很多字段，B代表buckets数组长度为2^B次方。数组中每个都是bmap的哈希桶。哈希桶包含四个字段tophash， keys，elems，overflow都是大小为8的数组。tophash 存放哈希值的最高字节，keys存放键，elems存放数据，overflow存放下一个溢出桶地址。
B<=4时，会创建溢出桶。go语言的键值对不是放在一起的，键八对放在一起，值八对放在一起，键值分开存放，因为如果放在一起可能需要内存空间对齐，会导致内存浪费。分开放更紧凑，也不会造成性能损失。
Map访问
- 计算桶号 key进行哈希计算，获得二进制哈希值，根据B获取哈希值的后B位（低位哈希值）即为桶号。
- 取哈希值的高8位作为 tophash。
- 在tophash的数组内进行匹配，如果没找到，则查看overflow是否为nil，若overflow不为空，则继续匹配，直到找到为止或者最终也未找到。如果找到了，也未必是我们想要的。因为存在哈希碰撞的情况，此时我们需要再次比较key值是否一致。如果key相同则匹配，如果不相同则继续在overflow寻找。
Map写入
- 计算key值的哈希值获得桶号和tophash，在哈希桶查找tophash是否为空，如果为空且后面无数据，则该key不存在。直接将key-value放在该位置。
- 如果匹配到相同的则看key是否相等，如果相等，直接更新value。
- 如果未找到，则继续在tophash查找。如果找不到则在空位存放。
Map删除
- 计算哈希值及tophash，查看是否存在，如果找到了，对比key，key一致则删除key-value。
- 重置tophash
Map清空
- new 一个新 map 会解除上一个map的引用，重新创建一个map，垃圾回收器会自动回收map。
- for range 一个个删除 go 编译器进行优化，调用mapclear函数。
两者相比，for range 更快。
Map扩容
为什么扩容？
使用时，空间不足，就需要扩容。
扩容比例
根据go版本不同 go1.17扩容规则为
在go1.18之前有一个临界值为1024，小于1024的时候，切片先两倍扩容，如果两倍扩容后的容量还是不够，就直接以切片需要的容量作为容量。
在go1.18之后，临界值换成了256，小于256和前面相同，大于256公式变为（oldcap+3*256）/4这个公式的值随着oldcap的越来越大，从2一直接近1.25，相对于1.18之前可以更平滑的过渡。
扩容触发的条件
- 达到最大负载因子（平均每个桶的key-value数量 >= 6.5）
- 溢出桶数量太多（溢出桶超过普通桶）
map扩容类型
- 等量扩容 数据不多但是溢出桶多，导致查询效率降低。重写计算哈希重新存放到桶内，偏空间整理
- 翻倍扩容 数据量多
翻倍扩容步骤
扩容准备工作
a. 创建新的map
b. oldbuckets指向原来map地址
c. buckets指向新的map地址
d. 扩容结束前，访问读取oldbuckets内数据
e. map标记扩容状态
渐进式迁移数据
a. 所有数据存从旧桶渐进式迁移到新桶
b. 每次操作旧桶时，会将改动变更至新桶（桶被操作时，才会重新分配）
c. 迁移完成后，清除旧桶
网友评论