面试归纳：Go数据结构及Map底层实现

最近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访问

1. 计算桶号 key进行哈希计算，获得二进制哈希值，根据B获取哈希值的后B位（低位哈希值）即为桶号。
2. 取哈希值的高8位作为 tophash。
3. 在tophash的数组内进行匹配，如果没找到，则查看overflow是否为nil，若overflow不为空，则继续匹配，直到找到为止或者最终也未找到。如果找到了，也未必是我们想要的。因为存在哈希碰撞的情况，此时我们需要再次比较key值是否一致。如果key相同则匹配，如果不相同则继续在overflow寻找。

Map写入

1. 计算key值的哈希值获得桶号和tophash，在哈希桶查找tophash是否为空，如果为空且后面无数据，则该key不存在。直接将key-value放在该位置。
2. 如果匹配到相同的则看key是否相等，如果相等，直接更新value。
3. 如果未找到，则继续在tophash查找。如果找不到则在空位存放。

Map删除

1. 计算哈希值及tophash，查看是否存在，如果找到了，对比key，key一致则删除key-value。
2. 重置tophash

Map清空

1. new 一个新 map 会解除上一个map的引用，重新创建一个map，垃圾回收器会自动回收map。
2. 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之前可以更平滑的过渡。
扩容触发的条件

1. 达到最大负载因子（平均每个桶的key-value数量 >= 6.5）
2. 溢出桶数量太多（溢出桶超过普通桶）

map扩容类型

1. 等量扩容 数据不多但是溢出桶多，导致查询效率降低。重写计算哈希重新存放到桶内，偏空间整理
2. 翻倍扩容 数据量多

翻倍扩容步骤

扩容准备工作
a. 创建新的map
b. oldbuckets指向原来map地址
c. buckets指向新的map地址
d. 扩容结束前，访问读取oldbuckets内数据
e. map标记扩容状态

渐进式迁移数据
a. 所有数据存从旧桶渐进式迁移到新桶
b. 每次操作旧桶时，会将改动变更至新桶（桶被操作时，才会重新分配）
c. 迁移完成后，清除旧桶