【Go笔记】哈希表

简介

• map又称哈希表，是一种KV结构，分散存储在桶中
• 第一步计算键的哈希值，其结果与桶的数量无关
• 第二步通过取模得到下标
• 通常认为map是一种O(1)时间复杂度的操作，通过一个键快速查找到一个值

哈希碰撞与解决方法

• 哈希碰撞即不同的键通过哈希函数可能产生相同的哈希值，可能会导致同一个桶中可能存在多个元素
• 有两种主要策略可以避免哈希碰撞：拉链法以及开放寻址法

¶拉链法

• 即将同一个哈希桶（槽）中的元素通过链表的形式进行连接
• 最简单，最常用，可以不断链接新的元素，同时不用预先为元素分配内存
• 需要存储额外的指针用于链接元素，增加了哈希表的大小
• 链表存储的地址不连续，无法高效利用CPU的高速缓存
• 当哈希碰撞很频繁的时候，链表会变得很长，查找时间会也变得很长，平均获取时间会变成O(n)

¶开放寻址法

• 即在碰撞的时候通过某种方法寻找下一个可用的空位

• 查询的时候以相同的方式寻找，直到找到该空位

• Go中的哈希表采用的是优化的拉链法，每一个桶中存储了8个元素用于加速访问

特性

• Go允许值为nil的map进行访问，一定程度上减少了异常
• 使用delete(map, key)的操作时可以多次删除同一个值而不会报错

¶可以作为key的可比较的数据类型

• 一般数据类型 - bool, int, float, complex, string, pointer
• 特殊数据类型 - chan, interface, 相同结构的struct, 使用一般数据类型的数组

¶不可以作为key的数据类型

• 切片，函数，map

¶并发问题

• map不支持同时读+写、写+写
• map支持同时读+读
• 为了保障大多数场景下的查找效率，所以写操作与所有操作都互斥

哈希表的底层结构

• 先瞅瞅哈希表的定义结构

type hmap struct {
	count int // map中元素的数量
	flags uint8 // 当前map的状态，是否处于正在读写的状态
	B uint8 // 2的B次幂表示当前map中桶的数量
	noverflow uint16 // map中溢出桶的数量，当溢出数量太多的时候会进行same-size growth，避免内存泄露
	hash0 uint32 // 哈希种子
	buckets unsafe.Pointer // 指向当前map对应的首个桶的指针
	oldbuckets unsafe.Pointer // 扩容的时候临时存储旧桶的指正，扩容完毕后会清空
	nevacuate uintptr // 扩容时使用，标记当前旧桶中小于nevacuate的数据都转移到新桶中
	extra *mapextra // 存储溢出桶
}

• 两种扩容方式
• • 等量扩容（same-size growth）- 即不改变桶的大小，通过改变哈希种子来使得哈希分布更加均匀
• • 加倍扩容（double-size growth）- 力大砖飞，两倍桶
• 当一个桶中的链表长度超过8的时候，会新增一个溢出桶来存储溢出的数据，减少了rehash的次数
• 在代表桶的bmap结构在运行时只列出首个字段，一个固定长度为8的数组。此字段存储key哈希值的前8位
• 然后来看看桶的struct

type bmap struct {
	tophash [bucketCnt]uint8 // 存储哈希值，只存前八位
	key [bucketCnt]T // 存储key
	value [bucketCnt]T // 存储值
	overflow *bmap // 指向下一个溢出桶
	...
}

• 编译阶段确定了key, value以及桶的大小，因此运行时仅通过指针操作就可以找到特定位置的元素。桶在存储tophash后也会存储key数组和value数组
• hmap依靠B来计算桶的相对位置，然后通过buckets来确桶的内存地址

运行原理

• 将key和value分开存储是为了在字节对齐的时候压缩空间
• 如果初始化的map数量比较大，那么会提前创建好一些溢出桶存储在extra *mapextra中，这样使用溢出桶的时候就可以使用提前创建好的桶而不用再来申请内存空间
• 当发生一下两种情况的时候，map会进行重建
• • map超过了负载因子的大小
• • 溢出桶的数量过多，可能造成内存泄露
• • 负载因子 = 哈希表中元素数量 / 桶的数量
• 负载因子增大会意味着更多元素被分配到同一个桶中，效率会减慢
• Go中的负载因子为6.5，超过之后，会进行加倍扩容
• 删除操作和赋值操作类似，如果存在指定的key，那么就释放掉key和value引用的内存，然后在tophash中标注为emptyOne
• 删除操作之后，会检查当前删除的元素后面是否都为空，是则存储emptyRest，遇到的时候可以直接退出，省时间

具体实现细节

• 如果使用make()来初始化map，在类型检查阶段会将节点Op写成OMAKEMAP
• 如果make指定了长度，则会将长度常量值转为TINT，未指定长度则为nodintconst(0)
• 在遍历阶段，会执行runtime.makemap()或者runtime.makemap64()，保证map的长度不能超过int大小
• makemap函数会计算需要桶的数量2的B次幂
• makeBucketArray会给map申请内存，只有map的数量大于24，才会在初始化时生成溢出桶，大小为2的(b-4)次方，b为桶的大小。
• 啊如果内存已经被分配过了那就需要进行一个清空的操作，让GC来
• 如果采用了字面量初始化方式，其最终还是会被转化为make操作。其中，长度会被自动推断出来。如果长度小于25，那么就直接添加；如果长度大于25，新建两个数组循环添加
• 由于map的访问有一个返回值或者两个返回值两种形式，而Go没有函数重载的概念，因此在编译的时候就需要决定返回一个还是两个返回值。在AST阶段，若返回值为一个，Op操作则为OINDEXMAP，调用mapaccess1_XXX()；若为两个，则为OAS2MAPR，调用mapaccess2_XXX()。Go会根据key的不同选择不同种类的函数，但是在查找逻辑上都是相同的
• 采用hash & m方式来计算出key应该在哪个桶中，其实就是取模，然后计算出hash的前8位。
• 溢出桶以链表的形式延展
• 数据转移的时候遵循写时复制的规则，只有在真正赋值的时候才会选择是否进行数据转移
• 进行写时复制的时候，只转移当前需要的旧桶中的数据
• 在双倍重建中，两个新桶的距离总是与旧桶的数量值相等，相当于新桶穿插在旧桶之间
• 如果数据的hash & m值小于或等于旧桶的大小，那么此数据必须转移到旧桶位置完全相同的新桶上面去