These are some thoughts on the Consensus-based MPHF presented in Lehmann et al. (2025), and how this could be applied to PtrHash:

Lehmann, Hans-Peter, Peter Sanders, Stefan Walzer, and Jonatan Ziegler. 2025. “Combined Search and Encoding for Seeds, with an Application to Minimal Perfect Hashing.” arXiv. https://doi.org/10.48550/ARXIV.2502.05613.

Below are also some thoughts on the papers on tiny pointers, used to achieve hash tables with load factors very close to 1: Bender et al. (2021), Farach-Colton, Krapivin, and Kuszmaul (2025).

1 Consensus Link to heading

Setting. Suppose we have n Bernoulli processes Bi, each with probability11

It is allowed for the success of Bi to depend on Bi with i<i; see appendix C. 

of success pi. For each Bi, we retry it until success at attempt Si{0,1,2,}.

Goal. Store all Si using minimal space.

Optimal. The optimal space to store some successful Si for each i is ilog2(1/pi) bits. And in expectation, we must do at least Ti=1/pi trials of experiment i.

Main result. The main result states that with ε bits per element extra, for total space Mopt+εn+O(logn), it is possible to encode seeds Si using in expectation O(Tiopt/ε) tries.

Method. Consider a bitstring of length j(ε+log2(1/pj)). As the seed Si, use the 64 bits ending at position Lj:=ji(ε+log2(1/pj)).

Then, seeds Si can be found using a greedy DFS. Suppose seeds have already been found up to Si1.

  1. Using the additional bits between Li1 and Li, find a seed for Bi.
  2. On success, move on to Bi+1.
  3. On failure, go back to Bi1, and search its next seed. If needed, move back up more.

1.1 Consensus-RecSplit Link to heading

The MPHF they introduce using consensus is rather pretty:

  1. Assume that n=2d. We will build a depth-d splitting tree.
  2. First find a seed S0 that splits the n keys into two sets.
  3. Then find seeds S0 and S1 that split the two sets equally into four sets.
  4. Repeat, until in the last level we find seeds S0,,S2d11 that slit each leaf of two keys into individual keys.

The beauty is now that we can use Consensus to compactly store the seeds in each level using only minimal overhead. And as it turns out, in the basis this construction is space-optimal, and the only overhead is in the ε we use to encode the seeds.

The only drawback is that this now requires looking up log2n seeds to look up a key.

A bucketed version reduces the height of the tree from O(log2n) to O(log2(1/ε)) by ‘merging’ the top layers into a single k-perfect hash function.

Result. The result is the first MPHF that can be constructed in time O(n/ε) rather than Ω(nexp(1/ε)).

Commentary. In a way, RecSplit and PTHash/PHOBIC/PtrHash are on opposite ends of a spectrum:

  • recsplit recursively splits the keys into equal halves, requiring logn lookups
  • PTHash and variants split the keys into n parts at once, requiring only a single lookup.

The benefit of the first approach is that it is much more balanced: at each point, the number of keys in each node is completely known, and searching for a successful seed to split into half is relatively easy.

For PTHash on the other hand, keys are necessarily distributed over buckets of distinct sizes, following some distribution. This requires processing buckets from large to small and/or using a load factor α<1.

2 IDEA: Consensus-PtrHash Link to heading

An example. As a slightly artificial application, suppose we have n keys ki that we want to hash into n slots. For the first key, the probability of hitting an empty slot is 1, so S0=0. For the second key, the probability of hitting an empty slot is p1=(n1)/n, and so S1 follows a geometric distribution with expected value n/(n1). Generally, Si has success probability pi=(ni)/n and follows a geometric distribution with mean n/(ni). Now we could simply write all Si back-to-back as, say, 64-bit integers, but this is inefficient.

Suppose for the moment that all Si are instead uniformly distributed between 0 and 1/pi, rather than geometric. Then we need log2(1/pi) bits to encode each Si, and it turns out that Mopt=ilog2(1/pi) bits is the optimal number of bits to encode some successful Si for each i.

New idea. instead of partitioning keys into buckets, we can directly assign each key a slice of, say, 16 bits in the output buffer of nlog2e+nε bits. Basically things work exactly as in the example, but instead of knowing that a key has ID i, we take x=h(k)/264 as the relative position, and let it use the bits at position (x+(1x)ln(1x))n(log2e+ε), which is the perfect bucket assignment function of PHOBIC (Hermann et al. 2024) and corresponds to the integral of 1/pi.

Compared to the current buckets of around λ=4 elements on average, in this new situation, each element gets 1.5 to 2 bits of its own on average. This should speed up construction, since effectively we now have more but smaller buckets, meaning that elements can be placed one-by-one instead of a full bucket at once. (Ie, instead of doing up to 256 tries to place 4 elements, we now do 4 times 4 tries to place one element at a time.)

A drawback of this approach is that one the one hand we want to choose seeds from left to right, while on the other hand we want to assign them from large buckets (dense regions) to small buckets (sparse regions). Probably a mix of both can work. Anyway because of the perfect bucket assignment function, the largest buckets will be at the start, and so going left to right should somewhat work. Still, it is to be expected that the distribution won’t be perfect for the small buckets towards the end, causing, say, 4 keys to map to the same bit position. One solution could be to add 8 buffer bits at the end of each cache line, so that dependencies never travel too far out. Then, we can again prioritize cache lines or bytes with a heavy load factor, and work outwards from those.

Either way, the hash-evict strategy as in PtrHash probably won’t work, since updating existing seed values in the middle of other things would throw off adjacent seeds as well.

Using the εn buffer. We can spread out the buffer bits in various ways:

  • ε bits per element, so that the dense region at the start relatively gets a lot of buffer;
  • or uniformly spread out over the output bits;
  • or a mix of the two.

Further strategies to increase the probability of success could be:

  • As before, use load factor α0.99<1.
  • We could find n elements in the most dense regions, and separately store their hash values in a hash table. This would add a second cache miss for each element though, to check whether the value is special.
  • We could also write 1111111 to any region that we failed to place, and then look it up in a fallback table.

3 Tiny pointers and optimal open addressing hash tables Link to heading

Tiny pointers are introduced in Bender et al. (2021) (hackernews). The core idea feels quite similar to most minimal perfect hashing algorithms: Instead of storing the hashed position of a key using logn bits of memory, it is sufficient to store only log1/δ bit tiny pointers (1δ is the load factor) and then look up keys using both the key and the tiny pointer.

The main data structures used to achieve these tiny pointers are:

  • load-balancing tables, that split the input into blocks of size b=δ2logδ1. Then a block is chosen at random via the key, and if possible, the key is inserted into an empty position in the block and that position is returned.
  • In case insertions fails, a sparsely filled power-of-two-choices table is used, with buckets of size loglogn.

In the end, they manage to get down to variable-width tiny pointers of average size O(1+logδ1).

Funnel hashing. In Farach-Colton, Krapivin, and Kuszmaul (2025) (quanta, hackernews, youtube) the authors introduce new hash tables that achieve significantly higher load factors than previously, using techniques similar to (but simpler than, IMO) tiny pointers. The simpler one is funnel hashing:

  1. Set the bucket size β=2logδ1.
  2. Create arrays A1,A2,, each of which is size a multiple of β, with |Ai+1|3/4|Ai|. Also keep a small separate A fallback array, so that the total size is n.
  3. To try insert a key into Ai, hash it into a bucket of Ai, and try to insert it.

To insert a key in the full data structure, try inserting into β random buckets of A1, then β random buckets of A2, and so on,

The main benefit of this recursive data structure is that Ai slowly fills, but once it is somewhat full, we start falling back to a much emptier Ai+1, so that insertions never get too hard. Also, this spreads the hardness of inserting into Ai over more keys, as all keys are tried against Ai before going to Ai+1.

TODO: Can we somehow make a smooth version of this? Where the load factor slowly decreases as a function of position in the original array, and we don’t need the explicit levels?

TODO: Can we somehow use this as the basis of an MPHF? It may be hard to use together with the consensus scheme, since we explicitly first want to try inserting into Ai before Ai+1, and having ‘‘random’’ high-order bits overlapping a previous Si may mess this up.

Elastic hashing is a variant that batches insertions and fills one layer at a time (and spilling to the next one). It uses some clever probing to trade searching in a nearly full Ai with easy options in a mostly empty Ai+1.

References Link to heading

Bender, Michael A., Alex Conway, Martín Farach-Colton, William Kuszmaul, and Guido Tagliavini. 2021. “Tiny Pointers.” arXiv. https://doi.org/10.48550/ARXIV.2111.12800.
Farach-Colton, Martin, Andrew Krapivin, and William Kuszmaul. 2025. “Optimal Bounds for Open Addressing without Reordering.” arXiv. https://doi.org/10.48550/ARXIV.2501.02305.
Hermann, Stefan, Hans-Peter Lehmann, Giulio Ermanno Pibiri, Peter Sanders, and Stefan Walzer. 2024. “Phobic: Perfect Hashing with Optimized Bucket Sizes and Interleaved Coding.” In 32Nd Annual European Symposium on Algorithms. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPICS.ESA.2024.69.
Lehmann, Hans-Peter, Peter Sanders, Stefan Walzer, and Jonatan Ziegler. 2025. “Combined Search and Encoding for Seeds, with an Application to Minimal Perfect Hashing.” arXiv. https://doi.org/10.48550/ARXIV.2502.05613.

  1. It is allowed for the success of Bi to depend on Bi with i<i; see appendix C. ↩︎