三、哈希冲突

3.1 什么是冲突？

由于数组长度是有限的，而 Key 的范围可能是无限的。 根据鸽巢原理，必然会有两个不同的 Key ($K_1 \neq K_2$)，经过计算得到相同的索引 ($H(K_1) = H(K_2)$)。 这就是哈希冲突。

3.2 解决方法

方法一：链地址法 (Chaining) —— 最常用

原理：数组的每个位置不直接存数据，而是存一个链表的头指针。所有哈希到该位置的元素，都挂在这个链表上。

• 结构：Array + Linked List
• 优点：实现简单，对装载因子不敏感。
• 缺点：需要额外的指针空间，链表过长会退化查找效率。

方法二：开放寻址法 (Open Addressing)

原理：如果位置被占了，就按照某种规则去寻找下一个空位。

1. 线性探测 (Linear Probing)：
   • Hash(x) + 1, Hash(x) + 2, ...
   • 缺点：容易产生“一次聚集”现象（数据连成一片）。
2. 二次探测 (Quadratic Probing)：
   • Hash(x) + 1^2, Hash(x) - 1^2, Hash(x) + 2^2...
3. 双重哈希 (Double Hashing)：
   • 使用两个哈希函数。

---