按年被提到
20192020 · 2 次2026
算法与数据结构›哈希、压缩与向量化·arXiv:1910.06416 · cs.DS

RecSplit: Minimal Perfect Hashing via Recursive Splitting

RecSplit:基于递归切分的最小完美哈希
Emmanuel Esposito, Thomas Mueller Graf, Sebastiano Vigna · 2019

用递归切分构造最小完美哈希,每键约 1.56 比特

开始阅读 ↗PDFalphaXiv 讨论
被提及 · 3 人首次 2019-12-20 · 最近 2025-03-06
3不同的人
4活跃月份
4讨论串
30被引(OpenAlex)

论文提出 RecSplit,一种存储最小完美哈希函数的新技术,期望构造时间线性、期望查询时间为常数。它首次做到每个键约 1.56 比特(距离 1.44 比特的理论下界约 8.3%),每个键构造时间不到 2 毫秒;作者称其能同时在构造时间、空间和查询时间上优于此前约 2 比特每键的最先进结构,构造过程也易于并行,超出内存的数据可直接在外存上构建。

HN 为什么提它

HN 评论者提到它多为算法作者自己介绍或使用这一最小完美哈希方法,并引用其约 1.56 比特每键的空间效率。

方法难度 4 / 5约 50 分钟经得起时间
读之前最好知道
1哈希函数与完美哈希
2信息论下界(比特每键)
3算法复杂度分析
4递归与分治

HN 书评

推荐在前,同类按时间 · 每篇最多保留 20 条,统计用全部提及
引用thomasmg · 2019-12

“We used this for RecSplit: RecSplit”

说明自己把这个方法用在了 RecSplit 上
Xor Filters: Faster and Smaller Than Bloom Filters原评论 ↗
引用thomasmg · 2025-03

“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.”

介绍自己发明的 RecSplit,每个键约 1.56 比特
Succinct data structures原评论 ↗
被提交为 story · 2 次