哈希表：哈希函数、冲突处理与装载因子
如果说折半查找是“利用有序性”来加速查找，那么哈希表代表的则是另一条完全不同的路线：
我不按大小比较，也不沿树路径逐步缩小范围，而是想办法把键直接映射到一个位置上，争取一次就找到。
这正是哈希表最吸引人的地方。它在平均意义上，插入、删除、查找都可以做到接近 O(1)。也正因为这种极强的常数级访问能力，哈希表几乎是现代程序里最常见的基础结构之一：
- 字典；
- 映射；
- 集合；
- 缓存；
- 去重；
- 频次统计；
- 索引定位。
但哈希表之所以有这种速度，并不是凭空来的，它背后依赖一整套设计：哈希函数怎么选、冲突怎么处理、什么时候扩容、装载因子如何控制。理解这些，才能真正理解为什么哈希表“平均很快”，又为什么它并不是没有代价的万能结构。
一、什么是哈希表
哈希表可以先理解成：
通过哈希函数，把键映射到表中的某个位置，从而支持快速查找、插入和删除的结构。
也就是说，哈希表的核心不是“顺序”，而是“映射”。
例如：
- 给定一个键
key； - 通过某个函数
hash(key)计算得到一个下标； - 再去这个位置存储或查找对应值。
如果理想情况下不同键都能均匀落在不同位置，那么查找就会非常快。
二、为什么哈希表查找能接近 O(1)
因为它不需要像顺序查找那样一个个比较，也不需要像 BST 那样沿路径逐层判断，而是希望：
- 键一进来就算出位置；
- 直接访问目标桶或槽位；
- 快速定位对应元素。
所以哈希表最本质的性能来源是：
用额外空间和良好的映射函数，换取近乎直接访问的能力。
三、什么是哈希函数
哈希函数是哈希表的核心组件。它的作用是：
把任意键值映射到有限范围的数组下标上。
一个好的哈希函数通常希望做到：
- 计算快；
- 分布尽量均匀；
- 尽量减少不同键落到同一位置的概率；
- 对常见输入模式不过于敏感。
例如整数键可以直接取模，字符串键通常要基于字符组合计算散列值。
哈希表好不好用，很多时候首先就取决于哈希函数设计得是否合理。
四、为什么冲突不可避免
这是哈希表必须正视的现实。
因为：
- 键的集合理论上可能非常大；
- 但哈希表数组大小总是有限的；
- 不同键最终映射到同一位置，是必然会发生的。
这种现象就叫哈希冲突。
也就是说，哈希表真正需要解决的问题不是“如何完全没有冲突”，而是：
冲突发生后，如何仍然保持查找、插入和删除足够高效。
五、冲突处理的经典方式有哪些
最常见的通常有两大类。
1. 开放定址法
如果某个位置被占了，就继续按某种探测规则往后找空位。
常见形式包括：
- 线性探测；
- 二次探测；
- 双重哈希。
它的特点是：
- 所有元素都存放在同一个数组里；
- 访问局部性通常较好；
- 但删除处理和聚集问题需要特别注意。
2. 链地址法
数组的每个位置不直接只放一个元素，而是挂一条链表或桶结构。发生冲突时，把多个键值对放到同一个桶里。
它的特点通常是：
- 实现相对直观；
- 删除更自然；
- 对装载因子容忍度更高；
- 现代很多语言哈希表底层都采用这类思路，并在桶里进一步做优化。
六、什么是装载因子
装载因子通常记作：
1 | α = 元素个数 / 哈希表桶数 |
它反映的是：
- 哈希表当前有多满；
- 冲突概率大致会不会上升；
- 性能是否可能开始下降。
例如：
- 装载因子很低，说明表比较空，冲突较少；
- 装载因子越来越高，冲突通常会越来越明显。
所以装载因子是衡量哈希表性能状态的一个非常关键的指标。
七、为什么哈希表需要扩容
因为随着元素越来越多：
- 冲突会增加；
- 查找链变长，或探测次数增多；
- 平均
O(1)可能逐渐恶化。
于是很多实现会在装载因子超过某个阈值时自动扩容。扩容通常意味着：
- 申请更大的桶数组；
- 重新把旧元素根据新容量计算位置；
- 再全部搬过去。
这个过程通常叫rehash 或重哈希。
八、为什么重哈希代价不低但仍然值得做
因为虽然某一次扩容很贵，但如果不扩容，之后很长一段时间的所有操作都会因为冲突增多而变慢。
这和前面讲动态数组扩容的均摊分析很像：
- 平时操作很快；
- 偶尔一次扩容比较贵；
- 但长期平均下来仍然是值得的。
所以哈希表的“平均 O(1)”背后，往往默认了：
- 哈希函数合理；
- 冲突处理得当；
- 装载因子被控制在合适范围。
九、哈希表和树结构相比有什么不同
1. 哈希表
- 平均查找快；
- 不维护顺序；
- 不适合范围查询；
- 迭代顺序通常不稳定。
2. BST / 红黑树
- 查找通常是
O(log n)； - 维护有序性；
- 适合范围查询和有序遍历；
- 代价是单次常数往往更高。
所以哈希表不是“更快的树”，而是针对“只关心键是否存在或键值映射”的问题做了极致优化。
十、哈希表最典型的应用场景有哪些
几乎到处都是，例如：
- 字典和映射；
- 集合判重；
- 词频统计；
- 缓存索引；
- 数据去重；
- LRU 缓存中的键到节点映射；
- 业务系统中各种按主键快速索引。
只要问题的味道是：
- 是否存在；
- 对应值是什么；
- 频次是多少；
- 快速按键定位；
那哈希表通常都是首选之一。
十一、哈希表的局限是什么
1. 不保序
它不适合做有序遍历和范围检索。
2. 性能依赖哈希函数和数据分布
输入模式不好时，冲突可能严重。
3. 最坏情况可能退化
如果冲突极端集中，复杂度可能明显上升。
4. 扩容和重哈希代价不小
只是被均摊掉了，不代表没有。
所以哈希表很强，但它的强大通常是“平均意义上的、建立在设计合理前提上的强大”。
十二、学习哈希表时最容易踩的坑
1. 误以为哈希表绝对 O(1)
更准确地说，通常是平均或期望意义上的接近 O(1)。
2. 只会用语言自带字典，不理解冲突处理
这样就很难真正理解性能边界。
3. 忽略装载因子和扩容影响
这会让人误以为哈希表是无成本增长的。
4. 把哈希表用到需要顺序性的场景
这会导致结构选择方向一开始就错了。
总结
哈希表的重要性，不只是因为它常用，而是因为它代表了一种非常激进且成功的查找优化思路：用映射和空间换速度。真正值得先建立起来的，是这些核心认识：
- 哈希表通过哈希函数把键映射到桶位置，从而支持快速查找；
- 冲突不可避免，关键在于如何处理冲突；
- 开放定址法和链地址法是最经典的两大路线；
- 装载因子直接影响冲突程度和整体性能；
- 扩容与重哈希是哈希表维持平均高性能的重要机制；
- 真正学会哈希表，不是只会用
map，而是知道它为什么快、什么时候会慢、又不适合解决哪些问题。
把这一篇理解透之后，后面再去学字符串匹配、跳表、布隆过滤器和缓存结构时，你会更容易把哈希表看成一个基础能力组件，而不只是一个“存键值对的容器”。
参考资源：