AFTD Auto-Formalizing Theoretical Domains

hash_occupied_slots

def

The set of occupied slots in Finset (ZMod n) after sequentially inserting a list A : List (ZMod n) into an initially empty hash table of size n using offset sequence r : Fin n → ZMod n.

Statement

def hash_occupied_slots (n : ℕ) (r : Fin n → ZMod n) (A : List (ZMod n)) : Finset (ZMod n)
Defined in
arXiv:2610.31363 Section 2
Verified
23 Oct 2026
Axioms
none listed
Built on 1
  • hash_insert_stepGiven 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,…
Used by 16
  • hash_occupy_count_nilFor any n, r : Fin n → ZMod n, and S : Finset (ZMod n), hash_occupy_count n r S [] = 0.
  • hash_probe_tail_countThe number of pairs of an insertion sequence of length t and an additional query slot whose insertion cost under offset sequence r…
  • linear_probing_displacementsGiven 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…
  • 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_tail_count_zero_of_lt_strictFor any table size n with [NeZero n], any bijective offset sequence r, and load t < n, the probe tail count is 0 whenever k > t.
  • hash_probe_expected_cost_zeroFor any table size n with [NeZero n] and any offset sequence r : Fin n → ZMod n, the expected probe cost hash_probe_expected_cost n r 0…
  • hash_probe_tail_prob_zeroFor any table size n with [NeZero n], offset sequence r : Fin n → ZMod n, and number of inserted keys t, the 0-th tail probability of…
  • hash_probe_expected_cost_twoAfter two insertions the expected cost is 1+2/n+(3+[2r₁=0])/n².
  • prime_fixed_offset_linear_probe_stochastic_maximum_threeFor a 3-slot hash table (p = 3), every bijective probe sequence r : Fin 3 → ZMod 3 with r 0 = 0, every load t < 3, and every integer k ≥…
  • not_hash_probe_tail_prob_zero_of_ltThe statement hash_probe_tail_prob_zero_of_lt is false: Take n = 1, r = (fun _ => 0 : Fin 1 → ZMod 1), t = 1, k = 2. Hypotheses hold:…
  • hash_probe_tail_prob_oneFor any table size n ≥ 2 with [NeZero n], any bijective offset sequence r with r 0 = 0, and any load t ≤ n, the 1st tail probability…
  • hash_probe_tail_two_eq_adjacent_meanThe second probe-cost tail equals the expected number of occupied adjacent pairs, divided by the table size.
  • prime_fixed_offset_linear_probe_tail_prob_interior_t_predAt load t = p - 1 (one empty slot), every bijective offset sequence has identical probe tail probabilities, matching linear probing.
  • hash_occupy_countThe number of slots in S : Finset (ZMod n) that are occupied after inserting the list A : List (ZMod n) into an initially empty table of…
  • hash_occupied_slots_nilFor any n and offset sequence r : Fin n → ZMod n, hash_occupied_slots n r [] = ∅.

Read back from the Lean

hash_occupied_slots n r A defines the finset of occupied slots in ZMod n resulting from sequentially inserting the elements of the list A : List (ZMod n) into an initially empty hash table ∅ : Finset (ZMod n) of size n, using the probe offsets r : Fin n → ZMod n. At each element a of A, it finds the set of candidate probe indices j : Fin n for which the slot a + r j is not yet in the current occupied set T. If this set of candidates is non-empty, the slot a + r j for the minimal candidate index j (in the canonical ordering of Fin n) is added to T; otherwise, T remains unchanged.

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

/-- Set of occupied slots after inserting a list of elements into an initially empty hash table. -/
def hash_occupied_slots (n : ℕ) (r : Fin n → ZMod n) (A : List (ZMod n)) : Finset (ZMod n) := A.foldl (hash_insert_step n r) ∅
See it in the graphDiscuss this resultChallenge it