pipette
ENEnglish

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

Maksym Petkus

PreprintAfirmaciones fuertes, leer con cuidadoUso en el mundo real

En palabras de los autores

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 hashbrown's throughput when both hash the same raw bytes and when hashbrown is keyed on native integers, its best case; on negative lookups alone, and . Multitable reaches any physical load factor up to and including one ( demonstrated), exactly for the requested capacity, compared to hashbrown which doubles at for 4-byte keys and values. At saturation of hashbrown (assumed average case of its rigid ladder) and multitable sized to physical load factor, hashbrown takes 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 insert, hit, and miss configurations. Multitable is more memory-efficient, at equal mixed-lookup throughput on the map of -byte keys and values the filtered multitable needs up to fewer bytes than hashbrown, and the plain multitable is smaller, holding \mathbf{22%} more keys in the same memory.

Resultado principalEl resumen no menciona limitaciones.

Apareció: jueves, 1 de octubre. arXiv. Preprint, todavía sin revisión por pares.