linear_probing_displacements
Given a table size n and a sequence of n home slots h in Fin n -> ZMod n, linear_probing_displacements n h i is the number of occupied slots inspected by insertion i before finding an empty slot under linear probing.
Statement
def linear_probing_displacements (n : ℕ) [NeZero n] (h : Fin n → ZMod n) : Fin n → ℕ- Defined in
- scout/2610-31363-a-sharp-analysis-of-fixed-offset-hash-tables.md
- Verified
- 03 Nov 2026
- Axioms
- none listed
- Built on 2
- hash_occupied_slotsThe set of occupied slots in Finset (ZMod n) after sequentially inserting a list A : List (ZMod n) into an initially empty hash table of…
- linear_probe_offsetGiven a natural number n, linear_probe_offset n is the function from Fin n to ZMod n that maps each index j : Fin n to its canonical…
- Used by 1
- linear_probing_noisy_displacementsGiven $n \ge 1$, home slot assignments $h : \text{Fin } n \to \mathbb{Z}/n\mathbb{Z}$, and a noise vector…
Read back from the Lean
linear_probing_displacements defines a function that, given a positive natural number n (with hypothesis [NeZero n]) and a sequence of hash addresses h : Fin n → ZMod n, maps each index i : Fin n to a natural number representing the displacement (probe distance) of the i-th element under linear probing.
Specifically, for an index i:
1. It computes the set T of occupied hash slots resulting from inserting the first i.val elements (h 0, ..., h (i - 1)) into an initially empty hash table of size n via linear probing.
2. It considers all candidate probe offsets j : Fin n such that h i + (j : ZMod n) ∉ T.
3. If this candidate set is nonempty, it returns the value j.val of the minimal j : Fin n in the set (i.e., the smallest displacement $\ge 0$ that finds an unoccupied slot).
4. If the candidate set is empty, it returns 0.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- Vector of displacements (number of occupied slots inspected before the first empty slot) for each sequential insertion in an n-slot circular hash table under linear probing. -/ def linear_probing_displacements (n : ℕ) [NeZero n] (h : Fin n → ZMod n) : Fin n → ℕ := fun i => let T := hash_occupied_slots n (linear_probe_offset n) ((List.ofFn h).take i.val) let candidates := Finset.univ.filter (fun j : Fin n => h i + (j : ZMod n) ∉ T) if hc : candidates.Nonempty then (candidates.min' hc).val else 0