形式陈述

哈希表用哈希函数 $h:U\to \{0,\dots ,m-1\}$ 把键映射到含 $m$ 个槽位的数组。不同键可能碰撞，必须由链地址、开放寻址或其他策略处理。负载因子通常为 $\alpha =n/m$。在简单均匀哈希等随机性假设下，链地址查找、插入和删除的期望成本为 $O(1+\alpha )$；开放寻址还依赖探测序列和 $\alpha <1$。最坏情况下所有键碰撞，操作可退化到 $\mathrm{\Theta }(n)$。

直觉

用一个可快速计算的“近似地址”直接跳到键可能所在的小区域，再在碰撞结构中做少量局部工作。

例子与边界

链地址把同槽键放入链表或小容器；开放寻址把所有键留在数组并按探测序列寻找空槽。删除开放寻址元素常需墓碑，否则会截断后续查找路径。扩容并重新哈希可保持负载因子，但单次扩容为线性成本，通常靠摊还分析得到长期常数。密码学哈希强调抗碰撞/抗攻击，普通算法哈希只需分布和速度，目标不同。

推论与应用

哈希表实现字典、集合、缓存和符号表。面对对手可控键时，应使用随机密钥哈希、通用哈希或碰撞树化，不能把平均模型当作无条件最坏保证。

参考资料

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, Introduction to Algorithms, 4th ed., MIT Press, 2022，Ch. 11, hash tables, chaining, and open addressing。
• Robert Sedgewick and Kevin Wayne, Algorithms, 4th ed., Addison-Wesley, 2011，§3.4, hash tables and symbol-table implementations。