哈希

哈希表是计算机科学中最重要、应用最广泛的数据结构之一。它通过“空间换时间”的策略，实现了在理想情况下 的查找、插入 and 删除效率。

一. 核心概念与定义

哈希表（也叫散列表）是一种根据关键码值（Key）直接进行访问的数据结构。

• 基本原理：它通过一个函数——哈希函数（Hash Function），将主要数据（Key）映射到表中的一个位置（Index）来访问记录。

1.1 底层存储（Buckets/Slots）

哈希表底层通常是一个数组。数组的每个位置被称为“桶（Bucket）”或“槽（Slot）”。

1.2 哈希函数（Hash Function）

这是哈希表的灵魂。它的作用是将任意长度的输入（Key）转换为一个固定长度的整数索引。

$$Index = Hash(Key) \ \% \ ArraySize$$

优秀的哈希函数应具备的特质：

1. 确定性：对于相同的 Key，必须永远产生相同的 Hash 值。
2. 高效性：计算速度要快（尽量使用位运算、移位等）。
3. 均匀分布（最重要）：输出值应尽可能均匀地分布在数组范围内，避免堆积。

1. 除法哈希函数

这是最直观、最常用的方法，核心利用了取模运算。

• 逻辑：将关键字 除以哈希表的大小 ，取其余数作为哈希地址。 $$h(k) = k \mod m$$
• 设计要点：
  • 的选择至关重要。通常建议选择一个不接近 2 的幂的质数。
  • 如果 ，则哈希值仅取决于 的低 位，这会导致如果输入数据的低位分布不均，冲突会非常严重。
• 优点：实现极其简单，计算速度快。
• 缺点：对 的选择敏感，处理不当易产生堆积。

2. 乘法哈希函数

$$h(k) = [(a \cdot k) \pmod{2^w}] >> (w - r)$$

公式变量含义：

• ：待哈希的关键字（通常是一个整数）。
• ：一个精心选择的大整数常数。为了分布均匀，它通常是一个大的奇数，且接近黄金分割比例与 的乘积。
• ：计算机的字长（Word size），通常是 32 或 64。
• ：你希望得到的哈希值的位数。即哈希表的大小 。
• ：位右移操作。

第一阶段：乘法与自动取模 (a * k) mod 2^w：

• 在 C++ 等编程语言中，当你使用无符号整数（如 uint32_t）进行乘法时，如果结果超过了 ，它会产生溢出并自动丢弃高位。
• 这个“溢出”本质上就是执行了 操作。
• 意义：这一步极快，不需要显式的取模运算。它将结果限制在一个机器字长（ 位）内。

第二阶段：右移提取 >> (w - r)：

• 乘法结果 的低位通常受 的细微变化影响较小，而中间和高位则包含了 的更多信息，分布更均匀。
• 通过右移 位，我们舍弃了低位，将高处的 位移动到最低位。
• 意义：最终得到的数值范围正好是 ，完美对应大小为 的哈希表索引。

3. 滚动哈希

滚动哈希主要用于字符串匹配（如 Rabin-Karp 算法）。它允许在 时间内，通过已知的哈希值快速计算出滑动窗口移动后的新哈希值。

• 逻辑：将字符串视为一个 进制的数（ 通常取质数，如 31 或 131）。
  对于窗口内的字符串，其哈希值为：

  $$H = (s[0] \cdot P^{n-1} + s[1] \cdot P^{n-2} + \dots + s[n-1]) \mod M$$

• “滚动”过程：
  当窗口向右移动一位，移出字符 old，移入字符 new 时：

  1. 减去最高位的值：
  2. 整体左移（乘基数）：
  3. 加上新字符的值：
  4. 最后全程取模。
• 应用：在大文本中查找子串、检测文章抄袭等，能将 的匹配复杂度优化至接近 。

小白理解版：

• 为了计算，我们必须把字符串（如 “ABC”）看作一个数字。
• 我们将它看作一个 进制数。比如在十进制中，。
• 在字符串中，我们假设 ，进制 ：
  • "ABC" 的哈希值
• 假设窗口里现在是 "ABC"，我们要滑向下一个字符 "D"（即窗口变为 "BCD"）。
• 步骤拆解：
  1. 脱离旧首位：我们要减去 A 开头的贡献。
     • 此时剩下的是 的部分。
  2. 左移（升阶）：原本的 B 是 ，C 是 。在新窗口 "BCD" 中，B 应该变成 ，C 变成 。
     • 所以我们要把整个剩下的值 乘以 ：。
  3. 填入新末位：加上 D 的值（）
     • 。

二. 哈希冲突（Hash Collision）

由于 Key 的取值空间通常是无穷的，而数组的空间是有限的，必然会出现两个不同的 Key 计算出同一个索引的情况：

$$Hash(Key_1) = Hash(Key_2)$$

这就叫哈希冲突。

解决冲突的两种主流方案：

2.1链地址法

• 原理：数组的每个位置不再存单独的数据，而是存一个链表的头指针。
• 过程：当发生冲突时，将新元素追加到该索引对应的链表中。
• 查找：先算出索引，找到对应的链表，然后遍历链表比对 Key。
• 缺点：链表遍历是 （为数据数量），且指针需要额外空间。

2.2开放寻址法

• 原理：所有元素都存放在数组里。如果当前位置被占了，就按某种规则找“下一个”空位。
• 探测方式：
  1. 线性探测
     • 探查逻辑：如果 被占用，则检查 ，以此类推。
       • 公式：
       • 通俗理解：如果当前坑位有人，就看紧挨着的下一个，直到找到空位。
     • 缺点：一次聚集。
       • 容易形成一段连续被占用的区域。这会导致新元素落入此区域后需要经过多次探查才能找到空位，严重拖慢查找和插入速度。
  2. 二次探测
     • 探查逻辑：探查间隔不再是固定的 ，而是 的二次函数。
       • 公式：
       • 通俗理解：第 1 次跳 1 格，第 2 次跳 4 格，第 3 次跳 9 格……
     • 优点：消除了线性探查中的“一次聚集”现象。
     • 缺点：二次聚集。
       • 虽然跳得开了，但如果两个关键字的初始哈希值 相同，它们的探查路径依然是完全一样的。
  3. 双重哈希
     • 探查逻辑：使用两个独立的哈希函数。第一个哈希函数确定起始位置，第二个哈希函数确定步长。
       • 公式：
       • 通俗理解：如果位置被占，步长由第二个哈希函数决定。不同的关键字即使起始位置相同，由于 不同，它们的探查步长也会不同。
     • 设计要求： 的结果必须与 互质，否则可能无法遍历表中所有位置（通常 取 2 的幂且 返回奇数，或者 为素数且 ）。
• 优点：数据在数组中连续，CPU 缓存友好。
• 缺点：删除元素很麻烦（不能直接删，要标记为“已删除”，否则会中断后续元素的查找链）

三. 扩容与装载因子

哈希表不能无限塞数据，否则冲突会剧增，退化成链表，效率变成

• 装载因子（Load Factor, ）： $$\alpha = \frac{\text{填入表中的元素个数}}{\text{散列表的长度}}$$
• 扩容阈值：通常设定为 0.75（如 Java HashMap）。即当数组用了 75% 时，触发扩容。
• 扩容过程：
  1. 创建一个新的数组，通常是原容量的 2倍。
  2. 重新计算旧数组中所有元素的 Hash 值，并将它们放入新数组中。
  3. _注意_：这是一个非常耗时的 操作。

四.简单均匀分布哈希假设

简单均匀分布哈希假设（SUHA）是一种理想化的理论模型，它假设任何关键字都以等概率且独立地映射到哈希表的 个槽位中的任何一个。

设哈希表大小为 ，已存储的元素数量为 ，装载因子 。

在 SUHA 假设下，查找复杂度为

• 常数项 “1” 的含义：哈希映射与定位
  • 动作：当你查找一个关键字时，首先需要通过哈希函数计算出它的哈希值，并根据这个值直接跳转到哈希表对应的“桶”（槽位）。
  • 开销：在计算机中，数组的下标随机访问是 的。
• 变量项 “” 的含义：链表内的线性搜索
  • 背景：在拉链法中，同一个桶里的元素是以链表形式存储的。定位到桶后，你需要遍历这个链表来寻找目标。
  • 逻辑：根据 SUHA 假设， 个元素会均匀地分布在 个桶里。
    • 平均长度：每个桶中链表的预期长度就是装载因子 （即 ）。
  • 开销：
    • 查找失败：你需要检查完整个链表才能确定元素不存在，预期检查次数为 。
    • 查找成功：如之前讨论，平均只需检查链表的一半元素，预期次数约为 。
  • 总结：在渐进分析（大 O 表示法）中，无论是 还是 ，其阶数都是 。