完美哈希的BDZ算法学习笔记

Querainy · 2020-12-26 21:45:31 · 个人记录

又是神仙东西（

cmph 600行实现把我看懵了（

BDZ Algorithm用来构造PHF(完美哈希函数)和MPHF(最小完美哈希函数)。思想非常简单，实现也可以非常简单，效率还很不错的东西。

论文(来自cmph)

我们假设要构造的完美哈希函数把n个key映射到0,...,m-1。

定义 :

hypergraph(超图) : 每条边连接不止两个点的图。

k-hypergraph : 每条边连接k个点的hypergraph。

r-partite hypergraph(r部超图) : 点集是r行m/r列，每条边在每行连接一个点的r-hypergraph。

BDZ求PHF分两步 : 建立一个无环的r-partite hypergraph(Mapping)，然后根据这个hypergraph进行hash(Assigning)。

因为分析和实践都表明，r=3时BDZ表现最好，所以我们以下默认r=3。

从PHF构造MPHF非常简单，把PHF搞出来然后计排离散化一下就好了，所以我们以下默认是做PHF而不是MPHF。

非常简单，我们用3个hash函数h_0, h_1, h_2分别把key映射到三行中的三个结点，然后使用(在3-hypergraph上的)拓扑排序看是否有环，有环就重来。这个拓扑排序是说一条边至少有一个端点度为1就可以删了。

这个拓扑序(删边的序列)我们留着，一会还有用。

如果不能拓扑排序，也就是有环的话，我们再随机三个hash函数，再来一遍。

这一步看起来非常奇怪，主要是为了期望线性的复杂度，也就是期望常数次的随机轮数。具体复杂度证明我实在看不下去，有兴趣可以自行阅读论文。

对于每个边，我们把它分配给它的端点之一，把那个点的编号作为这个边的hash值。因为不能有冲突，我们设一个vis[]记录每个点是否已经被分配了。

按什么顺序分配呢?这里用到了奇妙的拓扑序 : 因为每条边被删的时候同时会删至少一个点，如果我们按拓扑序倒着处理这些边，那么就能保证每条边的端点中至少还有删它的时候删掉的点没有被分配。这也是为什么要保证这个hypergraph无环。(可以用来做构造题?)

然后你发现r=2时这个无向图无环等价于是森林，所以r=2的情况跟你在树上直接分配本质相同......

然后你发现这东西跟Cuckoo Hash非常相似。

查询的时候，我们直接根据选的那三个hash函数，对要查的key找到对应的hypergraph中的边，然后看它对应的结点编号。非常简单。

分析和实践都表明，m=1.26n左右时BDZ表现最好。记得m要是3的倍数哦。

本来打算看看那个严格完美哈希的，结果看不动，于是先爬来填这个坑了。