Aug 21, 2020
8 分钟前阅读
哈希表用于保存键值对,通过哈希函数对键进行哈希之后,根据哈希值和表的大小求出存储值的位置。
由于哈希函数的选择,对于不同的键可能会出现哈希值相同的结果,而因为键不同不能对值进行覆盖,此时需要通过一些方式解决哈希冲突,常用方法包括分离链接法和开地寻
址法。
也称为拉链法,这种哈希表的结构,每个哈希值对应的位置都是一个链表,称为桶(bucket),对于哈希值相同的键值对,首先查询到桶的位置,然后遍历链表找到值相等的元素。
对于这种方法,如果桶容纳的元素过多,查找速度就会大幅下降。比如同样是 10000 个元素,平均分布在 1000 个桶里的查找速度是 10000 个桶的 1/10,但是即使如此查找速度也是线性表的 1000 倍。
开放地址法是指对于产生哈希冲突的键值对,我们要通过二次甚至多次的计算来得到一个新的位置存储键值对,对于表的大小要求比拉链法要高。
一般的公式为
$$ h_i(X) = (Hash(X) + F(i)) \mod TableSize $$
常用的选择探查函数的方法有:
Go map 采用了哈希表的方法来实现,并且采用拉链法解决冲突问题。
哈希表的结构采用 runtime.hmap
表示,表中的每个位置,也就是哈希桶采用 runtime.bmap
来表示。
对于 map 的详细介绍,可以去参考 draven 的文章 Go 语言设计与实现 - 3.3 哈希表
我们重点关注在哈希表中的几个字段:
这个字段表示的是 map 的大小,存储的是对数值,因为 map 的大小是按照二的倍数扩容的,即 $cap = 2^B$
这个字段用于标记哈希桶中存储元素 hash 的高 8 位,在没有元素时存储的是可能的标志值,用于表示桶或者位置的状态,对于 hash 小于 minTopHash
的哈希值,会加上 minTopHash
再存入 tophash
。
那么 tophash
对于 map 查找元素究竟有什么用?
我们参考 runtime.mapaccess1
,在访问 map 元素时就会使用这个函数(不使用 ok 断言),我们看它计算 hash 和查找元素的过程:
hash := t.hasher(key, uintptr(h.hash0))
m := bucketMask(h.B)
b := (*bmap)(add(h.buckets, (hash&m)*uintptr(t.bucketsize)))
这部分代码进行了 hash 运算和查找哈希桶的过程,通过 runtime.bucketMask
求出蒙版范围,然后对 hash 值截断,根据在表大小范围内的后 $2^B$ 位来选择桶。
通过 runtime.bucketmask
的源码我们可以了解到,它是通过把在 hmap.B
范围内的位置 1 来得到蒙版值。
同时这段也解释了为什么使用 bmap.tophash
可以区分同一个桶中的元素,因为在选择桶时不会参考高位,因此高位具有随机性。
接下来看如何寻找元素位置:
top := tophash(hash)
bucketloop:
for ; b != nil; b = b.overflow(t) {
for i := uintptr(0); i < bucketCnt; i++ {
if b.tophash[i] != top {
if b.tophash[i] == emptyRest {
break bucketloop
}
continue
}
k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
if t.indirectkey() {
k = *((*unsafe.Pointer)(k))
}
if t.key.equal(key, k) {
e := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize))
if t.indirectelem() {
e = *((*unsafe.Pointer)(e))
}
return e
}
}
}
return unsafe.Pointer(&zeroVal[0])
首先使用 runtime.tophash
计算 hash 的高 8 位,并且会对结果进行判断:
if top < minTopHash {
top += minTopHash
}
即排除掉标志值。
然后通过两层 for
循环,外层遍历当前桶和它的溢出桶(溢出桶机制可以参考 Go 语言设计与实现 - 3.3 哈希表 - 2 数据结构),内层的 for
循环先检查当前位置的 tophash
,通过标志数值可以判断桶是否为空,如果为空直接跳出所有循环返回零值,tophash
不匹配则进入下一次循环;tophash
匹配时才会对判断 key 是否匹配,并且还需要通过 t.indirectkey
检查键是否为引用。
t.indirectkey
如何工作?我们先查看 t.indirectkey
,这个方法通过位运算输出了 t.flags
的第一位,根据注释的提示我们去找到对应 flag 的含义。
if t.Key().Width > MAXKEYSIZE {
ot = duint8(lsym, ot, uint8(Widthptr))
flags |= 1 // indirect key
}
代码对键类型的大小判断,大于 MAXKEYSIZE
时就会使用引用存储键,并标志为 indirect key。
Go map 通过哈希表来实现,采用拉链法进行冲突解决。具体到寻址则是利用低位进行桶的选择,然后遍历桶进行键的查找,利用 hash 的高 8 位进行预匹配,加速了键的查找,并且利用标志位进一步减少多余操作。
Sharing is caring!