Multitable speeds up hash tables and saves memory even at full capacity
MultiTable: A Faster Hash Table at any Physical Load Factor up to and Including One
Cryptography and SecurityData Structures and Algorithms
Summary
Hash tables are a common way to store and find data quickly on computers. The authors introduce multitable, a new hash table design that works faster and more efficiently than one popular Rust implementation, hashbrown. It can handle being almost completely full without slowing down or using extra space, unlike many existing tables. Multitable also needs less memory to hold the same data and keeps working smoothly as it fills up.
What this means in practice
- •For software engineers: Improve in-memory key-value stores by replacing existing hash tables with multitable to achieve faster data access and lower memory use at high load.
- •For database developers: Enhance the efficiency of database indexing by integrating multitable for stable high-load performance and reduced storage overhead.
Authors
Maksym Petkus
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 $\mathbf{2.1\times}$ hashbrown's throughput when both hash the same raw bytes and $\mathbf{1.9\times}$ when hashbrown is keyed on native integers, its best case; on negative lookups alone, $3.2\times$ and $2.9\times$. 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 $\mathbf{22\%}$ more keys in the same memory.