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

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

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

特殊要求：

1. 使用固定大小的数组（假设大小为1000）
2. 使用双重哈希（double hashing）解决哈希冲突
3. 当遇到冲突时，通过第二个哈希函数计算步长，进行探测

解题过程：

第一步：理解双重哈希的基本原理
双重哈希是开放地址法的一种，当发生冲突时，使用两个哈希函数：

• 第一个哈希函数：h₁(key) 计算初始位置
• 第二个哈希函数：h₂(key) 计算探测步长
• 探测序列：position = (h₁(key) + i × h₂(key)) % size，其中i=0,1,2...

第二步：设计哈希函数
我们需要设计两个合适的哈希函数：

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

def hash2(key, size):
    # 步长不能为0，且应与表大小互质
    # 常用方法：hash2(key) = 1 + (key % (size-1))
    return 1 + (key % (size - 1))

第三步：设计数据结构

class MyHashMap:
    def __init__(self, size=1000):
        self.size = size
        self.keys = [None] * size  # 存储键
        self.values = [None] * size  # 存储值
        self.DELETED = object()  # 删除标记

第四步：实现put操作

def put(self, key, value):
    # 计算初始位置和步长
    h1 = self.hash1(key)
    h2 = self.hash2(key)
    
    i = 0
    current_pos = (h1 + i * h2) % self.size
    
    # 寻找可插入位置
    while (self.keys[current_pos] is not None and 
           self.keys[current_pos] != self.DELETED and
           self.keys[current_pos] != key):
        i += 1
        current_pos = (h1 + i * h2) % self.size
        
        # 防止无限循环（理论上表未满就不会循环）
        if i >= self.size:
            return
    
    # 插入或更新
    self.keys[current_pos] = key
    self.values[current_pos] = value

第五步：实现get操作

def get(self, key):
    h1 = self.hash1(key)
    h2 = self.hash2(key)
    
    i = 0
    current_pos = (h1 + i * h2) % self.size
    
    # 沿着探测序列查找
    while self.keys[current_pos] is not None:
        if self.keys[current_pos] == key:
            return self.values[current_pos]
        
        i += 1
        current_pos = (h1 + i * h2) % self.size
        
        if i >= self.size:
            break
    
    return -1  # 未找到

第六步：实现remove操作

def remove(self, key):
    h1 = self.hash1(key)
    h2 = self.hash2(key)
    
    i = 0
    current_pos = (h1 + i * h2) % self.size
    
    # 查找要删除的键
    while self.keys[current_pos] is not None:
        if self.keys[current_pos] == key:
            # 标记为已删除（不能直接设为None，否则会破坏探测链）
            self.keys[current_pos] = self.DELETED
            self.values[current_pos] = None
            return
        
        i += 1
        current_pos = (h1 + i * h2) % self.size
        
        if i >= self.size:
            break

第七步：完整代码实现

class MyHashMap:
    def __init__(self, size=1000):
        self.size = size
        self.keys = [None] * size
        self.values = [None] * size
        self.DELETED = object()
    
    def hash1(self, key):
        return key % self.size
    
    def hash2(self, key):
        return 1 + (key % (self.size - 1))
    
    def put(self, key, value):
        h1 = self.hash1(key)
        h2 = self.hash2(key)
        
        for i in range(self.size):
            pos = (h1 + i * h2) % self.size
            
            # 找到空位或已删除位置或相同key
            if (self.keys[pos] is None or 
                self.keys[pos] == self.DELETED or
                self.keys[pos] == key):
                self.keys[pos] = key
                self.values[pos] = value
                return
    
    def get(self, key):
        h1 = self.hash1(key)
        h2 = self.hash2(key)
        
        for i in range(self.size):
            pos = (h1 + i * h2) % self.size
            
            if self.keys[pos] is None:
                return -1
            if self.keys[pos] == key:
                return self.values[pos]
        
        return -1
    
    def remove(self, key):
        h1 = self.hash1(key)
        h2 = self.hash2(key)
        
        for i in range(self.size):
            pos = (h1 + i * h2) % self.size
            
            if self.keys[pos] is None:
                return
            if self.keys[pos] == key:
                self.keys[pos] = self.DELETED
                self.values[pos] = None
                return

关键要点说明：

1. 双重哈希相比线性探测能减少聚集现象
2. 第二个哈希函数要确保步长与表大小互质
3. 删除操作使用标记法，保持探测链的完整性
4. 装载因子过高时需要扩容（实际应用中）