处理哈希冲突

虽然理想的哈希函数能将键完美均匀地分布到哈希表的槽位中，避免任意两个键落入同一个位置，但实际情况通常不尽如人意。给定有限数量的槽位 ($m$) 和可能远大于（甚至无限）的键的集合，鸽巢原理告诉我们，冲突（即多个键映射到同一个哈希索引）必然发生。即使使用很好的哈希函数，随着表被填满，冲突发生的可能性也会越来越大。

因此，设计或使用哈希表时的一个基本环节是，制定策略来有效管理这些冲突。如果没有解决策略，每当发生冲突时，我们就会覆盖现有数据，导致哈希表不正确。目标是以一种方式处理冲突，即保持存储和检索的正确性，同时尽量减少性能下降。

存在两种主要的解决哈希冲突的方法：链表法和开放寻址法。

链表法

链表法的思路很直接：我们不要求每个槽位最多只容纳一个元素，而是让哈希表数组中的每个槽位 ($j$) 引用一个数据结构，该结构保存 所有 哈希到索引 $j$ 的元素。最常见的是，这个辅助数据结构是一个链表。

使用链表法的哈希表。槽位 1 和 5 包含单个元素。槽位 3 发生了冲突，将键 B 和键 C 都存储在一个链表中。槽位 0、2、4 和 6 为空。

操作：

1. 插入： 计算哈希索引 $j = h(\text{键})$。将新元素（键值对）插入 table[j] 处的链表。对于添加到链表头部而言，这通常是一个 $O(1)$ 操作。
2. 查找： 计算哈希索引 $j = h(\text{键})$。遍历 table[j] 处的链表，将查找键与链表中每个元素的键进行比较。
3. 删除： 计算哈希索引 $j = h(\text{键})$。在 table[j] 处的链表中查找具有匹配键的元素。如果找到，则将其从链表中移除（标准的链表删除操作）。

性能：

链表法的性能在很大程度上取决于负载因子 $\lambda = n/m$，其中 $n$ 是表中存储的元素数量，$m$ 是槽位（或桶）的数量。链的平均长度是 $\lambda$。

假设哈希函数均匀分布键（简单均匀哈希假设），一次不成功查找的平均时间是 $O(1 + \lambda)$，因为我们需要计算哈希值 ($O(1)$) 并可能遍历平均链长 ($\lambda$)。一次成功查找的平均时间略少，也大约是 $O(1 + \lambda)$。如果槽位数量 $m$ 与元素数量 $n$ 成比例（即 $\lambda$ 保持在一个常数范围内），那么插入、删除和查找操作的平均时间为 $O(1)$。

最坏情况发生在所有键都哈希到同一个槽位时。在这种情况下，哈希表退化为单个链表，查找/删除操作需要 $O(n)$ 时间。这表明了良好哈希函数的重要性，以及在负载因子过高时可能需要调整表大小。

开放寻址法

与链表法不同，开放寻址法将所有元素直接存储在哈希表数组本身中。当发生冲突（即哈希到一个已被占用的槽位 $j$）时，我们系统地探测表中后续的槽位，直到找到一个空槽位。

检查槽位的顺序称为探测序列。哈希函数被有效地扩展，将键和探测次数（第一次尝试为 0，第二次为 1，依此类推）作为输入：$h(\text{键}, i)$，其中 $i = 0, 1, 2, ...$。

存在几种探测策略：

1. 线性探测： 这是最简单的策略。如果初始槽位 $j = h(\text{键}, 0)$ 被占用，我们尝试 $j+1$，然后 $j+2$， $j+3$，依此类推，必要时在表末尾回绕（即，对 $i=0, 1, 2, ...$ 探测 $(h(\text{键}) + i) \pmod{m}$）。

   • 问题： 线性探测存在主聚集问题。随着已占用槽位的块形成，任何哈希到该块的键都需要遍历整个块，并且插入到该块中会使其更长。这会增加平均查找时间。

2. 二次探测： 为了缓解主聚集问题，二次探测使用二次偏移量。探测序列是 $(h(\text{键}) + c_1 i + c_2 i^2) \pmod{m}$，其中 $i=0, 1, 2, ...$，且 $c_1$ 和 $c_2$ ($c_2 \neq 0$) 是常数。一个常见选择是 $h(\text{键}) + i^2 \pmod{m}$。

   • 问题： 虽然它避免了大的连续块（主聚集），但它可能受到次聚集问题的影响。如果两个不同的键哈希到同一个初始槽位，它们将遵循完全相同的探测序列。

3. 双重哈希： 此方法使用第二个独立的哈希函数 $h_2(\text{键})$，以在初始冲突后确定探测的步长。探测序列是 $(h_1(\text{键}) + i \cdot h_2(\text{键})) \pmod{m}$，其中 $i=0, 1, 2, ...$。

   • 好处： 这通常是首选的开放寻址方法，因为它显著减少了主聚集和次聚集。哈希到相同初始槽位的键的探测序列很可能不同，具体取决于 $h_2$ 的结果。必须注意确保 $h_2(\text{键})$ 永远不为零，并且与表大小 $m$ 互质，以确保所有槽位最终都可以被探测到。

示例：线性探测插入

考虑一个大小为 $m=7$ 的表和一个简单的哈希函数 $h(k) = k \pmod{7}$。我们来插入键 15, 22, 8, 1。

1. 插入 15： $h(15) = 15 \pmod{7} = 1$。槽位 1 为空。将 15 放置在索引 1。 Table: [_, 15, _, _, _, _, _]
2. 插入 22： $h(22) = 22 \pmod{7} = 1$。槽位 1 已被 15 占用（冲突！）。 探测 $i=1$: $(1 + 1) \pmod{7} = 2$。槽位 2 为空。将 22 放置在索引 2。 Table: [_, 15, 22, _, _, _, _]
3. 插入 8： $h(8) = 8 \pmod{7} = 1$。槽位 1 已被占用。 探测 $i=1$: $(1 + 1) \pmod{7} = 2$。槽位 2 已被占用。 探测 $i=2$: $(1 + 2) \pmod{7} = 3$。槽位 3 为空。将 8 放置在索引 3。 Table: [_, 15, 22, 8, _, _, _]
4. 插入 1： $h(1) = 1 \pmod{7} = 1$。槽位 1 已被占用。 探测 $i=1$: $(1 + 1) \pmod{7} = 2$。槽位 2 已被占用。 探测 $i=2$: $(1 + 2) \pmod{7} = 3$。槽位 3 已被占用。 探测 $i=3$: $(1 + 3) \pmod{7} = 4$。槽位 4 为空。将 1 放置在索引 4。 Table: [_, 15, 22, 8, 1, _, _]

操作：

• 插入： 使用所选序列进行探测，直到找到一个空槽位。将元素插入那里。如果表变得太满（负载因子接近 1），则需要调整大小（创建更大的表并重新哈希所有现有元素）。
• 查找： 从 $h(\text{键})$ 开始，使用相同的序列进行探测。如果找到元素，则返回它。如果在探测过程中遇到一个空槽位，则该元素不在表中。
• 删除： 这比较复杂。简单地将槽位标记 (token)为空可能会破坏后续查找的探测序列。如果我们在上面的示例中删除了 22（在索引 2），那么稍后查找 8 或 1 时将遇到现在为空的槽位 2，并错误地得出它们不存在的结论。一个常见解决方法是使用特殊的“已删除”标记（有时称为墓碑）来标记槽位。插入可以重用已删除的槽位，但查找必须继续探测它们之后的位置。这会使事情复杂化，如果发生大量删除，可能导致较长的查找时间。可能需要定期重新哈希以清除墓碑。

性能：

开放寻址法的性能对负载因子 $\lambda = n/m$ 非常敏感。与链表法中 $\lambda$ 可以超过 1 不同，在开放寻址法中 $\lambda$ 必须小于 1（您不能存储比槽位更多的项）。当 $\lambda$ 接近 1 时，所需的探测次数会急剧增加，性能急剧下降。例如，在均匀哈希假设下（对于简单的线性/二次探测不切实际，但通过双重哈希近似实现）：

• 不成功查找/插入的平均探测次数：$\approx 1/(1-\lambda)$
• 成功查找的平均探测次数：$\approx (1/\lambda) \ln(1/(1-\lambda))$

为了保持良好性能（平均时间接近 $O(1)$），通过在必要时调整表大小，保持较低的负载因子很重要，线性/二次探测通常低于 0.5，双重哈希可能达到 0.7 或 0.8。开放寻址法可能比链表法具有更好的缓存性能，因为元素在数组中是连续存储的，但它需要更仔细的实现和管理。

选择策略

• 链表法通常更易于实现，特别是删除操作。随着负载因子的增加，其性能下降得更平缓，并且 $\lambda$ 可以大于 1。然而，它需要额外的内存用于指针和链表节点，这也会对缓存局部性产生负面影响。
• 开放寻址法避免了指针的开销，并且可以表现出更好的缓存性能。然而，它实现起来更复杂（尤其是删除），并且随着负载因子接近 1，性能会急剧下降，因此需要通过调整大小来仔细控制 $\lambda$。探测策略的选择也很重要。

在许多标准库实现中（例如 Python 3.6 版本之前的 dict 使用开放寻址法，或 Java 的 HashMap 使用链表法），这些细节对用户是隐藏的。然而，在设计专门的基于哈希的结构或分析依赖它们的算法的性能特征时，理解这些冲突解决机制很有价值。例如，在特征哈希中，冲突意味着不同的特征可能被映射到相同的索引（特征混叠）。虽然有时可以接受甚至对正则化 (regularization)有益，但理解冲突解决有助于我们认识到其中涉及的潜在权衡。