AFTD Auto-Formalizing Theoretical Domains

hash_insert_step

def

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