哈希算法题目：设计一个哈希映射，使用开放地址法（线性探测）解决冲突

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

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

要求：

1. 使用开放地址法（Open Addressing） 解决哈希冲突，具体采用线性探测（Linear Probing） 策略。
2. 当哈希表负载因子超过阈值时，自动扩容（例如扩容为原大小的2倍）并重新哈希所有元素。
3. 删除操作需处理"逻辑删除"标记，避免影响后续查询和插入。

解题过程详解

步骤1：理解开放地址法与线性探测

• 开放地址法：所有元素直接存储在哈希表的数组中（而非链地址法的链表）。当发生冲突时，按预定规则（如线性探测）寻找下一个空闲槽位。
• 线性探测：若当前槽位被占用，则顺序检查下一个槽位（索引+1），直到找到空位或匹配的键。

关键问题：

• 删除处理：直接删除元素会导致探测链断裂，后续查询可能失败。需使用"逻辑删除"标记（如DELETED）。
• 扩容时机：负载因子（已用槽数/总槽数）过高时，冲突概率增大，需扩容。

步骤2：设计数据结构
定义哈希表的组成：

1. 数组buckets：存储键值对。每个槽位为三元组 (key, value, status)，其中status标记状态：
   • EMPTY：空槽
   • OCCUPIED：已占用
   • DELETED：已逻辑删除
2. 容量capacity：当前数组大小。
3. 负载因子阈值loadFactor：默认0.75，触发扩容。
4. 当前元素数size：包括逻辑删除的元素（实际需根据OCCUPIED槽数计算负载）。

示例代码结构（Python风格）：

class HashMap:
    def __init__(self, capacity=16):
        self.capacity = capacity
        self.size = 0  # 仅统计OCCUPIED槽数
        self.loadFactor = 0.75
        self.buckets = [(-1, -1, 'EMPTY')] * capacity  # (key, value, status)

步骤3：实现哈希函数与探测逻辑

• 哈希函数：hash(key) = key % capacity（简化示例，实际需处理负键）。
• 线性探测：从初始索引index = hash(key)开始，循环检查槽位：
  • 若状态为OCCUPIED且键匹配，则操作该槽位。
  • 若状态为EMPTY或DELETED，根据操作类型处理（插入时可用DELETED槽）。
  • 索引步进：index = (index + 1) % capacity。

查找槽位的辅助函数：

def _find_slot(self, key):
    index = key % self.capacity
    first_deleted = -1  # 记录首个可重用的DELETED槽
    while self.buckets[index][2] != 'EMPTY':
        if self.buckets[index][2] == 'OCCUPIED' and self.buckets[index][0] == key:
            return index  # 找到键
        if self.buckets[index][2] == 'DELETED' and first_deleted == -1:
            first_deleted = index  # 标记首个可重用槽
        index = (index + 1) % self.capacity
    # 未找到键，返回可插入位置（优先重用DELETED槽）
    return first_deleted if first_deleted != -1 else index

步骤4：实现put操作

1. 调用_find_slot定位槽位。
2. 若槽位为OCCUPIED且键匹配，更新值。
3. 否则（空槽或DELETED），插入新键值对，标记为OCCUPIED，更新size。
4. 检查负载因子：若size / capacity > loadFactor，调用_resize()扩容。

def put(self, key, value):
    index = self._find_slot(key)
    if self.buckets[index][2] == 'OCCUPIED' and self.buckets[index][0] == key:
        self.buckets[index] = (key, value, 'OCCUPIED')  # 更新值
    else:
        self.buckets[index] = (key, value, 'OCCUPIED')
        self.size += 1
    if self.size / self.capacity > self.loadFactor:
        self._resize(2 * self.capacity)

步骤5：实现get操作

1. 调用_find_slot定位槽位。
2. 若槽位为OCCUPIED且键匹配，返回值；否则返回-1。

def get(self, key):
    index = self._find_slot(key)
    if self.buckets[index][2] == 'OCCUPIED' and self.buckets[index][0] == key:
        return self.buckets[index][1]
    return -1

步骤6：实现remove操作

1. 调用_find_slot定位槽位。
2. 若槽位为OCCUPIED且键匹配，标记为DELETED，size减1。

def remove(self, key):
    index = self._find_slot(key)
    if self.buckets[index][2] == 'OCCUPIED' and self.buckets[index][0] == key:
        self.buckets[index] = (-1, -1, 'DELETED')
        self.size -= 1

步骤7：实现扩容重置

1. 创建新容量的空数组。
2. 遍历旧数组，将所有OCCUPIED元素重新插入新数组（忽略EMPTY和DELETED）。
3. 更新buckets和capacity。

def _resize(self, new_capacity):
    old_buckets = self.buckets
    self.capacity = new_capacity
    self.buckets = [(-1, -1, 'EMPTY')] * new_capacity
    self.size = 0
    for key, value, status in old_buckets:
        if status == 'OCCUPIED':
            self.put(key, value)  # 重新插入有效元素

关键点总结

1. 逻辑删除：避免断裂探测链，DELETED槽在插入时可重用。
2. 负载因子计算：仅基于OCCUPIED槽数，排除DELETED。
3. 循环探测：使用取模运算实现数组环形遍历。
4. 时间复杂度：平均O(1)用于操作，最坏O(n)（全表扫描）。

通过以上步骤，可实现一个支持动态扩容、线性探测冲突解决的健壮哈希映射。