哈希算法题目：设计一个哈希映射，使用双重哈希解决冲突

题目描述
设计一个哈希映射（HashMap），要求实现以下操作：

• put(key, value): 插入键值对到哈希映射中
• get(key): 返回键对应的值，如果键不存在则返回-1
• remove(key): 删除键对应的键值对

需要满足以下要求：

1. 使用固定大小的数组（不涉及动态扩容）
2. 使用双重哈希（double hashing）解决哈希冲突
3. 键和值都是整数（为简化问题）
4. 当哈希映射已满时，put操作可以覆盖已有键或失败（本题要求覆盖）

解题过程

步骤1：理解双重哈希的基本原理
双重哈希是开放地址法的一种，使用两个哈希函数来解决冲突：

• 第一个哈希函数计算初始位置：h1(key) = key % capacity
• 第二个哈希函数计算步长：h2(key) = 1 + (key % (capacity - 1))
• 当发生冲突时，探测序列为：(h1(key) + i * h2(key)) % capacity（i=0,1,2,...）

这样设计可以避免线性探测的"聚集"现象，提供更好的分布性。

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

• 一个固定大小的数组buckets，用于存储键值对
• 特殊标记来区分空桶和已删除的桶（因为删除操作需要特殊处理）
• 数组容量（通常选择质数以保证双重哈希能遍历所有位置）

class MyHashMap:
    def __init__(self, capacity=1000003):  # 选择一个质数作为容量
        self.capacity = capacity
        self.buckets = [None] * capacity
        # None表示空桶，(-1, -1)表示已删除的桶，(key, value)表示有数据的桶

步骤3：实现双重哈希函数

def _hash1(self, key):
    return key % self.capacity

def _hash2(self, key):
    return 1 + (key % (self.capacity - 1))  # 保证步长不为0，且与capacity互质

步骤4：实现查找位置的辅助方法
这个方法用于找到键应该存放的位置，或确认键是否存在：

def _find_index(self, key):
    """返回键应该存放的位置索引，或键当前所在的位置"""
    index = self._hash1(key)
    step = self._hash2(key)
    
    first_deleted = -1  # 记录第一个遇到的已删除位置
    
    i = 0
    while i < self.capacity:
        current = self.buckets[index]
        
        # 如果遇到空桶，说明键不存在
        if current is None:
            # 如果有遇到过已删除的位置，优先复用
            return first_deleted if first_deleted != -1 else index
        
        # 如果遇到已删除的桶，记录位置但继续查找
        elif current == (-1, -1):
            if first_deleted == -1:
                first_deleted = index
        
        # 如果找到键本身
        elif current[0] == key:
            return index
        
        # 冲突，继续探测
        index = (index + step) % self.capacity
        i += 1
    
    # 如果数组已满且没找到，返回第一个可用的已删除位置或最后一个探测位置
    return first_deleted if first_deleted != -1 else -1

步骤5：实现put方法

def put(self, key, value):
    index = self._find_index(key)
    
    if index == -1:  # 哈希表已满且没有合适位置
        return
    
    # 如果位置是已删除或空桶，或者键已存在，直接插入/覆盖
    self.buckets[index] = (key, value)

步骤6：实现get方法

def get(self, key):
    index = self._find_index(key)
    
    if index == -1 or self.buckets[index] is None or self.buckets[index] == (-1, -1):
        return -1
    
    return self.buckets[index][1]

步骤7：实现remove方法

def remove(self, key):
    index = self._find_index(key)
    
    if index != -1 and self.buckets[index] is not None and self.buckets[index] != (-1, -1):
        # 标记为已删除，而不是直接设为None
        self.buckets[index] = (-1, -1)

步骤8：完整代码实现

class MyHashMap:
    def __init__(self, capacity=1000003):
        self.capacity = capacity
        self.buckets = [None] * capacity
    
    def _hash1(self, key):
        return key % self.capacity
    
    def _hash2(self, key):
        return 1 + (key % (self.capacity - 1))
    
    def _find_index(self, key):
        index = self._hash1(key)
        step = self._hash2(key)
        
        first_deleted = -1
        
        i = 0
        while i < self.capacity:
            current = self.buckets[index]
            
            if current is None:
                return first_deleted if first_deleted != -1 else index
            elif current == (-1, -1):
                if first_deleted == -1:
                    first_deleted = index
            elif current[0] == key:
                return index
            
            index = (index + step) % self.capacity
            i += 1
        
        return first_deleted if first_deleted != -1 else -1
    
    def put(self, key, value):
        index = self._find_index(key)
        if index != -1:
            self.buckets[index] = (key, value)
    
    def get(self, key):
        index = self._find_index(key)
        if index == -1 or self.buckets[index] is None or self.buckets[index] == (-1, -1):
            return -1
        return self.buckets[index][1]
    
    def remove(self, key):
        index = self._find_index(key)
        if index != -1 and self.buckets[index] is not None and self.buckets[index] != (-1, -1):
            self.buckets[index] = (-1, -1)

关键点总结

1. 双重哈希通过两个不同的哈希函数减少冲突和聚集现象
2. 删除操作使用特殊标记(-1, -1)而不是直接设为None，保证探测序列的连续性
3. _find_index方法统一处理查找逻辑，避免代码重复
4. 选择质数作为容量可以保证双重哈希能遍历所有位置
5. 时间复杂度：平均情况下O(1)，最坏情况下O(n)