【go专家编程——常见数据结构map的实现原理】-EW帮帮网

1.特性速览

1.1 操作方式

初始化
- m := map[keyType]valueType{key1:value1}
- m := make(map[keyType]valueType,capSize)
增
- m["apple"] = "red"
删
- delete(m,"apple")
改
- m["apple"] = "a litter red"
查
- value,isExist = m["apple"]
len()函数可以查询map中键值对的个数

1.2 危险操作

并发读写
- map的操作不是原子的，多协程操作map时存在并发读写的风险。go在map的视线中增加了读写监测机制，一旦发现读写冲突立即触发panic，以免隐藏问题。
空map
- 向值为nil的map中添加元素会触发panic，在使用时需要避免

2.实现原理

2.1 数据结构

go中的map使用Hash表作为底层实现，一个Hash表里可以有多个bucket，而每个bucket保存了map中的一个或一组键值对。

2.1.1 map结构

type hmap struct{
	count	int	// 当前保存的元素个数
	B		uint // bucket 数组的大小
	buckets		unsafe.Pointer //bucket数组，数组的长度为2^B	
	oldbuckets	unsafe.Pointer //老旧bucket数组，用于扩容,大小为当前桶的一半，仅在映射扩容过程中非空。
	flags	uint8 // 存储映射的标志位信息，用于记录映射的各种状态，如是否为哈希冲突等。
	// 哈希种子，用于计算键的哈希值。
	hash0	uint32 
	// noverflow 记录大约的溢出桶数量；详细信息请参阅 incrnoverflow 方法。
	noverflow uint16 
	// nevacuate 用于记录疏散（evacuation，即重新分配）进度的计数器。小于这个值的桶已完成疏散。
	nevacuate uintptr   
	// extra     指向可选附加字段的指针，包含映射可能需要的额外信息。
	extra *mapextra 
}

2.1.2 bucket结构

type bmap struct{
	tophash [8]uint8	//存储hash值的高8位，每个bucket的容量为8
	data []byte		//key value数据:key/key/key/.../value/value/value...
	overflow *bmap	//指向下一个bucket，将所有冲突的键连接起来
}

data和overflow成员并没有在结构体中显式声明出来，运行时在访问bucket时直接通过指针的偏移来访问这些虚拟对象。

2.2 Hash冲突

当有两个或两个以上数量的键被“Hash”到了同一个bucket时，我们称这些键发生了冲突。Go使用链地址法来解决键冲突。
每个bucket可以存放8个键值对，当同一个bucket存放超过8个键值对时就会再创建一个bucket，用类似链表的方式将bucket连接起来。

2.3 负载因子

负载因子用于衡量一个Hash表冲突情况，公式为：
负载因子=键数量/bucket数量

负载因子过大过小都不理想
- 负载因子过小，说明空间利用率低
- 负载因子过大，说明冲突严重，存取效率低
当负载因子过大时会触发rehash
- Redis的map实现中负载因子大于1时就会触发rehash
- Go的map负载因子达到6.5时才会触发rehash

2.4 扩容

2.4.1 扩容条件

降低负载因子的常用手段是扩容，为了保证访问效率，当新元素将要添加进map时，都会检查是否需要扩容，扩容实际上是以空间换时间的手段。

触发扩容需要满足以下任意条件：

负载因子大于6.5
overflow的数量达到了 $2^{min(15,B)}$

2.4.2 增量扩容

当负载因子过大时，就新建一个bucket数组，新的bucket数组的长度是原来的2倍，然后将旧bucket中的数据搬迁到新的bucket数组中。
Go语言采用的是逐步搬迁策略，即每次访问map时都会触发一次搬迁，每次搬迁2个bucket
扩容时先让hmap数据结构中的oldbuckets成员指向原buckets数组
申请新的buckets数组（长度为原来的两倍），并将数组指针保存到hmap数据结构的buckets成员中
逐步搬迁
待oldbuckets数组中所有键值对搬迁完毕后，就可以安全地释放oldbuckets数组

2.4.3 等量扩容

所谓等量扩容，并不是扩大容量，bucket的数量不变，重新做一遍类似于增量扩容的搬迁动作，将单个bucket中松散的键值对重新排列一下，以使bucket的使用效率更高，进而保证更快的存取速度
在极端情况下，经过大量的元素增加删除，键值对刚好几种在一部分的bucket，overflow中的bucket大部分都为空，访问效率很差。
重新组织后，overflow的bucket数量会减少，既节省了空间，又提高了访问效率（这主要是因为删除元素后，这个链表不会进行自动重组，所以需要通过等量扩容的方式来）

2.5 增删改查

2.5.1 查询

根据key计算hash值
取hash值低位与hmap.B取模来确定bucket的位置
取hash值高位，在tophash数组中查询
如果tophash[i]中存储的hash值与当前key的hash值相等，ze获取tophash[i]的key值进行比较
如果在当前bucket中没有找到，则依次从溢出的bucket中查找

如果当前map处于搬迁过程中，则优先从oldbuckets数组中查找，在从buckets数组中查找。

查找不到返回相应的零值。

2.5.2 添加

根据key值计算hash值
取hash值低位与hmap.B取模来确定bucket的位置
查找该key是否存在，存在则直接更新值
不存在，则在该bucket中寻找空余位置并插入

如果当前map处于搬迁过程中，则新元素会直接添加到新的buckets数组中。

2.5.3 删除

删除元素实际上是先查找元素
如果元素存在则把元素从相应的bucket中清除

【go专家编程——常见数据结构map的实现原理】