设计哈希映射（二次探测法实现）

字数 3028 2025-12-14 02:37:26

设计哈希映射（二次探测法实现）

题目描述
我们需要设计一个哈希映射（HashMap），它支持以下操作：

put(key, value)：插入键值对。如果键已存在，则更新其值。
get(key)：返回键对应的值。如果键不存在，返回 -1。
remove(key)：删除键对应的键值对。

本题的特殊要求是：必须使用开放地址法（Open Addressing）中的二次探测法（Quadratic Probing）来解决哈希冲突。这意味着我们不使用链地址法的链表，而是将键值对直接存储在数组中，当发生冲突时，通过二次探测函数寻找下一个可用的空槽位。

解题过程循序渐进讲解

步骤1：理解二次探测法原理
二次探测法是解决哈希冲突的一种开放地址法策略。其核心思想是：

首先，用一个哈希函数计算键的初始索引：hash(key) = key % capacity。
如果该索引位置已被占用（且键不同），则通过一个二次函数探测下一个位置：
index = (hash(key) + c1 * i + c2 * i^2) % capacity，其中 i 是探测次数（从0开始）。
通常简化形式为：index = (hash(key) + i^2) % capacity（即 c1=0, c2=1），但需要注意，这样可能导致无法遍历所有槽位。更通用的二次探测函数为：
index = (hash(key) + i * i) % capacity 或 index = (hash(key) + i // 2 + i^2 // 2) % capacity，但为简单起见，我们采用 i^2 的形式，并确保表的大小为质数，以提高遍历覆盖率。

为什么表大小要设为质数？
在二次探测中，如果表大小不是质数，可能会导致探测序列无法覆盖所有槽位，从而无法找到空位（即使有空位）。质数大小能增加探测序列的周期，使其更有可能遍历所有位置。

步骤2：数据结构设计
我们需要定义：

一个数组（列表）table，用于存储键值对。每个槽位是一个结构，包含 key 和 value。
标记已删除的槽位：由于开放地址法中，直接删除一个元素会导致后续查找中断（因为探测遇到空位就停止），我们需要标记已删除的槽位为 DELETED，这样查找时可以跳过它继续探测，而插入时可以复用这个位置。
初始容量（设为质数，如101），以及负载因子（如0.75）。当元素数占比超过负载因子时，进行扩容（rehash）。

步骤3：定义槽位状态
每个槽位有三种状态：

EMPTY：从未使用过。
OCCUPIED：当前存储着键值对。
DELETED：曾被占用但已被删除。

我们可以用一个特殊值（如 None）表示 EMPTY，用另一个特殊值（如一个唯一标记对象）表示 DELETED。但更清晰的方法是：为每个槽位存储 key 和 value，并用一个额外数组 status 记录状态，或者用 key 的特殊值来区分状态（例如，规定 key 为 None 表示 EMPTY，key 为 -1（如果键范围允许）或一个特殊哨兵对象表示 DELETED）。

步骤4：哈希函数与探测函数

哈希函数：hash(key) = key % capacity。
探测函数：pos = (hash(key) + i * i) % capacity，其中 i 从0开始递增。
注意：i 的上限是多少？理论上，如果表大小为质数，且负载因子小于0.5，二次探测通常能在有限步内找到空位。但为了安全，我们可以探测 capacity 次，如果仍未找到空位，就触发扩容。

步骤5：操作详解

5.1 查找槽位辅助函数
我们需要一个辅助函数 find_slot(key)，它返回一个元组 (index, status)：

如果找到了 key，返回其位置索引和 OCCUPIED。
如果没找到，返回第一个可插入的位置（即状态为 EMPTY 或 DELETED 的槽位索引），以及该位置的状态。

查找过程：

计算初始哈希值 h = key % capacity。
初始化 deleted_index = -1，用于记录遍历过程中遇到的第一个 DELETED 位置（可供插入复用）。
从 i = 0 开始，计算 pos = (h + i * i) % capacity，检查 pos 位置：
- 如果状态为 OCCUPIED 且 key 匹配，返回 (pos, OCCUPIED)。
- 如果状态为 DELETED 且 deleted_index == -1，记录 deleted_index = pos。
- 如果状态为 EMPTY，停止探测。如果有记录的 deleted_index，返回 (deleted_index, DELETED)，否则返回 (pos, EMPTY)。
如果 i 达到 capacity（表示探测了整个表未找到 EMPTY），触发扩容，然后重新查找。

5.2 put操作

调用 find_slot(key) 找到位置 pos 和状态 st。
如果 st 是 OCCUPIED，说明键已存在，直接更新该位置的 value。
否则（状态为 EMPTY 或 DELETED），在 pos 处存储 key 和 value，并将状态设为 OCCUPIED。
元素计数 size 加1（如果新增）。
检查负载因子是否超过阈值（例如 size / capacity > 0.75），若是，执行扩容（rehash）。

5.3 get操作

调用 find_slot(key) 找到位置和状态。
如果状态是 OCCUPIED，返回该位置的 value。
否则返回 -1。

5.4 remove操作

调用 find_slot(key) 找到位置 pos 和状态。
如果状态是 OCCUPIED，将该位置状态改为 DELETED（注意：只改状态，不清空 key 和 value 也可以，但为安全可清空），size 减1。
否则（键不存在），什么也不做。

步骤6：扩容（Rehash）
当负载因子过高时，需要扩容以保持效率。过程：

创建一个新的、更大的数组（新容量通常为大于两倍旧容量的一个质数）。
遍历旧表的所有 OCCUPIED 槽位，对每个键值对重新执行 put 操作插入新表（注意：新表的哈希函数用新容量）。
替换旧表为新表，更新容量。

步骤7：质数容量选择
我们可以在初始化时和扩容时，从预定义的质数列表中选择一个合适的质数作为容量，例如：
[53, 97, 193, 389, 769, 1543, 3079, 6151, 12289, ...]
每次扩容时选择下一个更大的质数。

总结
本题的关键是理解开放地址法中二次探测的查找、插入、删除逻辑，以及如何处理已删除标记。二次探测能减少“聚集”现象，但需要表大小为质数以保证探测序列的完备性。实现时注意负载因子控制，以保持操作的平均时间复杂度为 O(1)。

设计哈希映射（二次探测法实现）题目描述我们需要设计一个哈希映射（HashMap），它支持以下操作： put(key, value) ：插入键值对。如果键已存在，则更新其值。 get(key) ：返回键对应的值。如果键不存在，返回 -1 。 remove(key) ：删除键对应的键值对。本题的特殊要求是：必须使用开放地址法（Open Addressing）中的二次探测法（Quadratic Probing）来解决哈希冲突。这意味着我们不使用链地址法的链表，而是将键值对直接存储在数组中，当发生冲突时，通过二次探测函数寻找下一个可用的空槽位。解题过程循序渐进讲解步骤1：理解二次探测法原理二次探测法是解决哈希冲突的一种开放地址法策略。其核心思想是：首先，用一个哈希函数计算键的初始索引： hash(key) = key % capacity 。如果该索引位置已被占用（且键不同），则通过一个二次函数探测下一个位置： index = (hash(key) + c1 * i + c2 * i^2) % capacity ，其中 i 是探测次数（从0开始）。通常简化形式为： index = (hash(key) + i^2) % capacity （即 c1=0, c2=1 ），但需要注意，这样可能导致无法遍历所有槽位。更通用的二次探测函数为： index = (hash(key) + i * i) % capacity 或 index = (hash(key) + i // 2 + i^2 // 2) % capacity ，但为简单起见，我们采用 i^2 的形式，并确保表的大小为质数，以提高遍历覆盖率。为什么表大小要设为质数？在二次探测中，如果表大小不是质数，可能会导致探测序列无法覆盖所有槽位，从而无法找到空位（即使有空位）。质数大小能增加探测序列的周期，使其更有可能遍历所有位置。步骤2：数据结构设计我们需要定义：一个数组（列表） table ，用于存储键值对。每个槽位是一个结构，包含 key 和 value 。标记已删除的槽位：由于开放地址法中，直接删除一个元素会导致后续查找中断（因为探测遇到空位就停止），我们需要标记已删除的槽位为 DELETED ，这样查找时可以跳过它继续探测，而插入时可以复用这个位置。初始容量（设为质数，如101），以及负载因子（如0.75）。当元素数占比超过负载因子时，进行扩容（rehash）。步骤3：定义槽位状态每个槽位有三种状态： EMPTY ：从未使用过。 OCCUPIED ：当前存储着键值对。 DELETED ：曾被占用但已被删除。我们可以用一个特殊值（如 None ）表示 EMPTY ，用另一个特殊值（如一个唯一标记对象）表示 DELETED 。但更清晰的方法是：为每个槽位存储 key 和 value ，并用一个额外数组 status 记录状态，或者用 key 的特殊值来区分状态（例如，规定 key 为 None 表示 EMPTY ， key 为 -1 （如果键范围允许）或一个特殊哨兵对象表示 DELETED ）。步骤4：哈希函数与探测函数哈希函数： hash(key) = key % capacity 。探测函数： pos = (hash(key) + i * i) % capacity ，其中 i 从0开始递增。注意： i 的上限是多少？理论上，如果表大小为质数，且负载因子小于0.5，二次探测通常能在有限步内找到空位。但为了安全，我们可以探测 capacity 次，如果仍未找到空位，就触发扩容。步骤5：操作详解 5.1 查找槽位辅助函数我们需要一个辅助函数 find_slot(key) ，它返回一个元组 (index, status) ：如果找到了 key ，返回其位置索引和 OCCUPIED 。如果没找到，返回第一个可插入的位置（即状态为 EMPTY 或 DELETED 的槽位索引），以及该位置的状态。查找过程：计算初始哈希值 h = key % capacity 。初始化 deleted_index = -1 ，用于记录遍历过程中遇到的第一个 DELETED 位置（可供插入复用）。从 i = 0 开始，计算 pos = (h + i * i) % capacity ，检查 pos 位置：如果状态为 OCCUPIED 且 key 匹配，返回 (pos, OCCUPIED) 。如果状态为 DELETED 且 deleted_index == -1 ，记录 deleted_index = pos 。如果状态为 EMPTY ，停止探测。如果有记录的 deleted_index ，返回 (deleted_index, DELETED) ，否则返回 (pos, EMPTY) 。如果 i 达到 capacity （表示探测了整个表未找到 EMPTY ），触发扩容，然后重新查找。 5.2 put操作调用 find_slot(key) 找到位置 pos 和状态 st 。如果 st 是 OCCUPIED ，说明键已存在，直接更新该位置的 value 。否则（状态为 EMPTY 或 DELETED ），在 pos 处存储 key 和 value ，并将状态设为 OCCUPIED 。元素计数 size 加1（如果新增）。检查负载因子是否超过阈值（例如 size / capacity > 0.75 ），若是，执行扩容（rehash）。 5.3 get操作调用 find_slot(key) 找到位置和状态。如果状态是 OCCUPIED ，返回该位置的 value 。否则返回 -1 。 5.4 remove操作调用 find_slot(key) 找到位置 pos 和状态。如果状态是 OCCUPIED ，将该位置状态改为 DELETED （注意：只改状态，不清空 key 和 value 也可以，但为安全可清空）， size 减1。否则（键不存在），什么也不做。步骤6：扩容（Rehash）当负载因子过高时，需要扩容以保持效率。过程：创建一个新的、更大的数组（新容量通常为大于两倍旧容量的一个质数）。遍历旧表的所有 OCCUPIED 槽位，对每个键值对重新执行 put 操作插入新表（注意：新表的哈希函数用新容量）。替换旧表为新表，更新容量。步骤7：质数容量选择我们可以在初始化时和扩容时，从预定义的质数列表中选择一个合适的质数作为容量，例如： [53, 97, 193, 389, 769, 1543, 3079, 6151, 12289, ...] 每次扩容时选择下一个更大的质数。总结本题的关键是理解开放地址法中二次探测的查找、插入、删除逻辑，以及如何处理已删除标记。二次探测能减少“聚集”现象，但需要表大小为质数以保证探测序列的完备性。实现时注意负载因子控制，以保持操作的平均时间复杂度为 O(1)。