MultiTable: A Faster Hash Table at any Physical Load Factor up to and Including One
Abstract
We present \emph{multitable} and its Rust reference implementation: a stable hash table both materially faster at equal physical memory and more flexible than the SwissTable in its Rust's hashbrown implementation. As an arithmetic mean over 84 configurations it delivers 2.1× hashbrown's throughput when both hash the same raw bytes and 1.9× when hashbrown is keyed on native integers, its best case; on negative lookups alone, 3.2× and 2.9×. Multitable reaches \textbf{any physical load factor} up to and \textbf{including one} ($0.9999$ demonstrated), exactly for the requested capacity, compared to hashbrown which doubles at $0.777$ for 4-byte keys and values. At 75% saturation of hashbrown (assumed average case of its rigid ladder) and multitable sized to $0.97$ physical load factor, hashbrown takes 66% more space. The lookup probe count has no cliff as the load factor approaches one. Bucket size, physical load factor, and failure budget are parameters, and the multitable can be grown without rehashing. We implement two variants of multitable: plain and filtered. At equal physical memory on an Apple M2 Pro the filtered multitable leads hashbrown in all $84$ insert, hit, and miss configurations. Multitable is more \textbf{memory-efficient}, at equal mixed-lookup throughput on the map of $4$-byte keys and values the filtered multitable needs up to 12% fewer bytes than hashbrown, and the plain multitable is 18% smaller, holding 22% more keys in the same memory.
Related
- Get Permanent Results Faster by Counting Stars
- Faster high-accuracy multicommodity flow in dense graphs
- Constrained Capacity for Faster-than-Nyquist Signaling in Frequency-Selective Fading Channels
- Faster Estimates from Binned Test Score Data---and How Accurate They Are
- An Adaptive Symplectic Proximal Point Algorithm: Faster Convergence and Improved Numerical Performance
BibTeX
@misc{petkus2026multitable,
title = {{MultiTable: A Faster Hash Table at any Physical Load Factor up to and Including One}},
author = {Maksym Petkus},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.39233},
eprint = {2609.39233},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.39233},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - MultiTable: A Faster Hash Table at any Physical Load Factor up to and Including One
AU - Maksym Petkus
PY - 2026
DA - 2026/09/30
PB - arXiv
DO - 10.48550/arxiv.2609.39233
UR - https://arxiv.org/abs/2609.39233
AB - We present \emph{multitable} and its Rust reference implementation: a stable hash table both materially faster at equal physical memory and more flexible than the SwissTable in its Rust's hashbrown implementation. As an arithmetic mean over 84 configurations it delivers 2.1× hashbrown's throughput when both hash the same raw bytes and 1.9× when hashbrown is keyed on native integers, its best case; on negative lookups alone, 3.2× and 2.9×. Multitable reaches \textbf{any physical load factor} up to and \textbf{including one} ($0.9999$ demonstrated), exactly for the requested capacity, compared to hashbrown which doubles at $0.777$ for 4-byte keys and values. At 75% saturation of hashbrown (assumed average case of its rigid ladder) and multitable sized to $0.97$ physical load factor, hashbrown takes 66% more space. The lookup probe count has no cliff as the load factor approaches one. Bucket size, physical load factor, and failure budget are parameters, and the multitable can be grown without rehashing. We implement two variants of multitable: plain and filtered. At equal physical memory on an Apple M2 Pro the filtered multitable leads hashbrown in all $84$ insert, hit, and miss configurations. Multitable is more \textbf{memory-efficient}, at equal mixed-lookup throughput on the map of $4$-byte keys and values the filtered multitable needs up to 12% fewer bytes than hashbrown, and the plain multitable is 18% smaller, holding 22% more keys in the same memory.
ER -