A Sharp Analysis of Fixed Offset Hash Tables

1 Introduction

• Fixed-offset probing uses a permutation of table-slot offsets, with linear probing and quadratic probing as special cases.The paper takes the first open slot in the sequence beginning at the key's hash value.Source: §1 · p. 1

1.1 New Result

• Prior work had established stronger high-load insertion bounds for quadratic probing than for general fixed-offset schemes, motivating a simpler general analysis.The paper contrasts its elementary analysis with recent fixed-offset and quadratic-probing analyses and earlier linear-probing analyses.Source: §1 · p. 1, §1.1 · p. 2
• At load factor 1 − ϵ, every fixed-offset table has expected insertion cost at most 1 + 2ϵ^-2; linear probing makes this bound asymptotically tight.The stated constant-factor gap is at most 4.Source: §1.1 · p. 2

1.2 Organization

• The note proceeds from sequence notation to occupation counts, a recurrence for full occupancy, and an insertion-time bound.This is the stated progression of Sections 2–5.Source: §1.2 · p. 2

2 Notation, Definitions, and Conventions

• With a uniformly random hash function, an input sequence is represented by its hash values in [n], which determine the occupied slots together with the fixed offset permutation.If an item lands at offset r_i, its insertion cost is i + 1.Source: §2 · p. 2
• For a sequence A, A<i and A>i denote the portions before and after position i, while A−i removes the ith element.Juxtaposition denotes sequence catenation.Source: §2 · p. 2

3 Properties of Occupation

• Occupy_S(A) counts the slots of S occupied after inserting sequence A into an empty table.The analysis uses this function even though its behavior depends implicitly on the fixed offset permutation.Source: §3 · p. 2
• Removing one element from an insertion sequence leaves the reduced table's occupied slots nested within those of the original table.At each later step, the original table has exactly one more occupied slot.Source: §3 · p. 3
• The analysis relates sequences that fully occupy S to the probability p_k(t) that a particular k-slot set is fully occupied after t random insertions.Theorem 3.3 reduces expected insertion cost to bounding p_k(t).Source: §3 · pp. 3–4
• For the next insertion, the first k probed slots form S_k, and the expected cost is bounded using the probability that S_k is occupied.The stated argument uses linearity of expectation and an upper bound on p_k(t).Source: §3 · p. 3

4 The Recursive Bound

• The recurrence works backward from the full-table values F_S(n) = n^n and p_k(n) = 1, bounding earlier values from later ones.The theorem applies for a set S of size k and k < t ≤ n.Source: §4 · pp. 4, 6
• The potential ϕ(A) is the expected number of occupied slots in S when A is extended by a random suffix to length t.The proof uses changes in this potential to bound the recurrence.Source: §4 · pp. 4, 6
• The proof controls changes in potential by comparing occupancy after appending alternative elements and using symmetry across the possible elements.For fixed S and t, symmetry gives expected occupancy t|S|/n after t insertions.Source: §4 · pp. 4–5

• After n−1 insertions, the sole free slot lies outside a given k-slot set with probability 1−k/n.Source: §5 · p. 6
• Theorem 4.1 supplies a recursive bound on p_k(t), with d defined as n−t.Source: §5 · p. 6
• At d = εn, p_k(t) is bounded by exp(−kε^2/2), which Theorem 3.3 uses to bound expected insertion cost.Source: §5 · p. 6

• The independence needed to preserve the guarantees for fixed-offset or quadratic hashing remains an open problem.Source: §6 · p. 7
• For linear probing, 5-wise independence is known to suffice.Source: §6 · p. 7
• For linear probing, 4-wise independence is not sufficient in general.Source: §6 · p. 7