hash_occupy_count
The 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 size n using offset sequence r : Fin n → ZMod n, defined as (hash_occupied_slots n r A ∩ S).card.
Statement
def hash_occupy_count (n : ℕ) (r : Fin n → ZMod n) (S : Finset (ZMod n)) (A : List (ZMod n)) : ℕ- Defined in
- arXiv:2610.31363 Definition 3.1
- Verified
- 23 Oct 2026
- Axioms
- none listed
- Built on 1
- 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…
- Used by 4
- hash_potential_of_length_eqFor any sequence A of length t, the potential hash_potential n r S t A equals the number of slots in S occupied by A, hash_occupy_count n…
- hash_occupy_count_nilFor any n, r : Fin n → ZMod n, and S : Finset (ZMod n), hash_occupy_count n r S [] = 0.
- hash_fully_occupied_seqsThe set of sequences A : Fin t → ZMod n such that hash_occupy_count n r S (List.ofFn A) = S.card, filtering Finset.univ.
- hash_potentialFor a table of size n, offset sequence r, slot subset S, target sequence length t, and prefix A, the potential hash_potential n r S t A is…
Read back from the Lean
hash_occupy_count n r S A is a definition that computes the number of elements in a given set of slots S : Finset (ZMod n) that are occupied after sequentially inserting the elements of a list A : List (ZMod n) into an initially empty hash table (modeled as a subset of ZMod n) of capacity n, using the probing offset function r : Fin n → ZMod n.
At each step, for an element a from A and current occupied set T, the set of candidate indices {j : Fin n | a + r j ∉ T} is considered: if non-empty, the slot a + r j_min corresponding to the minimal candidate index j_min is added to T; if empty (all probed slots are already occupied), T is unchanged. The final value is the cardinality of the intersection of the resulting set of occupied slots with S.
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 number of slots in S occupied after inserting sequence A. -/ def hash_occupy_count (n : ℕ) (r : Fin n → ZMod n) (S : Finset (ZMod n)) (A : List (ZMod n)) : ℕ := (hash_occupied_slots n r A ∩ S).card