MultiTable: A Faster Hash Table at any Physical Load Factor up to and Including One

We present 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 times hashbrown's throughput when both hash the same raw bytes and 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 any physical load factor up to and 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 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.