目录#

[[toc]]

概念#

散列表（Hash Table）：

• 是一种根据关键字 (Key) 直接访问存储位置的数据结构。
• 通过哈希函数将关键字映射到表中的一个存储位置（数组下标），从而实现接近 O(1) 的平均插入、删除、查找效率。

• 线性探测再散列：(H(key) + i) % m，i=0,1,2,…
• 二次探测：H(key) + i^2 等。
• 双重散列：使用第二个哈希函数提供步长。

成功查找

找到关键字，比较次数记作查找长度。

失败查找

找不到关键字，但要确认其不存在，平均比较次数称为平均查找失败长度（ASL失败）。

• 对开放定址的线性探测，有公式近似：

  $\text{ASL失败} \approx \frac{1}{2}\left(1 + \frac{1}{1-\alpha}\right)$

  其中 α 是装填因子。

与其他结构对比#

散列表的核心思想是空间换时间：

通过哈希函数直接定位数据存储位置，使插入、删除、查找在平均情况下都接近 O(1)，

例子#

0~10，共 11 个槽位。

逐步插入并处理冲突（线性探测）：

1. 87 → 3

2. 40 → 5

3. 30 → 2

4. 6 → 6

5. 11 → 4

6. 22 → 1

7. 98 → 0

8. 20 → 6 冲突

   6 位置已占 → 7 空，放到 7

0:98
1:22
2:30
3:87
4:11
5:40
6:6
7:20（第一次冲突）
8:空
9:空
10:空

平均查找失败长度#

平均查找失败长度 =

所有空槽位的探测长度总和 ÷ 空槽位数

失败查找从起始地址 H(key) 出发，线性探测直到遇到第一个空槽为止；比较次数 = 扫过的已占槽数 + 1（再比较到那个空槽）。

哈希函数决定了“入口集合”

• 题里给的散列函数是 H(key) = key % 7。
• 这表示任何关键字 key，计算出的哈希地址只可能是 0,1,2,3,4,5,6 七个数。
• 即使散列表物理长度是 11（位置 0~10），也不会有关键字的初始哈希地址是 7、8、9、10。

这点非常关键：

失败查找是从哈希函数给出的起点

既然哈希函数的值域只有 0～6，就不存在从 7～10 作为起点的失败查找。

由于 H(key)=key%7，起点只可能是 0～6。对每个起点计算到最近空槽（8）的长度：

• 从 0：0→1→2→3→4→5→6→7→8 ⇒ 9
• 从 1：1→2→3→4→5→6→7→8 ⇒ 8
• 从 2：2→3→4→5→6→7→8 ⇒ 7
• 从 3：3→4→5→6→7→8 ⇒ 6
• 从 4：4→5→6→7→8 ⇒ 5
• 从 5：5→6→7→8 ⇒ 4
• 从 6：6→7→8 ⇒ 3

求平均（在 7 个可能起点上均匀）：

$\frac{9+8+7+6+5+4+3}{7}=\frac{42}{7}= \boxed{6}$

小提醒：如果哈希函数是 % 11（与表长一致），那才应该在 0～10 上平均，此时会得到约 4.27。而本题因为 % 7，只在 0～6 上平均，所以是 6。

• 失败查找：我们找一个根本不存在的 key，哈希函数给出的起始位置一定是 key % 7（也就是 0～6 之间的某个位置）。
• 查找时从这个起点出发，按照线性探测（+1 循环）顺着走，一直走到第一个空槽就停下。
• 这一次探测需要的比较次数，就是该起点到它遇到的第一个空槽之间经过的槽位数 + 1（包括最后那个空槽）。

平均查找成功长度#

对每一个已经插入的元素，都从它的**哈希地址（key % 7）**开始，沿着线性探测的方向查找，直到找到该元素为止。

比较次数 = 探测过的槽位数（包括最后找到它的那个槽位）。

平均查找成功长度 =

所有已插入元素的比较次数总和 ÷ 元素个数。

• 除了 20 发生冲突需要 2 次比较，其余都只需 1 次。

总比较次数 = 1 + 1 + 1 + 1 + 1 + 1 + 1 + 2 = 9

$\text{平均查找成功长度} = \frac{9}{8} \approx 1.13$

成熟的哈希函数#

直接用成熟的哈希函数（例如 MD5、SHA 系列、CRC32 等）来做“key → 位置”的映射。

• 数据结构里的哈希函数：
  • 目标：快速均匀分布关键字，减少冲突。
  • 典型例：key % m、乘法散列法、FNV、MurmurHash。
• 密码学哈希函数（MD5、SHA1/2/3 等）：
  • 目标：不可逆、抗碰撞、输出分布极随机。
  • 应用：数字签名、校验、防篡改、存密码。

只要能把 key 映射成分布均匀的整数，就能作为散列表的哈希函数。