PHastR: Faster Minimal Perfect Hashing with Rotated Layouts

arXiv:2610.17833 · cs.DS · Submitted 2026-10-13 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.

Tom: We're looking at the paper: "PHastR: Faster Minimal Perfect Hashing with Rotated Layouts".

Title and authors: Tom: So we’ve been talking about how PHastR does things differently under the hood, focusing on those layout selections and rotations to reduce collisions. Now let's just get a handle on what this paper actually calls PHastR: Faster Minimal Perfect Hashing with Rotated Layouts.

Jane: Right, so they're basically presenting this new minimal perfect hashing function that they call PHastR, and the title tells you it’s faster to build and query because of these layout rotations.

Lu: They are looking at how this new design fits into the existing minimal perfect hashing family, showing it's an improvement over PHast+ when we talk about construction speed.

Meng: It seems like the core idea is that they're trying to get a structure that’s fast to build and fast to search without sacrificing the minimal space requirements of a perfect hash function.

Lalam: They are specifically focusing on how this new design fits into the existing minimal perfect hashing family, showing it's an improvement over PHast+ when we talk about construction speed.

Tom: Exactly, and what’s interesting is that they used bit-parallel operations to find feasible seeds using a method involving cyclic shifting for each key to see which slots are used on its ring.

Jane: That sounds like they’re making the process of finding a good seed much quicker than trying every single option one by one, which is what you usually have to do with older methods.

The paper's summary: Tom: So we know they have the construction and query speed benefits from those rotations, but what are the main technical improvements they introduced beyond just that collision reduction?

Jane: They really focused on making the construction process more efficient and robust, specifically by introducing an offline construction method where you only read your keys once during the whole build process.

Lu: That offline part is a big deal for building these structures with millions of items because it cuts down the time needed substantially compared to an in-memory build.

Meng: Building something with millions of items can take forever on a single machine, so if this construction method makes that time much shorter, that’s something we need to talk about for deployment.

Tom: The paper shows they parallelized the construction by splitting the input data into batches for different threads so they can all compute hashes simultaneously.

Jane: Parallel construction is definitely good for build speed during creation, but I still have to ask about deployment because I don't know if this complexity translates well to a production environment with lots of variety.

Lu: They also showed that they can find those good rotations without checking every single one individually by using bitwise OR operations on consecutive bits to find free rotations.

Meng: That sounds like they’ve found a smart way to filter out bad options before even trying them all, which is useful, but I still have to ask about the cost of running this structure at scale.

Tom: The main result they highlight is the query time improvement itself when you look at eight bit seeds. They claim PHastR bumps about one point five percent of keys when you search it compared to nearly four percent with PHast+ with wrapping and multiplier three.

Jane: That means for a user running this structure, the lookup speed gets noticeably quicker as your data set grows because those collisions are way less frequent than they used to be.

The paper's improvements: Tom: So we’ve covered that PHastR uses layout selection and rotation to make construction faster and queries quicker, but what are the specific ways they improved the system beyond just that collision reduction?

Jane: They introduced this offline construction method which is a big deal for building things on large datasets because you only read your keys once during the whole process, and it needs less than half a byte per key of memory compared to a standard in-memory build.

Lu: That’s significant because building these structures with millions of items can take forever, and this construction method cuts that time down substantially. Plus, they parallelized the construction by splitting the input data into batches for different threads so they can all compute hashes at the same time.

Meng: Parallel construction is good for build speed during creation, but I still have to ask about deployment because I don't know if this complexity translates well to a production environment with lots of variety.

Tom: The main result they focus on is the query time improvement itself when you look at eight bit seeds, where PHastR bumps about one point five percent of the keys when you search it compared to nearly four percent with PHast+ with wrapping and multiplier three.

Lu: They also showed that they can find those good rotations without checking every single one individually by using bitwise OR operations on consecutive bits to obtain L/T bits whose zeros are the free rotations, which map every key to a free slot unless two keys of the bucket are mapped to the same slot, which is rare.

Meng: That sounds like they’ve found a smart way to filter out bad options before even trying them all, but what about the cost of running this structure at scale? Does it still have any significant overhead when you try to deploy it in a real system?

Conclusion: Tom: So to wrap up, PHastR is a minimal perfect hashing structure that uses layout selection and rotation to make construction faster and queries quicker than previous methods in this paper, "PHastR: Faster Minimal Perfect Hashing with Rotated Layouts".

Jane: Right, it’s about taking the speed from one area and applying it to another by choosing independent layouts for seeds instead of relying on a single displacement mechanism.

Lu: The big picture here is that we can achieve practical speed improvements in minimal perfect hashing without having to rely on those more complex, slower techniques from PHast+ with wrapping.

Meng: For deployment at scale, this means faster build times and better query performance for systems handling millions of items.

Lalam: I’m confident in this result. The structure is mathematically sound and the performance gains over the baseline PHast plus with wrapping are backed by concrete numbers.

Tom: It's a solid step forward for anyone building large data structures that need fast lookups and construction times while keeping the memory footprint similar to what we already had.

Jane: It shows how careful design choices in seed selection can lead to tangible performance gains in real applications when you're dealing with massive key sets.

Lu: The direction they’re going is moving away from simple displacement in systems like PHast+ and toward more complex layout selection combined with rotation for better collision resistance.

Meng: If this approach can be generalized beyond just minimal perfect hashing, it could impact how we structure other complex data access patterns in large systems.

Tom: Well said. It’s a very balanced improvement for practical speed because they got better construction speed and query performance while keeping the memory footprint similar to what we already had.

Jane: So to summarize, PHastR is a new minimal perfect hashing structure that uses layout selection and rotation to nearly eliminate collisions.

Lu: We’ll keep an eye on how these layout and rotation ideas can be applied to other hashing families moving forward, like bucket placement algorithms.

Dipartimento di Informatica, Università degli Studi di Milano

cs.DS

Submitted: 2026-10-13

Updated: 2026-11-17

Code: https://github.com/vigna/phastr-bench

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Importance score: 100/100

The gist: PHastR presents a minimal perfect hash function that achieves faster construction and queries than PHast+ with wrapping and outperforms PHast in several aspects The main goal of these constructions…

Key concepts

PHastR Architecture
PHastR selects a seed using its lowest bits to choose one of several independent layouts for key placement. The higher bits then determine a single rotation applied uniformly across all keys in that layout's bucket. This combination makes the structure robust against self-collisions.
Self-Collision Immunity
The design aims to make self-collisions rare by having collisions happen independently within each chosen layout. Two keys only collide for almost all seeds if they collide in every single layout, which is highly improbable given the varied layouts.
Bitwise OR for Free Rotations
The method uses bitwise OR operations on consecutive bits of a row to identify specific bits that represent free rotations. These free rotations are guaranteed to map every key into an available slot, unless a rare collision occurs within that specific layout.

Terminology

Summary

PHastR presents a minimal perfect hash function that achieves faster construction and queries than PHast+ with wrapping and outperforms PHast in several aspects The main goal of these constructions is not to approach the lower bound, as those based on recursive splitting do at the price of slower queries but to obtain a practical structure that answers a query with close to one memory access on average

PHastR Architecture and Comparison

PHastR lies between PHast and PHast+ by using two parts in its seed selection: the lowest bits choose one of a few independent layouts, while the remaining bits choose a rotation that moves all keys of a bucket by the same amount This design makes it almost immune to self-collisions, which significantly reduces bumping compared to PHast+ with wrapping With 8-bit seeds, PHastR uses 1.

Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.

Improvements for AI systems

  1. Search for feasible seeds using bit-parallel operations to find all rotations of a layout that map no key to a used slot by cyclically shifting, for each key, the bits recording which slots of its ring are used. This allows evaluation of all rotations at once, as in PHast+.

  2. Implement an offline construction that reads the keys just once and needs less than half a byte per key of memory on large key sets. This construction builds the same structure as the one built in memory.

  3. Design a structure where self-collisions happen independently in each layout, making two keys collide for (almost) all seeds only if they do so in every layout, which is very unlikely. This makes PHastR bump far fewer keys than PHast+.

  4. Implement a placement scheme where the lowest bits of a seed choose one of a few independent layouts, and the remaining bits choose a rotation, which moves all the keys of the bucket by the same amount along their rings of slots.

  5. Utilize bitwise OR operations on L/T consecutive bits of a row to obtain L/T bits whose zeros are the free rotations, which map every key to a free slot. This yields feasible seeds unless two keys of the bucket are mapped to the same slot, which is rare.

  6. Use grouping and scheduling by splitting input into batches for each thread, where each thread computes hashes of its batch and appends them to a region associated with the batch and part. This allows parallel construction with efficient memory access patterns.

  7. Leverage the asymptotic lower bound of about 0.1/W on the expected value of bumped keys, proving that in a Poisson model, the best placement bumps about 1/2W of the keys. This quantifies why no search can produce a first level free of bumping on large key sets.

Sources

Related papers