Skip to content
Preprint

A Sharp Analysis of Fixed Offset Hash Tables

Oct 2026 · 1 citation · 15 references
Computer Science

TL;DR

This work considers the class of open addressing hash tables that uses a fixed offset sequence that uses a fixed offset sequence $r_0,r_1,\ldots,r_{n-1}$ to find an open slot in the table and gives a simple analysis that the expected insertion time when the load factor is 1-\epsilon is O(\epsilon^{-2})$.

Abstract

We consider the class of open addressing hash tables that uses a fixed offset sequence $r_0,r_1,\ldots,r_{n-1}$ to find an open slot in the table. As special cases this subsumes linear probing ($r_i=i$) and quadratic probing ($r_i=i^2$). We give a simple analysis that the expected insertion time when the load factor is $1-\epsilon$ is $O(\epsilon^{-2})$. This bound is tight for linear probing (but not for quadratic probing), so the analysis cannot be improved at this level of generality.

View source

Similar papers

Preprint Oct 2026

Optimal Worst-Case Open Addressing: Braided Cuckoo Hashing

In this paper, we introduce braided cuckoo hashing, an open-addressed hash table that supports load factor up to $1 - \varepsilon$ (for some parameter $\varepsilon \in (0, 1)$), while supporting queries, insertions, and deletions in worst-case time $O(\log \varepsilon^{-1})$, with high probability. This result represen...

A. Krapivin, William Kuszmaul · 0 citations
Preprint Nov 2026

Catalan Hashing: Efficient Linear Probing for Variable-Length Items

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 ite...

A. Conway, Hanna Komlós, William Kuszmaul · 0 citations
Preprint Oct 2026

Separating hash families with large universe II

For fixed integers $t,k\ge 2$, put $N=(t-1)(k-1)+1$. We prove that the maximum universe size of a $t$-perfect hash family of length $N$ over an alphabet of size $q$ satisfies $ p_t(N,q)\ge q^{k-o(1)}$. Together with monotonicity in the length, this gives a positive answer to a question of Blackburn, Etzion, Stinson and...

Xin Wei, Gen-Nian Ge · 1 citation
Preprint Sep 2026

The Power of Two-Choice Linear Probing

There is a surprisingly strong ``power of two choices''phenomenon for linear-probing hash tables, allowing for a two-choice hash table to achieve significantly better bounds than what might at first seem to be possible.

Amir Azarmehr, Michael A. Bender, William Kuszmaul et al. · 0 citations
Preprint Oct 2026

A note on the logarithmic exponent of Ramsey number $r(4,t)$

In this short note, we point out that the recent lower bounds for off-diagonal Ramsey numbers $r(s,t)$ with fixed $s\ge 5$, together with the recent proof of the Ajtai--Erd\H{o}s--Koml\'os--Szemer\'edi independence conjecture, imply \[ r(4,t)=\frac{t^3}{(\log t)^{2+o(1)}}. \] This note is solely for informal circulatio...

Kai-Zhe Chen · 0 citations
Preprint Oct 2026

Dimension Amplification for Tarski Fixed-Point Query Lower Bounds

We prove that finding a fixed point of a monotone map on the nine-dimensional grid $[N]^9$ requires $\Omega((\log N)^3)$ deterministic queries, even when the fixed point is unique and each query returns the entire function value. The proof gives a construction that raises the dimension from $d$ to $4d+1$, preserves uni...

Bo-Yu Liu, Zihe Wang · 2 citations

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.