跳到正文
研踪PaperTrail
← 研踪 PaperTrail

arXiv:2610.17833 · v4

PHastR: Faster Minimal Perfect Hashing with Rotated Layouts

首次提交 2026-10-13 14:51
版本更新 2026-11-17 13:55
雷达观测 2026-11-18 19:43
arXiv ↗PDF ↗

摘要

We present PHastR, a minimal perfect hash function of the PHast family. Like PHast+, the fast-to-build variant of PHast, PHastR finds feasible seeds with bit-parallel operations: its seeds move keys along rings of slots, and to evaluate the seeds of a bucket it cyclically shifts, for each key, a word recording which slots of its ring are used. Unlike PHast+, however, it is almost immune to self-collisions, which make two keys of a bucket collide for (almost) all its seeds: more than a third of the buckets bumped by PHast+ with wrapping and multiplier 3 contain one. With 8-bit seeds, PHastR uses 1.941.94 bits per key, essentially the same space as the best variant of PHast+ with wrapping, but it is built in 37%37\% of the time, and its queries are 34%34\% faster on 10910^9 keys, as it bumps 0.5%0.5\% of the keys instead of 3.9%3.9\%; they are faster also than those of PHast, which takes almost thirteen times as long to build, and than those of PtrHash, which uses more than one bit per key more. With a larger expected bucket size PHastR comes within 0.020.02 bits per key of the space of PHast, using 1.901.90 bits per key, and its queries are still about as fast. Its construction also scales better with the number of threads: with all the threads of a 96-core machine it is more than two and a half times faster than that of PHast+. An offline construction built PHastR on a trillion keys in 9.39.3 hours on a single machine. Finally, we argue that when each key can be placed only within a range of WW slots, every placement of nn random keys on nn slots, however found, must bump on large key sets a constant fraction of the keys: we derive an asymptotic lower bound of about 0.1/W0.1/W on the expected value of this fraction, and we prove that, in a Poisson model, the best placement bumps about 1/2W1/2W of the keys, which is about one tenth of the keys bumped by PHastR.

AI 论文解读

基于摘要 · 非全文审阅

此版本尚未生成 AI 解读。解读由后台任务生成并按论文版本保存,登录后共享已有结果。

版本差异

本站首次收录为 v4,暂无更早版本可对照。

观测到的版本

相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。

v4 · 2026-11-17 13:55 · 最新观测版本

PHastR: Faster Minimal Perfect Hashing with Rotated Layouts

We present PHastR, a minimal perfect hash function of the PHast family. Like PHast+, the fast-to-build variant of PHast, PHastR finds feasible seeds with bit-parallel operations: its seeds move keys along rings of slots, and to evaluate the seeds of a bucket it cyclically shifts, for each key, a word recording which slots of its ring are used. Unlike PHast+, however, it is almost immune to self-collisions, which make two keys of a bucket collide for (almost) all its seeds: more than a third of the buckets bumped by PHast+ with wrapping and multiplier 3 contain one. With 8-bit seeds, PHastR uses 1.941.94 bits per key, essentially the same space as the best variant of PHast+ with wrapping, but it is built in 37%37\% of the time, and its queries are 34%34\% faster on 10910^9 keys, as it bumps 0.5%0.5\% of the keys instead of 3.9%3.9\%; they are faster also than those of PHast, which takes almost thirteen times as long to build, and than those of PtrHash, which uses more than one bit per key more. With a larger expected bucket size PHastR comes within 0.020.02 bits per key of the space of PHast, using 1.901.90 bits per key, and its queries are still about as fast. Its construction also scales better with the number of threads: with all the threads of a 96-core machine it is more than two and a half times faster than that of PHast+. An offline construction built PHastR on a trillion keys in 9.39.3 hours on a single machine. Finally, we argue that when each key can be placed only within a range of WW slots, every placement of nn random keys on nn slots, however found, must bump on large key sets a constant fraction of the keys: we derive an asymptotic lower bound of about 0.1/W0.1/W on the expected value of this fraction, and we prove that, in a Poisson model, the best placement bumps about 1/2W1/2W of the keys, which is about one tenth of the keys bumped by PHastR.

查看此版本解读 →查看此版本原文 ↗