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

题目描述
设计一个哈希映射，使用开放地址法解决哈希冲突。需要实现以下操作：

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

解题过程

1. 基础结构设计
使用固定大小的数组存储键值对，每个位置存储三个信息：键、值、状态标记（空/占用/已删除）。初始数组大小设为质数（如2069）以减少聚类。

class MyHashMap:
    def __init__(self):
        self.size = 2069
        self.buckets = [{'key': -1, 'value': -1, 'status': 'empty'} 
                       for _ in range(self.size)]

2. 哈希函数设计
使用简单的取模哈希：hash(key) = key % size。通过双重哈希解决冲突：第一个哈希函数确定初始位置，第二个哈希函数确定步长。

def hash1(self, key):
    return key % self.size

def hash2(self, key):
    return 1 + (key % (self.size - 1))

3. put操作实现

• 计算初始位置index = hash1(key)
• 如果该位置为空或已删除，直接插入
• 如果被占用且键相同，更新值
• 如果被占用但键不同，使用双重哈希探测下一个位置：
  index = (index + hash2(key)) % size
• 循环直到找到合适位置

4. get操作实现

• 从初始位置开始线性探测
• 遇到已占用且键匹配时返回值
• 遇到空桶说明键不存在
• 跳过已删除的桶继续探测

5. remove操作实现

• 找到键对应的桶后不实际删除，而是标记为"已删除"
• 这样保证后续探测链不断裂

6. 扩容考虑
当负载因子超过阈值（如0.75）时，创建新数组并重新插入所有元素。这是保证性能的关键。

这个实现展示了开放地址法的核心思想：所有元素都存储在数组内，通过系统化的探测解决冲突。