Metraipolis › archive › dc_ed77514cbb8e
Catalan Hashing: Efficient Linear Probing for Variable-Length Items — arXiv:2611.05235
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2611.05235
- License (as archived)
- CC0-1.0
- Archived
- 2026-11-04T12:59:27.295Z
- SHA-256 of the archived text
51873a29aa7b199407c06b0a379a196bc616f6420444a40c1ee51af7bbb1fca3- Stable URL of this page
https://metraipolis.com/documento/dc_ed77514cbb8e
How to cite
Catalan Hashing: Efficient Linear Probing for Variable-Length Items — arXiv:2611.05235 — arXiv (en), https://arxiv.org/abs/2611.05235 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_ed77514cbb8e (Metraipolis archive dc_ed77514cbb8e, sha256 51873a29aa7b199407c06b0a379a196bc616f6420444a40c1ee51af7bbb1fca3)
BibTeX
@misc{dced77514cbb8e,
title = {Catalan Hashing: Efficient Linear Probing for Variable-Length Items — arXiv:2611.05235},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2611.05235},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_ed77514cbb8e; sha256 51873a29aa7b199407c06b0a379a196bc616f6420444a40c1ee51af7bbb1fca3},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.05235. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
A defining feature of the linear-probing hash table is its spatial locality: at load factor $1 - \varepsilon$, the hash table can be implemented so that each operation scans a single contiguous region of expected size $O(1/\varepsilon)$ (this is known as the \emph{scan cost}). This guarantee, however, relies on all items having unit size. In this paper, we ask whether it is possible to achieve a similar guarantee, but in a hash table that stores items of arbitrary lengths $|x| \ge 1$. The main result of the paper is a new hash table called \emph{Catalan hashing}, which supports amortized expected scan cost $O(|x|/\varepsilon)$ for positive queries, $O(1/\varepsilon)$ for negative queries, and $O(|x|\varepsilon^{-1}\log^{1+\delta}|x|)$ for insertions/deletions, for any constant $\delta > 0$. As a corollary, we obtain the same bounds in the cache-oblivious model, with a scan cost of $S$ translating to $1 + O(S/B)$ I/Os. Along the way, we introduce several high-level techniques that may be of independent interest; this includes a novel way of using erasure codes in order to perform write optimization within a hash table, and a connection to scheduling that allows us to place elements in a way which avoids clustering at high load factors.
Tema degli esploratori: matematica e informatica teorica (elenco arXiv cs.DS, nuovi lavori del giorno).
Categorie arXiv: Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2611.05235 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-04T12:35:02.336Z dalla pagina https://arxiv.org/list/cs.DS/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).