# Notes

### 2023-07-14

It is folklore that, under some conditions, open-addressed hash tables with quadratic probing do not miss free slots. This note explains why with a proof.

Let me break things down a little. With hash
tables, the prime problem to solve when
implementing insertion is conflicts: You are
handed a key value pair (K₁,V₁) and, after
hasing the key K₁, you realize that the table
slot designated by the hash value is already
filled with a binding (K₂,V₂). Chaining
implementations will just cram the binding
in the slot anyway, hence creating a bucket
with more than one binding in a single
table slot. Open-addressing implementations
will instead go look for another slot.
One obvious strategy for searching is to
go look at the next slot, and the next one,
and so on, potentially wrapping around when the
last slot of the table is visited.
Quadratic probing offers an alternative scheme:
instead of scanning slot `h+i mod N`

at the
i-th step, it scans the slot `h+P(i) mod N`

where `P`

is a polynomial function of degree 2.
This strategy helps with the clustering problem
that linear probing may create.

The polynomial `P`

of interest to us here is
`P(X) = (X + X²)/2`

.
The polynomial `P`

outputs so-called
triangular numbers (they can be stacked in a
triangle shape), and the sequence `P(0)`

, `P(1)`

,
`P(2)`

, ... is easily computed:

p_i = 0; for (i=0; i<N; i++) { assert(p_i == (i + i*i)/2); p_i += i; }

But, more importantly, if the table size is a power of 2, and there is a single free slot, quadratic probing will find it. It is not an obvious fact and I prove it below.

Formally, we want to show that as `i`

ranges
over the interval `I=[0,2ⁿ)`

, `h+P(i) mod 2ⁿ`

ranges over `I`

as well. Said differently, we
want to show that the function mapping `x`

to
`h+P(x) mod 2ⁿ`

is a bijection over `I`

.
Since `I`

is finite, it is sufficent to show
that the map is injective; that is, it maps
different values of `I`

to different values.

To prove injectivity we consider `i`

and `j`

in `I`

such that `h+P(i) mod 2ⁿ`

= `h+P(j) mod 2ⁿ`

and show
that `i`

must be equal to `j`

. We first reason by
equivalence:

(h + P(i) mod 2ⁿ) = (h + P(j) mod 2ⁿ) ⟺ (h + (i + i²)/2) - (h + (j + j²)/2) = k2ⁿ ⟺ (i + i²) - (j + j²) = k2ⁿ⁺¹ ⟺ (i - j)(1 + i + j) = k2ⁿ⁺¹

Breaking the products on both sides we get that
there must be three integers `k₁`

, `k₂`

, and `m`

such that:

A := i - j = k₁2ᵐ with k = k₁k₂ B := 1 + i + j = k₂2ⁿ⁺¹⁻ᵐ and 0 ≤ m ≤ n + 1

We now consider three cases:

- If
`m`

is not`0`

nor`n+1`

then it must be that both`A`

and`B`

are even. That is however impossible because`B = 1 + 2j + A`

, so when`A`

is even,`B`

is odd, and vice versa. - If
`m`

is`n+1`

, we must then have`i - j = k₁2ⁿ⁺¹`

, but since`i`

and`j`

are in the interval`I`

,`i - j`

is in`(-2ⁿ,2ⁿ)`

, so`k₁`

can only be zero and thus`i`

equals`j`

. - If
`m`

is`0`

, we again use a size argument. Since`i`

and`j`

are in`I`

, we have that`1 + i + j`

is in`(0,2ⁿ⁺¹-1)`

. So`k₂`

must be positive and less than 1; these requirements prove that the present case is impossible.

The only possible outcome for the case analysis
is thus that `i`

equals `j`

. Unwinding everything, the
map `h+P(x) mod 2ⁿ`

is injective on `I`

, so it is
also bijective on `I`

, so when `i`

ranges from `0`

to `2ⁿ-1`

, the map ranges over all of `I`

, and thus
quadratic probing indeed vists all slots!