二次探测是 1968 年提出的哈希表构造，至今仍是最简洁、最常用的方案之一。研究者长期猜想，在负载因子 $1-\epsilon$ 时，单次插入的期望时间应为 $O(\epsilon^{-1})$，但至今未能证明任何形如 $f(\epsilon^{-1})$ 的上界。
本文突破性地证明，二次探测的期望插入时间为 $\epsilon^{-(1+o(1))}$，即在 $\epsilon^{-1}$ 的多项式因子上紧匹配猜想，只差一个亚多项式因子。该结果通过对探测序列的细致概率分析，结合负载因子趋近 1 时的极限行为，构造了新的上界技巧。
该证明不仅解决了半个世纪未解的复杂度问题，也为进一步优化哈希表实现提供了理论依据。
博主点评：这篇工作在理论上彻底厘清了二次探测的性能上界，意义非凡。对实际系统的实现者而言，虽然常数因素仍需经验调优，但有了明确的渐近界限，设计更高效的哈希表将更有依据。