AFTD Auto-Formalizing Theoretical Domains

linear_probing_displacements

def

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

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
See it in the graphDiscuss this resultChallenge it