哈希算法题目：设计哈希映射（开放地址法实现）

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

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

要求：

• 使用开放地址法解决哈希冲突，具体采用线性探测法。
• 假设键和值都是非负整数（键的范围是 0 到 10^6），但哈希表容量有限（这里设定初始容量为 10007，是一个质数，有助于减少探测中的聚集问题）。
• 当哈希表的负载因子超过阈值（如 0.7）时，进行动态扩容（这里简化为提示，实现中可自行选择是否完整实现扩容逻辑）。

解题步骤

1. 理解开放地址法
开放地址法是一种哈希表解决冲突的方法。当发生冲突（即两个键映射到同一位置）时，它会按照某种探测序列（如线性探测：顺序检查下一个位置）在哈希表中寻找下一个可用的空位。

• 插入：计算哈希位置，如果被占用且键不同，则继续探测直到找到空位或相同键。
• 查找：从哈希位置开始顺序查找，直到遇到空位（说明键不存在）或找到相同键。
• 删除：不能直接清空位置，否则会破坏查找链。通常用标记法（如标记为“已删除”）。

2. 数据结构设计
我们使用两个数组：

• keys[]：存储键，初始化为一个特殊值（如 -1 表示空位，-2 表示已删除）。
• values[]：存储值。

初始容量设为质数（如 10007），以减少冲突。

3. 哈希函数
由于键是非负整数，可直接用取模运算：
hash(key) = key % capacity。

4. 探测方法
线性探测：如果位置 i 被占用，则尝试 (i + 1) % capacity，依此类推，直到找到空位或目标键。

5. 插入（put）步骤

• 计算初始索引 idx = key % capacity。
• 从 idx 开始循环：
  • 如果该位置键为 -1（空位）或 -2（已删除），或键等于当前 key，则在此处插入/更新键值对，并标记为有效（将 keys[idx] 设为 key）。
  • 否则，索引加一（取模）继续探测。
• 如果负载因子超限，触发扩容（此步骤省略详细实现，可参考：创建更大容量的新表，重新插入所有有效键值对）。

6. 查找（get）步骤

• 计算初始索引 idx = key % capacity。
• 从 idx 开始循环，直到遇到空位（keys[i] == -1）：
  • 如果 keys[i] == key 且不是已删除标记（即 keys[i] != -2），返回 values[i]。
  • 否则索引加一（取模）继续。
• 若循环结束未找到，返回 -1。

7. 删除（remove）步骤

• 计算初始索引 idx = key % capacity。
• 从 idx 开始循环，直到遇到空位（keys[i] == -1）：
  • 如果 keys[i] == key，标记该位置为“已删除”（如 keys[i] = -2），并清空值（可选）。
  • 否则索引加一（取模）继续。

8. 关键点与边界条件

• 线性探测可能导致“聚集”，但这里用质数容量缓解。
• 删除操作使用标记，避免查找链断裂。
• 探测循环必须能遍历整个表，避免无限循环（通过记录步数或保证有空位）。
• 当表接近满时，插入可能失败，需考虑扩容。

代码示例（简化版，无扩容）

class MyHashMap:
    def __init__(self, capacity=10007):
        self.capacity = capacity
        self.keys = [-1] * capacity
        self.values = [0] * capacity

    def put(self, key: int, value: int) -> None:
        idx = key % self.capacity
        while self.keys[idx] != -1:  # 非空位
            if self.keys[idx] == key:  # 键已存在
                self.values[idx] = value
                return
            idx = (idx + 1) % self.capacity
        # 找到空位或已删除位
        self.keys[idx] = key
        self.values[idx] = value

    def get(self, key: int) -> int:
        idx = key % self.capacity
        while self.keys[idx] != -1:  # 直到遇到真·空位
            if self.keys[idx] == key:
                return self.values[idx]
            idx = (idx + 1) % self.capacity
        return -1

    def remove(self, key: int) -> None:
        idx = key % self.capacity
        while self.keys[idx] != -1:
            if self.keys[idx] == key:
                self.keys[idx] = -2  # 标记为已删除
                return
            idx = (idx + 1) % self.capacity

总结
开放地址法通过原地探测解决冲突，节省指针开销，但需仔细处理删除和扩容。线性探测简单，但易产生聚集；二次探测或双重哈希可优化，但本题要求线性探测。此设计保证了基本操作的平均时间复杂度在良好哈希函数下接近 O(1)。