#CS225

Hashing Basic

核心思想

目标

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

效率

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

  • 一个好的哈希函数 h(key) 应该能非常快速地计算出索引，理想情况下是 常数时间 (Constant Time)，记作 O(1)。
  • 使用索引访问数组中的元素也是一个 O(1) 操作。
  • 因此，找到一个键的值 应该 存储在哪里的 理想 过程，总共只需要 O(1) 的时间 (哈希计算 + 数组访问)。 这整个结构 —— 哈希函数与数组的结合 —— 构成了 哈希表 (Hash Table) 的基础。 它允许我们非常高效地存储和检索与键关联的值，目标是使插入、删除和搜索的平均时间复杂度达到 O(1)。

基于哈希表的字典

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): 如果两个 不同 的键，比如 k1 和 k2，被哈希函数映射到了 相同 的索引 (即 h(k1)=h(k2))，会发生什么？这种情况称为 冲突 (collision)。我们需要相应的冲突解决策略。

理想情况：完美哈希函数

定义

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

  • 属性: 从数学上讲，如果我们考虑键集合 K 和数组索引集合 I=0,1,…,N−1，一个完美哈希函数 h:K→I 具有以下性质：

    • 一对一 (1-to-1 / 单射 / Injective): 没有两个不同的键映射到同一个索引。如果 k1≠k2，那么 h(k1)≠h(k2)。
    • 如果 $ K = N$ (键的数量等于数组大小)，它也是 满射 (onto / Surjective): 数组中的每个索引都被某个键映射到。
    • 一个既是单射又是满射的函数称为 双射 (bijective)。

为何完美很难得

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

  • 需要预知所有键: 通常你需要 预先 知道所有的键集合才能设计一个完美哈希函数。如果键是动态添加或删除的，这通常是不可行的。
  • 巨大或复杂的键空间: 对于非常大或不可预测的键空间 (例如任意字符串或复杂对象)，找到一个完美哈希函数在计算上非常困难或不可能。

实用的哈希函数

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

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

hH:key→i(i∈Z)

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

hC:i→[0,N−1]



1



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

hC(i)=i(modN)



1



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

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

好的哈希函数的特征

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

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

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

    • 每个键都等概率地哈希到数组中 N 个可用槽位的 任何一个。
    • 一个键的哈希值与其他所有键的哈希值是独立的。
    • 形式上，两个不同的键 ki 和 kj 发生冲突的概率是 P(h(ki)=h(kj))=1/N，其中 N 是表的大小。

通用哈希函数

  • 在 CS 225 课程中，我们关注的是 通用哈希函数 (General Purpose Hash Functions)。它们被设计成能在各种不同的键和键空间上都表现得相当好，而无需为每个特定应用进行专门调整。
  • 当实际使用的键空间远小于潜在的键空间，或者当表的大小 N 与键的数量 $ K $ 相差很大时，创建好的通用哈希函数会更加困难。
  • 还存在其他类型的哈希函数，例如 密码学哈希函数 (Cryptographic Hash Functions)，它们具有更严格的要求 (如抗碰撞性、抗原像攻击性等)，用于安全应用。它们的目标不同，并且通常比典型哈希表中使用的哈希函数慢。

例子：字符串哈希

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

  • 输入: “Alice was beginning to get very tired of”
  • 输出: “iweitegr” (幻灯片 59)
  • 输入: “sitting by her sister on the bank, and “
  • 输出: “-pthoes” (幻灯片 60)
  • 输入: https://en.wikipedia.org/wiki/Main_Page
  • 输出: snkdg/-e (幻灯片 63)
  • 输入: https://en.wikipedia.org/wiki/Battle_of_
  • 输出: snkdg/_i (幻灯片 64)

这展示了 映射 的过程。然而，请注意，这两个非常相似的维基百科 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)。

核心思想

  • 哈希表的数组本身不直接存储键值对。
  • 数组的每个槽位 (slot) 存储一个指向链表 (Linked List) 的指针 (或者直接是链表头节点)。
  • 当一个键 k 被哈希到索引 i 时，我们将这个键值对 (k,v) 插入到数组索引 i 处的链表中。
  • 所有哈希到同一个索引 i 的键值对都会被存储在同一个链表中。

示例

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

  • 键集合 S: { 16, 8, 4, 13, 29, 11, 22 } (共 n=7 个元素)
  • 数组大小 N: 7 (索引 0 到 6)
  • 哈希函数 h(k): k(mod7) (取 k 除以 7 的余数)

插入过程：

  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。

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

性能分析

  • 负载因子 (Load Factor) α : 衡量哈希表“满”的程度。

α=nN=存储的元素数量数组大小



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)，因为所有元素都必须存储在哈希表数组内部。

核心思想

  • 所有键值对 (k,v) 都直接存储在数组中。

  • 当要插入一个键 k，计算其哈希值 h(k)=i。

    • 如果索引 i 为空，则将 (k,v) 放入 array[i]。
    • 如果索引 i 已被占用 (发生冲突)，则按照一个预定义的探测序列 (Probe Sequence) 查找下一个可用的槽位，直到找到一个空槽位为止。

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

这是最简单的探测策略。

  • 探测序列: 如果 h(k) 位置冲突，则尝试 h(k)+1, h(k)+2, h(k)+3, … (所有索引都对数组大小 N 取模)。

尝试索引: (h(k)+j)(modN),for j=0,1,2,…

  • 示例跟踪 (假设使用前述例子的初始状态):

    • 插入 16: h(16)=2，放入 array[2]。(已有)
    • 插入 8: h(8)=1，放入 array[1]。(已有)
    • 插入 4: h(4)=4，放入 array[4]。(已有)
    • 插入 13: h(13)=6，放入 array[6]。(已有)
    • 插入 29: h(29)=1，array[1] 被 8 占用。尝试 (1+1)%7=2，array[2] 被 16 占用。尝试 (1+2)%7=3，array[3] 为空，放入 array[3]。
    • 插入 11: h(11)=4，array[4] 被 4 占用。尝试 (4+1)%7=5，array[5] 为空，放入 array[5]。
    • 插入 22: h(22)=1，array[1] 被 8 占用。尝试 (1+1)%7=2，被 16 占用。尝试 (1+2)%7=3，被 29 占用。尝试 (1+3)%7=4，被 4 占用。尝试 (1+4)%7=5，被 11 占用。尝试 (1+5)%7=6，被 13 占用。尝试 (1+6)%7=0，array[0] 为空，放入 array[0]。

开放寻址法的约束

  • 由于所有元素必须放在数组内，数组大小 N 必须大于或等于元素的数量 n。
  • 负载因子 α=n/N 必须小于等于 1 (α≤1.0)。
  • 实际应用中，为了保持良好性能，α 通常需要远小于 1 (例如 ≤0.5 或 ≤0.7)。

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

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

  • 描述 (Description): 已占用的槽位会倾向于连接在一起形成连续的块 (clusters)。当一个新的键哈希到这个块中的任何位置时，它最终会被添加到块的末尾，从而使块变得更长。这就像滚雪球一样，一旦形成一个小的聚集块，它就更有可能增长。
  • 后果: 导致查找和插入时需要探测的次数显著增加，性能下降。即使在负载因子较低 (α 较小) 时，也可能出现聚集。
  • 补救措施 (Remedy): 使用更智能的探测策略，如二次探测 (Quadratic Probing) 或 双重哈希 (Double Hashing)。

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

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

核心思想

  • 使用两个哈希函数：

    • h1(k): 计算初始的哈希位置 (与之前一样)。
    • h2(k): 计算探测时的步长 (step size)。这个步长对于不同的键应该是不同的。

  • 探测序列: 如果 h1(k) 位置冲突，则尝试 h1(k)+1×h2(k), h1(k)+2×h2(k), … (所有索引都对 N 取模)。

第 i 次探测 (从 i=0 开始): h(k,i)=(h1(k)+i×h2(k))(modN)



1
2
3
4



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

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

  • 哈希函数:

    • h1(k)=k(mod7)
    • h2(k)=5−(k(mod5))

  • 插入过程 :

    • 16, 8, 4, 13 的 h1 值分别是 2, 1, 4, 6，直接插入。

    • 插入 29:

      • h1(29)=1 (冲突，array[1] 已有 8)。
      • h2(29)=5−(29(mod5))=5−4=1。(幻灯片 39)
      • 第一次探测 (i=1): (h1(29)+1×h2(29))(mod7)=(1+1×1)(mod7)=2 (冲突，array[2] 已有 16)。
      • 第二次探测 (i=2): (h1(29)+2×h2(29))(mod7)=(1+2×1)(mod7)=3 (空)，将 29 放入 array[3]。(幻灯片 40)

    • 插入 11:

      • h1(11)=4 (冲突，array[4] 已有 4)。
      • h2(11)=5−(11(mod5))=5−1=4。(幻灯片 42)
      • 第一次探测 (i=1): (h1(11)+1×h2(11))(mod7)=(4+1×4)(mod7)=8(mod7)=1 (冲突，array[1] 已有 8)。
      • 第二次探测 (i=2): (h1(11)+2×h2(11))(mod7)=(4+2×4)(mod7)=12(mod7)=5 (空)，将 11 放入 array[5]。(幻灯片 44)

    • 插入 22:

      • h1(22)=1 (冲突)。
      • h2(22)=5−(22(mod5))=5−2=3。
      • 第一次探测 (i=1): (1+1×3)(mod7)=4 (冲突)。
      • 第二次探测 (i=2): (1+2×3)(mod7)=7(mod7)=0 (空)，将 22 放入 array[0]。(幻灯片 43)

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

运行时间分析总结

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

  • 重要提示: 不需要记忆这些复杂的公式！

8d30d2fb54f12d81bc88170efe03a6c.png

  • 需要观察的趋势:

    • 当负载因子 α 增加时:

      • 对于所有策略，查找所需的探测次数 (即运行时间) 都会增加。哈希表越满，性能越差。
      • 对于线性探测和双重哈希 (开放寻址法)，当 α 接近 1 时，性能会急剧恶化，探测次数趋向无穷大。(见幻灯片 48-52 的图示)

    • 当负载因子 α 保持常数时: (幻灯片 47)

      • 对于拉链法 (Separate Chaining)，平均查找时间是 O(1+α)。如果 α 是常数，那么平均查找时间就是 O(1)。
      • 对于开放寻址法，即使 α 是常数，性能也依赖于这个常数具体是多少，特别是当 α 较大时。

总结:

  • 哈希表通过哈希函数和数组提供潜在的 O(1) 平均时间复杂度。
  • 冲突是不可避免的，需要通过冲突解决策略处理。
  • 拉链法使用链表，实现简单，α 可以大于 1，平均性能 O(1+α)。

  • 开放寻址法 (如线性探测、双重哈希) 将所有元素存入数组，α≤1。

    • 线性探测简单但有主聚集问题。
    • 双重哈希通过第二个哈希函数确定步长，能有效缓解聚集。
  • 所有策略的性能都依赖于负载因子 α。保持较低的 α (特别是对于开放寻址法) 或使用拉链法并在 α 过大时调整数组大小 (rehashing) 是维持哈希表高性能的关键。

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

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

问题

  • 如果数组填满了 (对于开放寻址法，这意味着 α=1)，或者即使没完全填满，但负载因子 α 变得太高 (例如，对于开放寻址法 α>0.7，或者对于拉链法 α>1.0 或某个预设阈值)，会导致性能显著下降。

解决方案：Rehashing

Rehashing 的过程：

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

Rehashing 的成本

  • Rehashing 操作本身是昂贵的，因为它需要遍历所有 n 个元素，并为每个元素重新计算哈希值和执行插入操作。这个过程的时间复杂度是 O(n+N′)，通常简化为 O(n) (假设 N′ 与 n 成正比)。
  • 但是，Rehashing 不会经常发生。如果我们每次都将数组大小加倍，那么 Rehashing 的成本可以摊销 (Amortized) 到每次插入操作上。

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

  • 在 Rehashing 中: 虽然 Rehashing 操作本身耗时 O(n)，但由于它不常发生，我们可以把这次大的开销“分摊”到导致 Rehashing 的多次 (通常是 O(n) 次) 插入操作上。
  • 结果: 尽管单次插入的最坏情况 (Worst Case) 时间复杂度因为可能触发 Rehashing 而是 O(n)，但摊销后 (Amortized) 的插入时间复杂度可以保持在 O(1) (假设负载因子 α 保持在合理范围内)。

运行时间对比表

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

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

解读:

  • 哈希表的核心优势: 平均 (摊销) 情况下的 O(1) 查找和插入速度。这是它相比于 AVL 树 (O(log⁡n)) 和链表 (O(n) 查找) 的最大亮点。
  • 哈希表的弱点: 最坏情况下性能可能退化到 O(n)。这可能发生在哈希函数选择不当导致大量冲突，或者负载因子过高时。
  • AVL 树: 提供稳定的 O(log⁡n) 性能，无论是平均还是最坏情况。它还支持有序操作。
  • 链表: 插入快 (如果知道位置)，但查找慢。
  • 空间: 三者空间复杂度都是线性的 O(n)。哈希表可能需要比实际元素数 n 更多的空间 (取决于负载因子 α=n/N)。AVL 树和链表每个元素都需要额外的指针开销。

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

哪种冲突解决策略更好？

  • 存储大型记录 (Big Records): 如果每个 (key, value) 对中的 value 非常大，拉链法 (Separate Chaining / Open Hashing) 可能更好。因为开放寻址法需要把整个记录直接存在数组里，大的记录可能导致数组快速填满或移动成本高。拉链法只需要在数组中存储指向记录的指针 (或链表节点)，实际的大记录可以存在链表中，减少数组本身的内存占用和移动开销。
  • 结构速度 (Structure Speed): 如果追求极致速度，并且可以接受较低的负载因子，双重哈希 (Double Hashing / Closed Hashing) 通常更快。因为它避免了链表操作的开销 (指针跳转、节点分配 / 释放)，缓存局部性 (cache locality) 也可能更好。

哈希表取代了什么？

  • 哈希表常常作为列表 (List) 或 AVL 树 (AVL) 的替代方案，用于实现字典 (Dictionary) 或 集合 (Set) ADT (抽象数据类型)，特别是当主要需求是快速的插入、删除和查找，并且不需要维护元素的顺序时。

哈希的约束 vs. BST

  • 哈希表的约束:

    • 必须能直接提供完整的键 (key) 来进行查找。哈希函数 h(k) 需要键 k 作为输入。你不能只给一部分键或者一个范围来查找。
    • 无序性: 哈希表不保证元素的任何特定顺序。遍历哈希表得到的元素顺序通常是混乱的，取决于哈希函数和冲突解决。

  • BST (如 AVL) 的优势:

    • 有序性: BST 本身就是有序结构。可以高效地进行中序遍历得到排序好的元素。
    • 范围查询 (Range Queries): 可以高效查找某个范围内的所有键。
    • 邻近查找 (Nearest Neighbor): 可以高效地找到小于或大于某个给定值的最接近的键 (例如，使用 lower_bound, upper_bound)。(幻灯片 40)

为什么还要讨论 BST？

  • 正是因为 BST (如 AVL 树) 提供了哈希表无法提供的有序性相关操作 (范围查询、邻近查找、有序遍历)，所以在需要这些功能的场景下，BST 是更好的选择。理解哈希表的局限性，才能更好地选择合适的数据结构。

C++ STL 中的体现

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

  • std::map :

    • 通常基于平衡二叉搜索树 (Balanced BST) 实现 (例如红黑树)。
    • 提供 operator[], insert, erase 等操作，时间复杂度为 O(log⁡n)。
    • 支持有序操作: 提供 lower_bound(key) (查找第一个 大于等于 key 的元素) 和 upper_bound(key) (查找第一个 小于 key 的元素)，这两个操作依赖于内部的有序结构。
    • 遍历 `std::map