← 研踪 PaperTrailarXiv: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
摘要
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 bits per key, essentially the same space as the best variant of PHast+ with wrapping, but it is built in of the time, and its queries are faster on keys, as it bumps of the keys instead of ; 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 bits per key of the space of PHast, using 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 hours on a single machine. Finally, we argue that when each key can be placed only within a range of slots, every placement of random keys on slots, however found, must bump on large key sets a constant fraction of the keys: we derive an asymptotic lower bound of about on the expected value of this fraction, and we prove that, in a Poisson model, the best placement bumps about of the keys, which is about one tenth of the keys bumped by PHastR.
观测到的版本
相邻记录可能跳过中间版本;首次发现 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 bits per key, essentially the same space as the best variant of PHast+ with wrapping, but it is built in of the time, and its queries are faster on keys, as it bumps of the keys instead of ; 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 bits per key of the space of PHast, using 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 hours on a single machine. Finally, we argue that when each key can be placed only within a range of slots, every placement of random keys on slots, however found, must bump on large key sets a constant fraction of the keys: we derive an asymptotic lower bound of about on the expected value of this fraction, and we prove that, in a Poisson model, the best placement bumps about of the keys, which is about one tenth of the keys bumped by PHastR.
查看此版本解读 →查看此版本原文 ↗