哈希表——哈希如何工作与冲突解决

哈希表通过把每个键哈希到某个数组索引来存储键值对。这样，表就能直接跳到接近正确的位置，而不必把所有已存储的项逐个扫描一遍。

这就是为什么哈希表在平均情况下，查找、插入和删除通常都接近 $O(1)$。但这里有前提：哈希函数必须能把键分布得比较均匀，而且表还需要一套处理冲突的规则。

哈希表的作用是什么

哈希表存储的是键值对，例如 "name" -> "Ada" 或 42 -> "blue"。它主要由两部分组成：

• 一个由槽位或桶组成的数组
• 一个把每个键映射到这些槽位之一的哈希函数

如果数组有 $m$ 个槽位，可以把哈希函数理解为生成一个从 $0$ 到 $m-1$ 的索引。

举一个小整数的例子，规则可以是

$$h(k) = k \bmod 8$$

那么键 $10$ 会进入槽位 $2$，因为 $10 \bmod 8 = 2$。

真实的哈希函数通常设计得更谨慎，尤其是在处理字符串和更大规模数据集时。不过核心思想不变：快速计算出一个索引，然后检查那里存放的项。

为什么哈希冲突不可避免

当两个不同的键映射到同一个槽位时，就发生了冲突。

这很正常，因为表中的槽位数量通常少于可能的键的总数。对于

$$h(k) = k \bmod 8$$

键 $10$、$18$ 和 $26$ 都会映射到槽位 $2$。所以即使函数完全按定义工作，表仍然会遇到需要解决的冲突。

因此，哈希表并不保证每个键都有唯一的槽位。它保证的是：只要冲突处理得当，就能用一种快速方式把搜索范围缩小。

示例：一个表，一次冲突

假设一个表有 $8$ 个槽位，并使用

$$h(k) = k \bmod 8$$

插入键 $10$、$18$ 和 $7$。

首先，$10$ 会进入槽位 $2$，因为 $10 \bmod 8 = 2$。

接着，$18$ 也会哈希到槽位 $2$，于是发生冲突。

然后，$7$ 会进入槽位 $7$，所以这次插入不会冲突。

这里有一个始终不变的有用模式：

1. 对键做哈希。
2. 前往计算出的槽位。
3. 如果那里已经有不同的键，就应用冲突处理规则。

一旦这个模式清楚了，理解两种主要的冲突处理策略就会容易得多。

链地址法 vs. 开放定址法

链地址法在每个槽位保留一个桶

在链地址法中，每个槽位存储的是一个小型条目集合，而不只是一个条目。

如果 $10$ 和 $18$ 都哈希到槽位 $2$，那么桶 $2$ 里可能存放

• $(10, \text{value}_1)$
• $(18, \text{value}_2)$

要查找键 $18$ 时，表会直接跳到桶 $2$，然后只比较这个桶中的条目。

链地址法在概念上很简单，而且删除通常比开放定址法更容易。代价是，如果桶变得很长，操作速度就会变慢。

开放定址法始终在数组内部处理

在开放定址法中，每个数组槽位最多只保存一个条目。如果原本应该放入的槽位已满，表就会按照固定规则去探查其他槽位。

一种常见规则是线性探查：如果槽位 $2$ 被占用，就尝试 $3$，再尝试 $4$、$5$，必要时循环回到数组开头。

这样可以避免单独的桶链表，但相邻的已占用槽位可能会逐渐形成聚集。另一个细节是，查找和删除必须遵守与插入时相同的探查规则。

什么时候说 $O(1)$ 是合理的

哈希表常被描述为在平均情况下具有 $O(1)$ 的查找、插入和删除性能。这个平均情况的说法依赖于几个条件：

• 哈希函数能把键分布得比较均匀
• 负载因子保持在可控范围内
• 冲突处理策略实现正确

负载因子是下面这个比值：

$$\text{load factor} = \frac{\text{number of stored entries}}{\text{number of slots}}$$

如果表变得太满，冲突就会更频繁，性能也会变差。这就是为什么很多实现会在数组逐渐填满时进行扩容。

在最坏情况下，如果太多键堆积到同一区域，性能仍然可能退化到接近 $O(n)$。

哈希表中的常见误区

以为冲突意味着哈希函数失效了

并不是。冲突本来就是预期之中的。真正的问题是，表是否能高效地处理这些冲突。

把 $O(1)$ 当成无条件成立

$O(1)$ 通常说的是平均情况，而不是对每一种输入、每一个时刻都作出的保证。

把这里的哈希和加密混为一谈

在基础数据结构语境中，哈希函数的主要目标是快速索引，而不是保密。这是两种不同的目标。

忘记比较实际的键

两个键可能得到相同的哈希结果。即使已经到达正确的桶或探查位置，表仍然必须检查键本身是否真的匹配。

哈希表的使用场景

只要需要基于键进行快速查找，哈希表就很常用。常见例子包括字典、符号表、缓存、索引，以及统计数据中元素出现频率。

当按键精确查找比保持元素有序更重要时，哈希表非常合适。如果你需要有序遍历、范围查询或查找最接近的值，那么其他数据结构可能更合适。

试一个类似的冲突例子

取一个有 $8$ 个槽位的小数组，并使用 $h(k)=k \bmod 8$。插入几个键，例如 $3$、$11$、$19$ 和 $27$。然后分别用链地址法和线性探查法解决这些冲突。

这个练习会很快把核心思想变得具体起来：冲突不可避免，而冲突处理规则会改变表的行为。如果你想再进一步，可以试着换一个表大小，看看冲突会如何变化。