#CS225

Hashing Basic

核心思想

目标

  1. 定义键空间 (Keyspace): 我们首先要确定我们可能想要存储的所有可能键的集合。这个 keyspace 是一个形式化的、通常是数学上的描述。键可以是任何东西 —— 学生 ID (整数)、姓名 (字符串)、坐标 (数值对) 等。我们用 $k$ 来表示一个任意的键。
  2. 将键映射到整数: 核心目标是使用一个特殊的函数，称为 哈希函数 (Hash Function)，记作 $h(k)$，将来自我们键空间的任何键 $k$ 转换成一个小的整数。具体来说，我们希望将其映射到一个固定大小范围内的索引，通常代表数组中的位置。如幻灯片 4 所示，这个映射是 $h(key): key \rightarrow \mathbb{N}$，其中 $\mathbb{N}$ 代表自然数 (或者更具体地说，是有效索引的集合)。

效率

使用哈希的一个关键动机是速度。

基于哈希表的字典

C++ 上下文

Slides 展示了在 C++ 中使用类似字典 (Dictionary) 的数据结构的典型客户端代码：



1
2



1 Dictionary<KeyType, ValueType> d;
2 d[k] = v;

这看起来非常像你使用 std::map 或 std::unordered_map (后者通常用哈希表实现) 的方式。KeyType 是键的类型，ValueType 是值的类型，d 是字典对象，k 是一个键，v 是与该键关联的值。这个接口允许存储 (键, 值) 对。

哈希表的组成部分

哈希表可以分解为三个基本组成部分：

  1. 哈希函数 (A hash function): 如我们所讨论的，它将键映射到数组索引。
  2. 数组 (An array): 用于存储数据 (或指向数据 / 值的指针) 的基础数据结构。
  3. 冲突解决策略 (Collision Resolution Strategy): 如果两个 不同 的键，比如 $k_1$ 和 $k_2$，被哈希函数映射到了 相同 的索引 (即 $h(k_1) = h(k_2)$)，会发生什么？这种情况称为 冲突 (collision)。我们需要相应的冲突解决策略。

理想情况：完美哈希函数

定义

完美哈希函数 (Perfect Hash Function) 是一种理想情况。对于一个 给定 的键集合，完美哈希函数将每个键映射到数组界限内的一个 唯一 索引，且没有任何冲突。(幻灯片 21-28)

为何完美很难得

完美哈希函数虽然好，但在通用场景下通常不实用或无法构建：

实用的哈希函数

既然完美哈希通常遥不可及，我们就使用旨在“足够好”的实用哈希函数。这些函数通常包含两个部分：

  1. 哈希 (A Hash): 这部分接受输入的 key (可能很复杂，如字符串或对象)，并将其转换为一个整数 $i$。这个整数可能非常大，也可能是正数或负数。我们称这个函数为 $h_H$。

$$ h_H: key \rightarrow i \quad (i \in \mathbb{Z}) $$

  1. 压缩 (Compression): 这部分接受哈希步骤产生的可能很大或为负的整数 $i$，并将其映射到一个有效的数组索引，通常在范围 $[0, N-1]$ 内，其中 $N$ 是哈希表数组的大小。我们称这个函数为 $h_C$。

$$ h_C: i \rightarrow [0, N-1] $$



1



一个非常常见的压缩函数是取模运算符 (modulo operator)：

$$ h_C(i) = i \pmod N $$



1



(需要注意在某些编程语言中取模运算对负数的处理方式；通常使用 `(i % N + N) % N` 来确保结果非负)。

整个哈希函数是这两部分的组合：$h(key) = h_C(h_H(key))$。

好的哈希函数的特征

什么使得一个哈希函数是“好的” (即使不完美)？

  1. 计算时间 (Computation Time): 计算必须快，理想情况下是 $O(1)$。
  2. 确定性 (Deterministic): 同一个键 总是 必须产生相同的哈希输出。如果 $k_1 == k_2$，那么必须有 $h(k_1) == h(k_2)$。如果它是随机的，我们就永远无法可靠地找回我们的数据！

  3. 满足简单均匀散列假设 (SUHA / Simple Uniform Hashing Assumption): 这是用于分析哈希表性能的一个理论理想。它假设：

通用哈希函数

例子：字符串哈希

这些幻灯片演示了将长输入 (来自文本或 URL 的 40 个字符的字符串) 哈希成较短的、固定长度的输出 (8 个字符) 的想法。所示的方法 (例如，每隔 5 个字符取一个) 是哈希函数 ($h_H$ 部分) 的一个 简单示例。

这展示了 映射 的过程。然而，请注意，这两个非常相似的维基百科 URL 产生的输出也非常相似 (snkdg/ 前缀)。这可能表明这个特定的简单哈希方法在广泛分散相似键方面做得不好，如果略有不同的键很常见，则可能导致冲突。这突显了为什么设计 好的 哈希函数具有挑战性。

Collision Handling 冲突解决策略

一个完整的哈希表包含：

  1. 哈希函数 (Hash Function) $h(k)$: 将键 (key) 映射到数组索引。
  2. 数组 (Array): 底层的数据存储结构。
  3. 冲突解决策略 (Collision Resolution Strategies): 定义当两个不同的键哈希到同一个数组索引时该如何处理。这是不可避免的，除非使用完美的哈希函数，而这在大多数情况下是不现实的。

现在，我们将重点讨论第三部分：冲突解决策略。主要有两种方式：拉链法 (Separate Chaining) 和 开放寻址法 (Open Addressing / Probe-based Hashing)。

冲突处理策略一：拉链法 (Separate Chaining)

这是处理冲突的一种非常直观和常用的方法，也称为开放散列 (Open Hashing)。

核心思想

示例

让我们跟踪一下幻灯片中的例子：

插入过程：

  1. h(16) = 16 % 7 = 2 -> 将 16 插入到索引 2 的链表。
  2. h(8) = 8 % 7 = 1 -> 将 8 插入到索引 1 的链表。
  3. h(4) = 4 % 7 = 4 -> 将 4 插入到索引 4 的链表。
  4. h(13) = 13 % 7 = 6 -> 将 13 插入到索引 6 的链表。
  5. h(29) = 29 % 7 = 1 -> 索引 1 发生冲突！将 29 插入到索引 1 的链表中 (通常在链表头部或尾部)。现在索引 1 的链表包含 8 和 29。
  6. h(11) = 11 % 7 = 4 -> 索引 4 发生冲突！将 11 插入到索引 4 的链表中。现在索引 4 的链表包含 4 和 11。
  7. h(22) = 22 % 7 = 1 -> 索引 1 再次发生冲突！将 22 插入到索引 1 的链表中。现在索引 1 的链表包含 8, 29 和 22。

最终，数组的每个索引指向一个链表，链表中包含了所有哈希到该索引的元素。空索引指向空链表 (用 $\phi$ 表示)。

性能分析

$$ \alpha = \frac{n}{N} = \frac{\text{存储的元素数量}}{\text{数组大小}} $$



1
2
3
4
5
6
7
8
9
10



在拉链法中，$\alpha$ 代表了每个链表的**平均长度**。$\alpha$ 可以大于 1 (即链表平均长度可以超过 1)。($\alpha \Rightarrow \text{unbounded}$) -   **插入 (Insert):**

- 计算哈希值: $O(1)$
- 在链表头部插入: $O(1)$
- 所以，插入操作通常是 $O(1)$。 -   **查找 / 删除 (Remove / Find):**

- 计算哈希值: $O(1)$
- 在对应索引的链表中搜索: 平均情况下需要检查链表中的 $\alpha$ 个元素 (假设满足 SUHA)。最坏情况下，所有 $n$ 个元素都哈希到同一个索引，需要在链表中检查 $n$ 个元素。
- **最坏情况 (Worst Case):** $O(n)$
- **平均情况 (Average Case) (SUHA):** $O(1 + \alpha)$。计算哈希是 $O(1)$，遍历链表平均是 $O(\alpha)$。如果 $\alpha$ 是一个常数 (例如，我们通过调整数组大小 N 使得 $N$ 与 $n$ 成正比，保持 $\alpha$ 在一个合理的范围内，比如 $\alpha \approx 1$)，那么平均查找时间就是 $O(1)$。 -   **开放散列 (Open Hashing):** 因为元素存储在链表中，而不是必须在数组内部，所以 $\alpha$ 可以大于 1，因此称为开放散列。

冲突处理策略二：开放寻址法 (Probe-based Hashing / Open Addressing)

这是处理冲突的另一种主要方法，也称为闭合散列 (Closed Hashing)，因为所有元素都必须存储在哈希表数组内部。

核心思想

示例一：线性探测 (Linear Probing)

这是最简单的探测策略。

$$ \text{尝试索引: } (h(k) + j) \pmod N, \quad \text{for } j = 0, 1, 2, … $$

开放寻址法的约束

线性探测的问题：主聚集 (Primary Clustering)

线性探测虽然简单，但有一个严重的问题：

示例二：双重哈希 (Double Hashing)

这是一种更高级的开放寻址探测策略，旨在减少聚集问题。

核心思想

$$ \text{第 } i \text{ 次探测 (从 } i=0 \text{ 开始): } h(k, i) = (h_1(k) + i \times h_2(k)) \pmod N $$



1
2
3
4



-   关键在于 $h_2(k)$ 的选择：

    -   $h_2(k)$ 的值不能为 0。
    -   $h_2(k)$ 的**值应该与 $N$ 互质** (没有公约数)，以确保探测序列能覆盖所有槽位 (如果需要)。通常选择 $N$ 为素数，并让 $h_2(k)$ 的值域在 $[1, N-1]$。
示例

双重哈希通过使用依赖于键本身的步长，使得不同键即使初始哈希位置相同，它们的探测序列也会不同，从而大大减少了线性探测中的主聚集问题。

运行时间分析总结

以下总结了在 SUHA (简单均匀散列假设) 下，不同策略进行查找操作 (find(key)) 时期望的探测次数。

8d30d2fb54f12d81bc88170efe03a6c.png

总结:

动态调整大小：Rehashing (再哈希)

我们已经看到负载因子 $\alpha$ 对性能有巨大影响。那么，当哈希表变得太满 (即 $\alpha$ 超过某个阈值，比如 0.6 或 0.7) 时，我们该怎么办？答案是 Rehashing (再哈希)。

问题

解决方案：Rehashing

Rehashing 的过程：

  1. 分配新数组: 创建一个更大的新数组。通常，新数组的大小 $N’$ 是旧数组大小 $N$ 的两倍左右 (或者选择大于 $2N$ 的下一个素数，这对于某些哈希函数和探测策略效果更好)。
  2. 更新哈希函数: 由于数组大小变了 (从 $N$ 变为 $N’$)，我们的哈希函数 (特别是压缩部分) 通常也需要更新。例如，如果原来使用 $h(k) = k \pmod N$，现在需要使用 $h’(k) = k \pmod{N’}$。
  3. 复制并重新插入元素: 遍历旧哈希表中的所有元素。对于每个元素，使用新的哈希函数 $h’(k)$ 计算它在新数组中的位置，并将其插入到新数组中 (如果新位置发生冲突，则根据冲突解决策略处理)。这个过程不是简单地把旧数组的数据复制到新数组的相同索引，而是需要重新计算哈希值并找到新位置。
  4. 释放旧数组: 一旦所有元素都迁移到新数组，就可以释放旧数组的内存。

Rehashing 的成本

摊销时间复杂度 (Amortized Time Complexity)

运行时间对比表

这张表比较了哈希表 (Hash Table)、AVL 树 (自平衡二叉搜索树) 和链表 (Linked List) 在查找、插入操作上的时间复杂度以及空间复杂度。

操作 复杂度类型 哈希表 (Hash Table) AVL 树 (AVL) 链表 (Linked List)
查找 (Find) 摊销 (Amortized) $O(1)$ (假设 $\alpha$ 合理) $O(\log n)$ $O(n)$
  最坏 (Worst Case) $O(n)$ (所有元素冲突) $O(\log n)$ $O(n)$
插入 (Insert) 摊销 (Amortized) $O(1)$ (假设 $\alpha$ 合理, 包含 Rehashing 摊销) $O(\log n)$ $O(1)$ (头插 / 尾插)
  最坏 (Worst Case) $O(n)$ (触发 Rehashing 或严重冲突) $O(\log n)$ $O(1)$ (头插 / 尾插)
存储空间 (Storage)   $O(n+N) \approx O(n)$ (通常 $N$ 与 $n$ 成比例) $O(n)$ (每个节点存数据 + 指针) $O(n)$ (每个节点存数据 + 指针)

解读:

哈希表 vs. BST (AVL) 及其他讨论

哪种冲突解决策略更好？

哈希表取代了什么？

哈希的约束 vs. BST

为什么还要讨论 BST？

C++ STL 中的体现

C++ 标准模板库 (STL) 很好地体现了这两种结构的选择：