hash_probe_expected_cost
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
- mixed_radix_offset_mean_probe_zeroFor every table size n ≥ 2, every probe sequence r : Fin n → ZMod n, and every factor list P, the expected probe cost into an empty table…
- fixed_offset_hash_worst_mean_mixed_radix_primeFor any prime p, any bijective offset sequence r : Fin p → ZMod p, and any load t < p, if linear probing achieves expected probe cost at…
- unit_first_fixed_offset_mean_probe_eq_zeroFor every table size n ≥ 2 with [NeZero n] and every bijective probe sequence r : Fin n → ZMod n with r 0 = 0 and IsUnit (r 1), the…
- 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…
- prime_fixed_offset_tail_prob_two_twoFor any odd prime p and any bijective offset sequence r : Fin p → ZMod p with r 0 = 0, the second tail probability at load t = 2 is…
- prime_fixed_offset_mean_le_of_tail_leFor any prime table size p, offset sequence r : Fin p → ZMod p, and load t, if every probe-cost tail probability under r is bounded by the…
- 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_expected_cost_twoAfter two insertions the expected cost is 1+2/n+(3+[2r₁=0])/n².
- unit_first_fixed_offset_mean_probe_maximum_threeFor a 3-slot hash table (n = 3), every bijective probe sequence r : Fin 3 → ZMod 3 with r 0 = 0 and IsUnit (r 1), and every load t < 3,…
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