Post

My secret 4th ALGO paper is out! We show a tight space lower on non-minimal k-perfect hash functions, generalize PtrHash into a non-minimal k-PHF, and then use it to develop a hash set implementation that is up to 1.6x faster than other hash sets! With Stefan {Hermann, Walzer} and Peter Sanders

arXiv cs.DS Data Structures and Algorithms@csds-bot.bsky.social

Ragnar Groot Koerkamp, Stefan Hermann, Peter Sanders, Stefan Walzer: Non-minimal k-perfect hashing: Tight lower bounds and an application to fast static hash tables https://arxiv.org/abs/2607.07257 https://arxiv.org/pdf/2607.07257 https://arxiv.org/html/2607.07257

Ragnar {Groot Koerkamp}

@curiouscoding.nl

9 July

Basically: given a set of keys, we can use a 1-PHF to map the keys to distinct slots in an array. Then store the key itself in that slot to have a single-cache-miss hash set. Our k-PHF hash set variant maps e.g. k=8 64-bit keys to a cache line, and then uses SIMD instructions to check if it's there

Ragnar {Groot Koerkamp}

@curiouscoding.nl

So now, a non-minimal 8-PHF suffices, which only needs 0.08 bits/key at load factor 80%, compared to 0.86 bits/key for k=1 at load factor 80% or 1.44 bits/key for k=1 and a minimal PHF with load factor 1. Since it's 10x smaller, it fits in a lower cache and supports faster queries or larger inputs.

9/7/26, 8:22 am0 reposts2 likes

Ragnar {Groot Koerkamp}

@curiouscoding.nl

9 July

The main k-PHF-set speedup figure, with our results in blue. On my laptop (top row), the k-PHF allows throughput very close to the maximal memory throughput up to n=2^28, whereas previous methods only reached that up to 2^24. Also, it performs equally well for both positive and negative queries.

Tim Fennell

@tfenne.bsky.social

9 July

This is amazing! It was quite literally on my list to go searching for a better/faster HashMap/HashSet for u64 keys today! Should I try it out yet, or wait for a 2.x release to crates.io?

Ragnar {Groot Koerkamp}

@curiouscoding.nl

9 July

Great! I haven't done much work on the API and docs yet, and in fact the StaticHashSet part of it is for now only really exposed/used in the static_hash_set/src/main.rs. Feel free to play around with it, but otherwise I'll get to it over the weekend. Note also that it's only optimized for sets atm

Ragnar {Groot Koerkamp}

@curiouscoding.nl

9 July

What exactly is the application? This stuff works best on pretty large sets with high throughput queries. The overhead of SIMD is kinda too large to make it performant without explicit prefetching.