引用thomasmg · 2019-12
“We used this for RecSplit: RecSplit”
说明自己把这个方法用在了 RecSplit 上
用递归切分构造最小完美哈希,每键约 1.56 比特
论文提出 RecSplit,一种存储最小完美哈希函数的新技术,期望构造时间线性、期望查询时间为常数。它首次做到每个键约 1.56 比特(距离 1.44 比特的理论下界约 8.3%),每个键构造时间不到 2 毫秒;作者称其能同时在构造时间、空间和查询时间上优于此前约 2 比特每键的最先进结构,构造过程也易于并行,超出内存的数据可直接在外存上构建。
HN 评论者提到它多为算法作者自己介绍或使用这一最小完美哈希方法,并引用其约 1.56 比特每键的空间效率。
“We used this for RecSplit: RecSplit”
“Together with his student (I also helped a bit), he wrote a paper about RecSplit, a minimal perfect hash function (MPHF) algorithm I have invented: RecSplit - that algorithm uses around 1.56 bits per key.”