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

arXiv:2609.39233 · cs.CR, cs.DS, math.CO, math.PR · Submitted 2026-09-30 · Read on arXiv

cs.CR, cs.DS, math.CO, math.PR

Submitted: 2026-09-30

Updated: 2026-09-30

Code: https://github.com/maksympetkus/multitable

Terminology

• Linear Probing — 4× in this paper · explained in 2 episodes
• Benchmark — 3× in this paper · explained in 2 episodes
• Trace — 3× in this paper · explained in 2 episodes
• Allocator — 1× in this paper · explained in 1 episode

Sources

• Iceberg Hashing: Optimizing Many Hash-Table Criteria at Once
• IcebergHT: High Performance PMEM Hash Tables Through Stability and Low Associativity
• Optimal Bounds for Open Addressing Without Reordering
• Fast Random Integer Generation in an Interval

Related papers

• SoK: AI-Augmented Binary Reversing
• Relaxed Sender Anonymity for CBDC Interbank Settlement: A Zero-Knowledge Approach on Permissioned EVM
• Calibration-Family Overfit: Why Trusted Sabotage Monitors Don't Transfer Across Lineages
• Efficient Fuzzy PSI under One-Sided Assumptions
• Sealing the Audit-Runtime Gap for LLM Skills
• Token Composition: A Graph Based on EVM Logs