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!