AFTD Auto-Formalizing Theoretical Domains

hash_probe_expected_cost

deforiginal

For a table size n with [NeZero n], an offset sequence r : Fin n → ZMod n, and a number of inserted keys t : ℕ, hash_probe_expected_cost n r t is the expected probe cost to insert an additional uniformly random key, defined as the sum over k in Finset.range (n + 1) of hash_probe_tail_prob n r t k.

Statement

noncomputable def hash_probe_expected_cost (n : ℕ) [NeZero n] (r : Fin n → ZMod n) (t : ℕ) : ℝ
Related work
scout/2610-31363-a-sharp-analysis-of-fixed-offset-hash-tables.md:333
Verified
01 Nov 2026
Axioms
none listed
Built on 1
  • hash_probe_tail_probFor a table size n with [NeZero n], an offset sequence r : Fin n → ZMod n, and natural numbers t and k, hash_probe_tail_prob n r t k is…
Used by 9

Read back from the Lean

hash_probe_expected_cost is a definition that takes a non-zero natural number n (via [NeZero n]), a probe offset sequence r : Fin n → ZMod n, and a natural number t (representing the number of elements inserted), and returns the real number defined as the sum over k ∈ {0, ..., n} of hash_probe_tail_prob n r t k. This tail probability hash_probe_tail_prob n r t k is defined as the fraction: (hash_probe_tail_count n r t k : ℝ) / (n : ℝ)^(t + 1) where hash_probe_tail_count n r t k is the number of pairs (h, x) : (Fin t → ZMod n) × ZMod n (out of all n^(t + 1) possible configurations of t hash values h and a query hash value x) such that for every probe step j : Fin n with index j < k, the slot x + r j is in the set of occupied slots obtained by inserting h into the table according to r (i.e., x + r j ∈ hash_occupied_slots n r (List.ofFn h)).

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

/-- Expected probe cost for an additional uniformly hashed key into an n-slot table with t keys inserted using offset sequence r. -/
noncomputable def hash_probe_expected_cost (n : ℕ) [NeZero n] (r : Fin n → ZMod n) (t : ℕ) : ℝ := ∑ k ∈ Finset.range (n + 1), hash_probe_tail_prob n r t k
See it in the graphDiscuss this resultChallenge it