hash_adjacent_count
def
The number of occupied slots whose d-successor is also occupied.
Statement
def hash_adjacent_count (n : ℕ) (d : ZMod n) (T : Finset (ZMod n)) : ℕ- Source
- Unit-first fixed-offset mean-probe extremality; experiments 11670–11680 and arXiv:2610.31363.
- Verified
- 01 Nov 2026
- Axioms
- none listed
- Used by 2
- hash_probe_tail_two_eq_adjacent_meanThe second probe-cost tail equals the expected number of occupied adjacent pairs, divided by the table size.
- 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.
Lean source view module on GitHub
def hash_adjacent_count (n : ℕ) (d : ZMod n) (T : Finset (ZMod n)) : ℕ := (T.filter (fun x => x + d ∈ T)).card