PtrHash: Minimal Perfect Hashing at RAM Throughput
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915771878211584 |
|---|---|
| author | Koerkamp, Ragnar Groot |
| author_facet | Koerkamp, Ragnar Groot |
| contents | Given a set $K$ of $n$ keys, a minimal perfect hash function (MPHF) is a collision-free bijective map $\mathsf{H_{mphf}}$ from $K$ to $\{0, \dots, n-1\}$. This work presents a (minimal) perfect hash function that first prioritizes query throughput, while also allowing efficient construction for $10^9$ or more elements using 2.4 bits of memory per key.
Both PTHash and PHOBIC first map all $n$ keys to $n/λ< n$ buckets. Then, each bucket stores a pilot that controls the final hash value of the keys mapping to it. PtrHash builds on this by using 1) fixed-width (uncompressed) 8-bit pilots, 2) a construction algorithm similar to cuckoo-hashing to find suitable pilot values. Further, it 3) uses the same number of buckets and slots for each part, with 4) a single remap table to map intermediate positions $\geq n$ to $<n$, 5) encoded using per-cacheline Elias-Fano coding. Lastly, 6) PtrHash support streaming queries, where we use prefetching to answer a stream of multiple queries more efficiently than one-by-one processing.
With default parameters, PtrHash takes 2.0 bits per key. On 300 million string keys, PtrHash is as fast or faster to build than other MPHFs, and at least $2.1\times$ faster to query. When streaming multiple queries, this improves to $3.3\times$ speedup over the fastest alternative, while also being significantly faster to construct. When using $10^9$ integer keys instead, query times are as low as 12 ns/key when iterating in a for loop, or even down to 8 ns/key when using the streaming approach, just short of the 7.4 ns inverse throughput of random memory accesses. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_15539 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | PtrHash: Minimal Perfect Hashing at RAM Throughput Koerkamp, Ragnar Groot Data Structures and Algorithms F.2.2 Given a set $K$ of $n$ keys, a minimal perfect hash function (MPHF) is a collision-free bijective map $\mathsf{H_{mphf}}$ from $K$ to $\{0, \dots, n-1\}$. This work presents a (minimal) perfect hash function that first prioritizes query throughput, while also allowing efficient construction for $10^9$ or more elements using 2.4 bits of memory per key. Both PTHash and PHOBIC first map all $n$ keys to $n/λ< n$ buckets. Then, each bucket stores a pilot that controls the final hash value of the keys mapping to it. PtrHash builds on this by using 1) fixed-width (uncompressed) 8-bit pilots, 2) a construction algorithm similar to cuckoo-hashing to find suitable pilot values. Further, it 3) uses the same number of buckets and slots for each part, with 4) a single remap table to map intermediate positions $\geq n$ to $<n$, 5) encoded using per-cacheline Elias-Fano coding. Lastly, 6) PtrHash support streaming queries, where we use prefetching to answer a stream of multiple queries more efficiently than one-by-one processing. With default parameters, PtrHash takes 2.0 bits per key. On 300 million string keys, PtrHash is as fast or faster to build than other MPHFs, and at least $2.1\times$ faster to query. When streaming multiple queries, this improves to $3.3\times$ speedup over the fastest alternative, while also being significantly faster to construct. When using $10^9$ integer keys instead, query times are as low as 12 ns/key when iterating in a for loop, or even down to 8 ns/key when using the streaming approach, just short of the 7.4 ns inverse throughput of random memory accesses. |
| title | PtrHash: Minimal Perfect Hashing at RAM Throughput |
| topic | Data Structures and Algorithms F.2.2 |
| url | https://arxiv.org/abs/2502.15539 |