Source-linked AI summary
Quadratic Probing Insertions Are $ε^{-(1+o(1))}$
Yang Hu, William Kuszmaul, Jingxun Liang, Stefan Walzer, Huacheng Yu, Renfei Zhou
TL;DR
Quadratic probing is widely believed to avoid linear-probing clustering, but its expected insertion-time performance had remained unproved. This paper analyzes the scheme using a number-theoretic property and establishes an ε^{-(1+o(1))} expected insertion-time bound, showing clustering is avoided up to a subpolynomial factor in ε^{-1}.
Problem
Quadratic probing is believed to achieve O(ε^{-1}) expected insertion time while avoiding linear-probing clustering, but this conjecture has remained unproved.
Method
The analysis uses a number-theoretic property of quadratic probing and a weak characterization of previous insertions employing fixed-offset probing schemes.
Results
ε^{-(1+o(1))} is the expected time for the ((1−ε)n+1)-th insertion in a prime-size table when 1>ε>1/√log n.
Takeaways & Limitations
Quadratic probing avoids linear-probing clustering up to a subpolynomial factor in ε^{-1}.
Takeaways & Limitations
Deletions are not considered.
Abstract
from arXiv · showhide
First proposed in 1968, quadratic probing has stood for more than half a century as one of the simplest and most widely used hash-table designs in computer science. It is conjectured that, at load factor $1 - ε$, the hash table achieves $O(ε^{-1})$ expected insertion time. But even proving a bound of the form $f(ε^{-1})$ for any function $f$ has remained open. In this paper, we prove that the expected insertion time is $ε^{-(1 + o(1))}$. This settles the complexity of the data structure up to sub-polynomial factors in $ε^{-1}$.
1 Introduction
Quadratic probing was introduced to avoid linear probing’s clustering, but its high-load insertion-time guarantees remained largely unresolved. This paper proves an ε^{-(1+o(1))} expected bound and identifies structure-specific reasons for it.
- Linear probing’s clustering raises expected insertion time to Θ(ε^-2) when only an ε fraction of slots is empty.
- Quadratic probing replaces consecutive offsets with square offsets to retain data locality while escaping linear probing’s clustering behavior.
- Even an O(1) expected-time bound for a table that is 50% full had remained open before this work.
- The analysis considers insertion-only workloads and does not consider deletions.
- Theorem 1.1 establishes ε^{-(1+o(1))} expected time for the ((1−ε)n+1)-th insertion when n is prime and 1>ε>1/√log n.
- Quadratic probing avoids linear-probing-style clustering up to a subpolynomial factor in ε^-1.
- The analysis exploits small intersections between translated prefixes of quadratic probing sequences, a property unavailable to general fixed-offset schemes.
- The proof models previous insertions through translation invariance and positive association of free-slot indicators.
2 Preliminaries
The preliminaries define quadratic probing, establish basic properties of its probe sequence, and introduce positive association and occupied-set monotonicity used later in the analysis.
- A quadratic probing table stores keys in n slots and supports insertions and membership queries.
- For a key x, the algorithm examines h(x), h(x)+1^2, h(x)+2^2, … modulo n and stores x in the first empty slot.
- For prime n, the first n/2 quadratic-probing offsets are guaranteed to be distinct modulo n.
- Positive association means that coordinatewise nondecreasing functions of the variables have nonnegative covariance.
- Independent variables and monotone functions of common independent inputs are positively associated.
- Every insertion terminates within 2n probes when the table is not full, with later unprobed offsets examined in a fixed order if necessary.
- Occupied-set monotonicity preserves set inclusion after applying the same future insertions to two tables.
3 Poissonization and Positive Association
The analysis Poissonizes the number of stored keys, proves positive association and translation invariance for free slots, and uses these properties to control insertion-time probabilities.
- The Poissonized model inserts N∼Poisson((1−ε)n) keys instead of exactly (1−ε)n keys.
- The Poissonized model treats insertions after the table becomes full as no-ops with insertion time 2n.
- Poissonization reduces analysis of the fixed-load insertion time to analysis of the Poissonized model.
- In the Poissonized table, each free-slot indicator has expectation at least ε and the indicators are positively associated.
- The positive-association conclusion depends on Poissonization and need not hold for a fixed number of inserted keys.
- Rotational symmetry makes the free-slot vector translation-invariant, so covariance between slots depends only on their offset.
- Positive association is established by layering independent Poisson counts, applying Harris’s inequality and occupied-set monotonicity, then taking the layer limit.
- All vacancy covariances C(r) are nonnegative, enabling bounds on covariance sums along quadratic-probing offsets.
4 Bounding the Vacancy Covariances along a Probe Sequence
The analysis bounds the covariance accumulated along the first k quadratic probes by R(k), the maximum multiplicity of a difference between probe offsets. For k≤√n, R(k)=k^o(1), reflecting mostly distinct quadratic distances and enabling the final ε^{-(1+o(1))} time bound.
- Covariance measure: R(k) is the largest multiplicity of any difference b^2−a^2 modulo n among distinct probe indices a<b<k.Equivalently, it is the largest coefficient when the covariance sum is expressed using C(0),…,C(k−1).
- Covariance bound: The sum of covariances over all distinct pairs among the first k quadratic probes is at most R(k), for prime n and 1≤k≤n/2.This is the central technical proposition linking probe-distance multiplicities to vacancy covariances.
- Quadratic-distance structure: For k≤√n, R(k)=k^o(1), so quadratic probe distances are mostly distinct modulo n.This small multiplicity distinguishes quadratic probing from linear probing in the final analysis.
- Poissonized analysis: Poissonization makes the covariance terms C(r) nonnegative, allowing any subset sum of them to remain at most 1.The argument uses the variance bound Var(Z)≤n for the number of empty slots.
5 A Tail Bound from the Covariance Properties
The paper converts the covariance estimate into a tail bound for insertion time by analyzing positively associated vacancy indicators and comparing them with independent Bernoulli variables. Positive association is essential because a variance-only bound would be too weak for a nontrivial ε-dependent insertion-time result.
- Tail-bound setup: The covariance estimate is converted into a tail bound relating insertion time T to R(k) in the Poissonized table.The insertion probes 0^2,1^2,…,(k−1)^2 after normalizing the new key’s hash to 0.
- Positive association: Positive association enables a bound on the probability that all vacancy indicators among the first k probes are zero.The indicators are treated as positively associated Bernoulli variables, and the analysis controls their joint zero event.
- Why the stronger inequality matters: Without positive association, Chebyshev’s inequality yields only Pr[S=0]≤O(ε/k), which is too weak for any nontrivial insertion-time bound in ε^-1.Here the summed variances satisfy ∑_{i=1}^k Var(F_i^2)=Θ(kε).
- Proof strategy: The comparison replaces positively associated indicators with independent Bernoulli variables having the same marginals, then applies a Chernoff bound.A convex-function comparison controls the cost of replacing the dependent sum by the independent one.
- Combining estimates: The resulting tail estimate combines the positive-association inequality with Proposition 4.1’s covariance bound and eliminates the exponential term by polynomial domination.The exponential term is bounded using e^-x/8=O(x^-2) for x>0.
6 Bounding Insertion Time
The analysis bounds insertion-time tails by controlling repeated square differences, then combines arithmetic estimates with Poissonization and a covering argument. These bounds establish the tail behavior needed for the nearly optimal expected insertion-time result.
- Translating bounds to insertion time: The covariance bounds are converted into fixed-load insertion-time tails through Proposition 5.1 and the Poissonization comparison.The resulting cases cover the principal ranges of k, with monotonicity filling gaps between selected values.
- Covering the extreme regime: Quadratic probing avoids linear probing’s clustering because its probe differences spread sufficiently that R(k) initially grows at rate k^o(1), rather than Θ(k).The final large-k regime instead conditions on any occupied set and bounds the number of hashes causing very long insertions.
- Bounding R(k): R(k) measures the largest number of pairs among the first k probe indices sharing a square difference modulo n.It is also the largest coefficient in the relevant covariance linear combination.
- Bounding R(k): For k ≤ n^1/2, factoring b^2 − a^2 into (b − a)(b + a) reduces the count to a divisor bound.The congruence becomes an integer equality in this range.
7 Completing the Analysis
The paper completes the expected-time analysis by summing tail bounds across probe ranges. The only range contributing more than O(ε^-1) is controlled sufficiently to obtain the stated ε^{-(1+o(1))} bound.
- Final expected-time bound: Theorem 1.1 gives expected insertion time ε^{-(1+o(1))} for prime table size n and 1 > ε > 1/√log n.The insertion considered is the ((1 − ε)n + 1)-th insertion.
- Final expected-time bound: The proof may restrict to ε ≤ 1/2 because expected insertion time is nonincreasing in ε, while the ε = 1/2 case supplies the constant bound for larger ε.This reduction is used before the range-by-range summation.
- Final expected-time bound: The expectation is bounded by summing Pr[T > k] over probe counts, using that insertion time is at most 2n and the tail is nonincreasing.The proof handles the sum range by range.
- Final expected-time bound: Only one probe-count range contributes more than O(ε^-1) to the expectation.The remaining ranges are controlled by the tail bounds established earlier.