Hash tables

高级数据结构：哈希表 (3.10.3)

你好！欢迎来到计算机科学中最强大的数据结构之一：哈希表 (Hash Table) 的学习部分。如果你想要一种几乎可以瞬间存取数据的方法，这就是你的终极解决方案！我们将深入剖析它的工作原理，重点研究使其如此高效的巧妙数学运算，并探讨当出现“故障”（即哈希冲突）时该如何处理。

1. 哈希表的概念及其用途

想象一下你正在管理一个巨大的邮局。当一封信送达时，你肯定不想通过搜索每一条街道（就像线性搜索那样）来投递。你希望根据邮政编码（键）瞬间知道它应该放入哪个信箱（存储位置）。这正是哈希表所做的工作！

哈希表（有时也称为哈希映射，Hash Map）是一种专为实现超快速数据插入、删除和检索而设计的数据结构。

它通过在键 (Key) 和存储相应值 (Value) 的物理位置（索引）之间建立直接映射来实现这一目标。

核心术语

• 键 (Key)： 用于查找数据的唯一标识符（例如：学生 ID、用户名）。
• 值 (Value)： 实际存储的数据（例如：学生档案或个人详细信息）。
• 键值对 (Key-Value Pair)： 键与其对应值组合在一起的存储形式。
• 哈希表 (Hash Table / Array)： 承载数据的底层结构（通常是一个数组或列表）。

哈希表的典型用途

每当需要极速查找时，哈希表都是不二之选：

• 字典： 将单词（键）映射到其释义（值）。
• 数据库索引： 使用主键在大型数据库中快速定位记录。
• 编译器/解释器： 在符号表中管理变量和函数。

2. 哈希函数

哈希表之所以能实现极速访问，其背后的“魔法”在于哈希函数 (Hash Function)。

什么是哈希函数？

哈希函数是一种算法，它接收记录的键（可以是数字、字符串，甚至是复杂的对象），并计算出一个数值。这个数值代表了记录在哈希表中应该存储的位置（索引）。

该计算过程必须非常迅速且具有确定性（即同一个键始终产生同一个索引）。

应用简单的哈希函数（取模运算）

由于键可能非常大（比如 16 位的信用卡号），但哈希表的容量是有限的（假设只有 100 个槽位），因此哈希函数必须将键缩小到一个有效的索引范围内。

限制哈希函数输出的一种非常常见且简单的技术是使用 MOD（取模）运算符。

MOD 运算符返回除法的余数。如果你的哈希表大小为 \(N\)，使用 \( \text{Key} \bmod N \) 总是会返回一个 0 到 \(N - 1\) 之间的索引。

分步示例：
假设我们有一个大小为 10 的哈希表（索引为 0 到 9）。

1. 我们想要存储与 Key = 453 相关联的数据。
2. 我们简单的哈希函数是：\( \text{Index} = \text{Key} \bmod 10 \)。
3. 计算过程：\( 453 \bmod 10 = 3 \)。
4. 数据被存储在索引 3 的位置。

如果我们使用的键是 990，索引则为 0 (\( 990 \bmod 10 = 0 \))。

优秀哈希函数的特征

哈希函数不仅仅是简单的算术运算；它必须经过精心设计，以确保哈希表高效运行。

一个优秀的哈希函数应具备两个关键属性：

1. 计算快速： 计算过程本身必须非常快。如果哈希过程花费的时间比线性搜索还要长，那么使用这种数据结构就毫无意义了！
2. 均匀分布： 它必须保证记录在整个表中实现均匀分布。这意味着它应该将键分散到所有可用的索引中，以最大程度地减少堆积（聚集）。

如果你所有的键都哈希到了索引 5，那哈希表就彻底失效了！

3. 冲突与冲突处理

即使拥有最完美的哈希函数，有时不同的键产生完全相同的索引也是不可避免的。这被称为冲突 (Collision)。

什么是冲突？

冲突是指两个或多个不同的键值被哈希函数映射到了哈希表中的同一个位置（索引）。

类比： 你有 10 个储物柜供 12 名学生使用。即便分配策略再聪明，至少有两名学生不得不共用一个柜子或寻找替代方案。

使用再哈希法（线性探测）处理冲突

当发生冲突时，我们不能覆盖已有的数据。我们需要一种方法来找到下一个可用的空间。课程大纲中指定的方法被称为再哈希 (Rehashing)，具体来说就是线性探测 (Linear Probing)。

再哈希（线性探测）分步说明：

1. 键 Key A 被哈希到索引 H，数据 A 存储在 H 中。
2. 新键 Key B 被哈希，其结果也是 H（发生了冲突）。
3. 系统检查索引 H。由于该处已被数据 A 占用，系统会寻找下一个可用位置。
4. 系统检查 \(H + 1\)。如果是空的，数据 B 就存储在那里。
5. 如果 \(H + 1\) 也被占用了，它会继续检查 \(H + 2\)，依此类推。（如果到达了表末尾，则折回到索引 0 继续寻找）。

给学生的重要提示： 如果你稍后需要搜索 Key B，计算机会先将 Key B 哈希到索引 H。如果它发现该处是数据 A 而不是数据 B，它必须继续检查 \(H + 1\)、\(H + 2\) 等，直到找到目标键或遇到一个空槽位（这会告诉它该键不存在）。

4. 哈希表与数组的比较

课程大纲要求你理解将哈希表作为标准数组替代方案的优缺点。

数组（列表）回顾

数组是静态数据结构（固定大小，尽管存在动态列表/数组）。通过索引访问项是瞬间完成的 (O(1))。除非数组已排序允许使用二分查找 (O(log n))，否则搜索特定的值通常需要线性搜索 (O(n))。

哈希表 vs. 数组

特性	哈希表的优势	哈希表的劣势
查找速度（效率）	极快的平均时间（接近常数时间，O(1)），因为位置是直接计算出来的。	在最坏的情况下（大量冲突），查找时间会显著退化，有时会慢至 O(n)。
存储效率	与数组本身的数据存储量相比，该项通常不适用。	如果表填充稀疏（存在大量空槽），可能会浪费内存。
插入/删除	非常快，因为位置是直接计算的（平均时间 O(1)）。	处理冲突会增加代码的复杂性。
顺序性	不适用。	哈希表中存储的数据通常是无序的；按顺序获取排序数据非常困难甚至不可能。数组则基于索引维持固有的顺序。