Hash

Go Map 如何使用哈希值来寻址

基本概念 哈希表 哈希表用于保存键值对,通过哈希函数对键进行哈希之后,根据哈希值和表的大小求出存储值的位置。 哈希冲突 由于哈希函数的选择,对于不同的键可能会出现哈希值相同的结果,而因为键不同不能对值进行覆盖,此时需要通过一些方式解决哈希冲突,常用方法包括分离链接法和开地寻 址法。 分离链接法 也称为拉链法,这种哈希表的结构,每个哈希值对应的位置都是一个链表,称为桶(bucket),对于哈希值相同的键值对,首先查询到桶的位置,然后遍历链表找到值相等的元素。 对于这种方法,如果桶容纳的元素过多,查找速度就会大幅下降。比如同样是 10000 个元素,平均分布在 1000 个桶里的查找速度是 10000 个桶的 1/10,但是即使如此查找速度也是线性表的 1000 倍。 开放地址法 开放地址法是指对于产生哈希冲突的键值对,我们要通过二次甚至多次的计算来得到一个新的位置存储键值对,对于表的大小要求比拉链法要高。 一般的公式为 $$ h_i(X) = (Hash(X) + F(i)) \mod TableSize $$ $X$ 键 $i$ 多次探查的次数 $Hash(x)$ 哈希函数 $F(i)$ 探查函数,与寻址次数相关 常用的选择探查函数的方法有: 线性探查法 平方探查法 双散列 Go map 的实现 Go map 采用了哈希表的方法来实现,并且采用拉链法解决冲突问题。 哈希表的结构采用 runtime.hmap 表示,表中的每个位置,也就是哈希桶采用 runtime.bmap 来表示。 对于 map 的详细介绍,可以去参考 draven 的文章 Go 语言设计与实现 - 3.3 哈希表 我们重点关注在哈希表中的几个字段: hmap.B 这个字段表示的是 map 的大小,存储的是对数值,因为 map 的大小是按照二的倍数扩容的,即 $cap = 2^B$