hash_total_probe_cost
For a table of size n, an offset sequence r : Fin n → ZMod n, and a list of inserted key home slots A : List (ZMod n), hash_total_probe_cost n r A is the sum of the numbers of probes used by all insertions when the keys in A are inserted sequentially into an initially empty table.
Statement
def hash_total_probe_cost (n : ℕ) (r : Fin n → ZMod n) (A : List (ZMod n)) : ℕ- Defined in
- arXiv:2610.31363, Section 2
- Verified
- 03 Nov 2026
- Axioms
- none listed
Read back from the Lean
hash_total_probe_cost n r A defines the total probe cost (as a natural number ℕ) of sequentially inserting elements of a list A : List (ZMod n) into a hash table with n : ℕ slots using the probe offset function r : Fin n → ZMod n.
The calculation proceeds by folding over A starting with the initial state (∅, 0) consisting of an empty set of occupied slots Finset (ZMod n) and an initial cost of 0:
For each element a in A:
1. It considers the set candidates of probe indices j : Fin n such that a + r j is not in the currently occupied set.
2. If candidates is nonempty, it takes the minimal index j_min = candidates.min', adds the slot a + r j_min to the set of occupied slots, and adds j_min.val + 1 (the 1-based probe count) to the accumulated cost.
3. If candidates is empty (all probed locations are already occupied), the state remains unchanged.
The function returns the second component of the final state, which is the total accumulated probe cost.
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
/-- The total number of probes accumulated across sequential insertions of keys into an initially empty hash table under offset sequence r. -/ def hash_total_probe_cost (n : ℕ) (r : Fin n → ZMod n) (A : List (ZMod n)) : ℕ := let step : Finset (ZMod n) × ℕ → ZMod n → Finset (ZMod n) × ℕ := fun state a => have candidates : Finset (Fin n) := {j | a + r j ∉ state.1} if h : candidates.Nonempty then (state.1 ∪ {a + r (candidates.min' h)}, state.2 + (candidates.min' h).val + 1) else state (List.foldl step (∅, 0) A).2