hash_insert_step
Given table size n, an offset sequence r : Fin n → ZMod n, a set of occupied slots T : Finset (ZMod n), and an element a : ZMod n, hash_insert_step n r T a is the updated set of occupied slots in Finset (ZMod n) obtained by adding a + r(j) to T for the minimal index j : Fin n such that a + r(j) ∉ T, or returning T unchanged if no such candidate index exists.
Statement
def hash_insert_step (n : ℕ) (r : Fin n → ZMod n) (T : Finset (ZMod n)) (a : ZMod n) : Finset (ZMod n)- Defined in
- arXiv:2610.31363 Section 2
- Verified
- 23 Oct 2026
- Axioms
- none listed
- Used by 5
- 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…
- hash_probe_expected_cost_sub_constTranslating an offset sequence by subtracting a constant element c in ZMod n preserves the expected probe cost at any load t, by…
- hash_occupied_slots_cardFor any table size n with [NeZero n], any bijective offset sequence r : Fin n → ZMod n, and any list of keys A with length at most n, the…
- hash_probe_expected_cost_twoAfter two insertions the expected cost is 1+2/n+(3+[2r₁=0])/n².
- hash_adjacent_step_counterexampleOn a fixed occupied set, a unit-first order can create more adjacent pairs on average in the next step than linear probing.
Read back from the Lean
Given a natural number n, a probe offset function r : Fin n → ZMod n, a finite set T : Finset (ZMod n), and an element a : ZMod n, hash_insert_step n r T a evaluates to a Finset (ZMod n) defined as follows:
Let candidates be the set of indices j : Fin n such that a + r j ∉ T.
- If candidates is non-empty, return T ∪ {a + r j_min}, where j_min is the minimum element of candidates under the standard linear order on Fin n.
- If candidates is empty, return T.
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
/-- One step of open addressing hash table insertion with fixed offset sequence. -/ def hash_insert_step (n : ℕ) (r : Fin n → ZMod n) (T : Finset (ZMod n)) (a : ZMod n) : Finset (ZMod n) := let candidates := Finset.univ.filter (fun j : Fin n => a + r j ∉ T) if h : candidates.Nonempty then T ∪ {a + r (candidates.min' h)} else T