故事的开端

故事：快递仓库的魔法柜子

在一个繁忙的快递小镇上，有一家神奇的仓库，名叫 “哈希快递”。这家仓库以“瞬间找到任何包裹”而闻名，秘密就在于它使用了 哈希表 的魔法！

第一章：仓库的魔法规则

仓库里有一排排整齐的 储物柜（Buckets），每个柜子都有一个编号（比如 0 到 99 号）。仓库管理员 哈希函数老爷爷 负责分配包裹。他的规则很简单：

“给我快递单号（Key），我告诉你柜子编号（Hash Value）！”

例如：

  • 单号 12345 → 老爷爷计算 12345 % 100 = 45 → 存入 45 号柜子。
  • 单号 67890 → 计算 67890 % 100 = 90 → 存入 90 号柜子。

第二章：冲突！两个包裹进了同一个柜子

一天，两个包裹的单号分别是 100 和 200。老爷爷一算：100 % 100 = 0，200 % 100 = 0 → 两个包裹都要进 0 号柜子！
仓库里顿时炸开了锅：“柜子只能放一个包裹，怎么办？”

这时，聪明的助手 链表小精灵 跳出来说：“别担心！我们给柜子加一条链子，挂上更多小盒子！”
于是，0号柜子里挂了一个小盒子放包裹 100，再挂一个盒子放包裹 200，像这样：

0号柜子 → [包裹100] → [包裹200] → NULL

这就是 链表法（Separate Chaining） 的魔法！

第三章：另一种魔法——开放寻址

另一个仓库的分店尝试了不同的方法。当冲突发生时，管理员 探测小分队 会按规则找下一个空柜子：

  • 单号 200 本应进0号柜子，但发现已被占用。
  • 探测小分队说：“向右找！1号柜子空着！” → 包裹 200 进了 1 号柜子。

这就是 开放寻址法（Open Addressing），像捉迷藏一样找空位！

第四章：为什么魔法会失效？

有一天，仓库的柜子几乎全被占满了（负载因子过高），冲突越来越多。快递员抱怨：“找个包裹要开十个柜子，太慢了！”

管理员当机立断：“启动扩容魔法！”
一夜之间，仓库的柜子从 100 个变成 200 个，所有包裹被重新计算编号（Rehash），冲突大幅减少。这就是哈希表的 动态扩容！

第五章：魔法的精髓

  1. 哈希函数：公平的分配者，决定包裹的命运。
  2. 桶（Buckets）：魔法柜子，直接存放或链式管理包裹。
  3. 冲突解决：链表像挂小盒子，开放寻址像捉迷藏。
  4. 扩容：仓库不够用时，悄悄扩建并重新分配。

故事的启示

  • 哈希表是“空间换时间”的魔法：用更多柜子（内存）换取快速查找（$O(1)$ 平均时间）。
  • 设计好哈希函数：像老爷爷一样公平，才能减少冲突。
  • 现实中的应用：
    • 你的手机通讯录（名字 → 电话）
    • 网络缓存（网址 → 数据）

下次当你 dict.get(key) 或 map[key] 时，记得感谢这个快递仓库的魔法🪄！

简介

哈希表 (hash table 或 hash map) 是一种实现关联数组 (associative array) 的抽象数据类型，该结构可以将键映射到值。

哈希表使用哈希函数/散列函数，来计算一个值在数组或桶 (buckets) 中或槽 (slots) 中对应的索引，可使用该索引找到所需的值。

hash-table-basic.svg

理想情况下，散列函数将为每个键分配给一个唯一的桶 (bucket)，但是大多数哈希表设计采用不完美的散列函数，这可能会导致哈希冲突 (hash collisions) ，也就是 hash 函数为多个键 (key) 生成了相同的索引，这种碰撞必须以某种方式进行处理。

链表法

hash-table-linkedlist.svg

开放寻址法

开放寻址法（Open Addressing）是哈希表中解决冲突的另一种常用方法。

开放寻址法的基本思想是：当有新的元素要插入到哈希表中时，如果计算出的哈希地址已经被占用，就通过某种探测策略寻找下一个空闲的位置来插入元素。在查找元素时，也按照同样的探测策略依次检查各个位置，直到找到目标元素或者确定元素不存在。

hash-table-open-addressing.svg

探测策略

  • 线性探测：这是最简单的探测策略。当发生冲突时，依次检查下一个位置，即 (hash(key) + i) % m，其中 i = 1, 2, 3,...，m 是哈希表的大小。

    例如，若 hash(key) 计算出的位置已经被占用，就检查 (hash(key) + 1) % m 这个位置，若还是被占用，就检查 (hash(key) + 2) % m，以此类推。

  • 二次探测：二次探测的探测序列为 (hash(key) + i^2) % m 和 (hash(key) - i^2) % m，其中 i = 1, 2, 3,...。它通过采用二次函数的方式来寻找下一个可用位置，相比线性探测，能减少“聚集”现象。

  • 双重哈希：使用两个哈希函数 hash1(key) 和 hash2(key) ，当发生冲突时，探测序列为 (hash1(key) + i * hash2(key)) % m，其中 i = 1, 2, 3,...。hash2(key) 的值通常与 m 互质，这样可以使探测序列更加均匀地分布在哈希表中。

特点
  • 优点
    • 不需要额外的空间：相比于链地址法等解决冲突的方法，开放寻址法不需要为每个哈希桶维护一个链表或其他数据结构来解决冲突，因此在空间利用上更为紧凑。
    • 查找效率较高：在哈希表装填因子较低的情况下，查找操作可以很快地定位到目标元素，平均查找长度较短。
  • 缺点
    • 删除操作复杂：在开放寻址法中，删除一个元素不能简单地将其位置置为 None，因为这可能会影响后续元素的查找。通常需要做特殊标记，以表示该位置曾经有元素但已被删除，这增加了删除操作的复杂性和实现难度。
    • 聚集问题：容易出现“聚集”现象，即连续的多个位置被占用，导致新元素插入和查找时需要探测更多的位置，降低了效率。尤其是线性探测，聚集问题可能会比较严重。

哈希函数

哈希函数（Hash Function）的核心任务是将任意类型的数据（如字符串、数字、对象等）转换为一个固定范围的整数（哈希值），以便用于快速查找、存储或验证。以下是其工作原理的详细说明：

基本要求

  • 一致性：相同的输入必须始终生成相同的哈希值。
  • 高效性：计算速度快，时间复杂度通常为 $O(1)$ 或 $O(n)$（n 为输入长度）。
  • 均匀分布：不同输入应尽量均匀映射到不同的哈希值，减少冲突。

常见键类型的转换方法

整数类型键

  • 直接取模法：

    def hash_int(key, table_size):
    return key % table_size  # 例如 key=15, table_size=10 → 哈希值=5
    • 适用场景：键本身是整数，且分布均匀。
    • 缺点：若键的分布与模数相关（如全为偶数），会导致哈希冲突。
字符串类型键

字符串的哈希需要将字符序列转换为整数，常用方法包括：

  • 简单字符相加：

    def hash_string_simple(s, table_size):
    hash_value = 0
    for char in s:
        hash_value += ord(char)  # 将字符转为ASCII码并累加
    return hash_value % table_size
    • 示例："cat" → 99 + 97 + 116 = 312 → 假设 table_size=100 → 哈希值 12。
    • 缺点：易冲突（如 "act" 也会得到 12）。

  • 多项式滚动哈希（PolyRoll Hash）：

    def hash_string_poly(s, table_size, base=31):
    hash_value = 0
    for char in s:
        hash_value = hash_value * base + ord(char)
    return hash_value % table_size

    • 示例："cat" → 计算过程：

      hash = 0 * 31 + 99 = 99
hash = 99 * 31 + 97 = 3166
hash = 3166 * 31 + 116 = 98142
hash_value = 98142 % 100 → 42

    • 优势：减少冲突概率（顺序敏感，"cat" 和 "act" 哈希值不同）。

对象类型键
  • 基于唯一标识符：

    • 使用对象的内存地址或唯一ID生成哈希值。

    • 示例（Python的默认对象哈希）：

      class User:
    def __init__(self, id, name):
        self.id = id
        self.name = name

    def __hash__(self):
        return hash(self.id)  # 基于id生成哈希值
复合类型键（如元组、字典）

  • 组合哈希：

    def hash_tuple(t, table_size):
    combined_hash = 0
    for item in t:
        combined_hash ^= hash(item)  # 异或操作合并哈希值
    return combined_hash % table_size
    • 示例：元组 (3, "apple") → 组合 hash(3) 和 hash("apple")。

哈希冲突的必然性

由于哈希函数将无限可能的输入映射到有限整数范围，冲突不可避免。例如：

  • 鸽巢原理：若哈希表有100个桶，插入101个键，至少有一个桶需要存储2个键。
  • 解决冲突的方法：
    • 链表法（拉链法）：每个桶存储一个链表，冲突时追加。
    • 开放寻址法：冲突时按规则（如线性探测）寻找下一个空桶。

设计哈希函数的关键

  • 雪崩效应：输入的微小变化（如一个字符改变）应导致哈希值大幅变化。
    • 示例：加密哈希函数（如SHA-256）几乎满足此特性。
  • 均匀性：哈希值应均匀分布在桶范围内。
  • 避免模式重复：如质数取模（table_size 选质数）可减少特定键分布的冲突。

实际应用示例

(1) Java的 hashCode() 方法

  • 字符串哈希：计算公式为： $ s[0] \times 31^{(n-1)} + s[1] \times 31^{(n-2)} + \dots + s[n-1] $ 其中 $s[i]$ 是字符的ASCII码，$n$ 是字符串长度。

(2) Python 的字典（dict）

  • 使用内置 __hash__() 方法生成键的哈希值。
  • 对不可变类型（如字符串、元组）支持哈希，可变类型（如列表）不支持。

(3) 加密哈希函数（如SHA-256）

  • 用途：数据完整性验证、密码存储。
  • 特点：抗碰撞性强，但计算较慢，不适合哈希表。

指标参数

  • 容量与负载因子

    • 负载因子（Load Factor）= 已存条目数 / bucket 总数。
    • 负载因子过高（如 >0.7）会导致冲突频繁，需扩容（Rehashing）。

  • 哈希函数质量

    • 均匀的哈希函数能减少 bucket 间的负载不均衡。