哈希表与冲突处理

引言：$O(1)$ 的承诺

哈希表 (Hash Table / Map) 堪称编程中最重要的数据结构。它承诺了常数时间 $O(1)$ 的插入、删除和查找性能。

然而，由于可能的 Key 是无限的，而数组空间是有限的，两个不同的 Key 最终会映射到同一个索引上。这就是 冲突 (Collision)。一个系统如何处理冲突，决定了它的性能上限和内存占用。

算法要解决什么问题？

• 输入： 键值对 (Key-Value)。
• 输出： 通过 Key 瞬间访问 Value。
• 承诺： 性能不随数据集的增大而变慢。

核心思想 (直觉版)

想象一面巨大的 编号邮箱墙。

1. 你拿一个名字 (“Luke”)。
2. 哈希函数 将 “Luke” 转换为一个数字（例如 42）。
3. 你直接走向 42 号邮箱。
4. 如果 “Sarah” 的哈希值也是 42，麻烦就来了。

冲突处理策略

1. 拉链法 (Separate Chaining) - Java HashMap 采用

每个“桶”实际上是一个 链表。

• 如果多个 Key 都映射到索引 42，它们就排队存在 42 号位的链表里。
• 优点： 实现简单，永远不会被“填满”。
• 缺点： 冲突多时，$O(1)$ 会退化成 $O(N)$（遍历链表）。

2. 开放寻址法 (Open Addressing) - Python dict 采用

如果 42 号位被占了，就去找 下一个可用 的位置。

• 线性探测： 看 43, 44, 45…
• 优点： 缓存局部性好（所有数据都在一个连续数组里）。
• 缺点： 容易产生“聚集效应”（一大片连续空间被占用，导致搜索变慢）。

工程中的核心考量

• 装载因子 (Load Factor)： 当表被填满 75% 时，性能会急剧下降。此时大多数哈希表会进行 扩容 (Resize)（通常容量翻倍）。
• 哈希洪水攻击 (Hash Flooding)： 如果攻击者知道你的哈希算法，他们可以发送数千个故意碰撞到同一个索引的 Key，让你的 $O(1)$ 服务器变成 $O(N^2)$ 的蜗牛。现代语言通过 哈希加盐/随机化 来防御。

性能与复杂度总结

• 时间 (平均)： $O(1)$。
• 时间 (最坏)： $O(N)$ (发生大量冲突时)。
• 空间： $O(N)$。

小结：一句话记住它

“哈希表通过将 Key 转换为索引来实现瞬间访问。拉链法和开放寻址法是处理‘两个 Key 争抢同一个位置’时的两种交通規則。”