Skip to the content

Math 2.0

Resources / preprint

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

URI	`m2://res/Y7NC12TBNP`
Kind	preprint
Creators	Maksym Petkus
Date	2026-09-30
Subjects	arxiv cs.CR, arxiv cs.DS, arxiv math.CO, arxiv math.PR
Scope	border

Expressions

e1: version, preprint

Date	2026-09-30
Ids	arXiv 2609.39233

Items in this resource

The mentions of the inventory that name this resource. Each name links to the card of its inventory row.

Item	Kind	Where	Source
Constant positive-lookup cost	statement	corollary 2	arxiv
Exact mean overflow; \appproof{pf:meanoverflow	statement	theorem 2	arxiv
Bounded differences	statement	lemma 4	arxiv
Efficient construction	definition	definition 2	arxiv
Perfect construction	definition	definition 1	arxiv
Bucket occupancy	statement	proposition 1	arxiv
Improved multicollision bound	statement	proposition 5	arxiv
Logarithmic depth	statement	proposition 4	arxiv
Perfect table	statement	theorem 1	arxiv
Per-level bound; \appproof{pf:levelbound	statement	proposition 3	arxiv
Truncated mean; \appproof{pf:truncated	statement	lemma 2	arxiv
Cap and monotonicity; \appproof{pf:capmono	statement	lemma 3	arxiv
Depth truncation	statement	corollary 1	arxiv
Tilted quantiles; \appproof{pf:tilt	statement	lemma 6	arxiv
Efficient table; \appproof{pf:efficient	statement	theorem 3	arxiv
Multilevel table	unknown	unknown	arxiv
Lookup cost	statement	proposition 2	arxiv
Collision counts	statement	lemma 1	arxiv
Negative association and stored keys; \appproof{pf:na	statement	lemma 5	arxiv

Catalogue records

arxiv: 2609.39233 (work)