一、哈希表的基本概念

哈希表通过「哈希函数」将键（Key）映射到数组的某个索引（槽位），但不同的键可能映射到同一个槽位，这就是「冲突」。解决冲突的核心是：当多个键映射到同一槽位时，如何存储这些键值对。

二、开放寻址法（Open Addressing）

核心思想：所有元素都存储在哈希表的数组中，发生冲突时，通过「探测」寻找下一个空槽位存储冲突元素。
（数组大小固定，元素数量不能超过数组长度）

1. 线性探测（Linear Probing）

• 探测规则：冲突时，按顺序检查下一个槽位（当前索引 + 1、+2...），直到找到空槽。
• 示意图（逻辑结构）：
  假设哈希表数组大小为 8（索引 0-7），哈希函数为 hash(key) = key % 8。
  插入键：10、18、26（冲突发生时的探测过程）：

初始数组（空）：[ , , , , , , , ]

1. 插入 10：hash(10)=2 → 存到索引2 → [ , ,10, , , , , ]
2. 插入 18：hash(18)=2（与10冲突）→ 探测索引3（空）→ 存到3 → [ , ,10,18, , , , ]
3. 插入 26：hash(26)=2（冲突）→ 探测3（非空）→ 探测4（空）→ 存到4 → [ , ,10,18,26, , , ]

• 特点：实现简单，但容易产生「聚集效应」（冲突元素扎堆，导致后续探测链变长）。

2. 二次探测（Quadratic Probing）

• 探测规则：冲突时，按平方序列探测下一个槽位（当前索引 + 1²、-1²、+2²、-2²...），避免线性探测的聚集问题。
• 示意图（逻辑结构）：
  同上数组，插入键：10、18、26：

1. 插入10 → 索引2 → [ , ,10, , , , , ]
2. 插入18：hash=2（冲突）→ 探测 2+1²=3（空）→ 存到3 → [ , ,10,18, , , , ]
3. 插入26：hash=2（冲突）→ 探测 2+1²=3（非空）→ 探测 2-1²=1（空）→ 存到1 → [ ,26,10,18, , , , ]

• 特点：减少聚集效应，但探测序列可能无法覆盖所有槽位（需保证数组大小为质数或 2 的幂）。

3. 双重哈希（Double Hashing）

• 探测规则：冲突时，使用第二个哈希函数计算「步长」，按「当前索引 + 步长、+2× 步长...」探测空槽（步长需与数组大小互质）。
• 示意图（逻辑结构）：
  数组大小 8，第一个哈希 hash1(key)=key%8，第二个哈希 hash2(key)=5 - (key%5)（步长）。
  插入键：10、18、26：

1. 插入10 → hash1=2 → 存到2 → [ , ,10, , , , , ]
2. 插入18：hash1=2（冲突）→ hash2=5-(18%5)=5-3=2 → 步长2 → 探测2+2=4（空）→ 存到4 → [ , ,10, ,18, , , ]
3. 插入26：hash1=2（冲突）→ hash2=5-(26%5)=5-1=4 → 步长4 → 探测2+4=6（空）→ 存到6 → [ , ,10, ,18, ,26, ]

• 特点：分散性好，几乎无聚集，但实现稍复杂（需设计两个哈希函数）。

三、链地址法（Chaining，更常用）

核心思想：哈希表的每个槽位对应一个「链表」，冲突的元素直接添加到该槽位的链表中（无需探测）。
（数组大小固定，但链表可动态增长，元素数量无上限）

示意图（逻辑结构）

同样数组大小 8，哈希函数 hash(key)=key%8，插入键：10、18、26、34（均冲突）：

数组槽位：[链表, 链表, 链表, 链表, 链表, 链表, 链表, 链表]

1. 插入10：hash=2 → 槽位2的链表添加10 → 槽位2：[10]
2. 插入18：hash=2 → 槽位2的链表尾部添加18 → 槽位2：[10 → 18]
3. 插入26：hash=2 → 槽位2的链表尾部添加26 → 槽位2：[10 → 18 → 26]
4. 插入34：hash=34%8=2 → 槽位2的链表尾部添加34 → 槽位2：[10 → 18 → 26 → 34]

• 查找过程：例如查找 26，先计算 hash=2，再遍历槽位 2 的链表，找到 26。
• 特点：实现简单，处理大量冲突时效率稳定（链表长度均匀时，查找复杂度接近 O (1)），是多数编程语言中哈希表的默认实现（如 Java 的 HashMap、Python 的 dict）。

四、两种方法的对比

维度	开放寻址法	链地址法
内存利用	高（无链表指针开销）	较低（链表节点需额外存储指针）
冲突处理	依赖探测序列，负载过高时效率骤降	链表动态增长，冲突处理更稳定
实现复杂度	较高（需处理探测、删除标记）	简单（链表插入 / 删除）
适用场景	内存紧张、元素数量固定	元素数量动态变化、冲突频繁

通过以上逻辑示意图，可以清晰看到：开放寻址法是「在数组内部找空位」，而链地址法是「在数组槽位上挂链表存冲突元素」。实际应用中，链地址法因简单和稳定性更常用。