哈希算法题目：设计一个哈希集合，支持添加、删除和查询操作，使用双重哈希解决冲突

题目描述

设计一个哈希集合（HashSet）数据结构，需要支持以下操作：

1. add(key)：向集合中插入一个值 key（如果集合中已存在则不插入）。
2. remove(key)：从集合中移除值 key（如果存在）。
3. contains(key)：判断集合中是否包含值 key，返回布尔值。

约束与要求：

• 使用开放地址法处理哈希冲突，特别指定使用双重哈希作为冲突解决策略。
• 需要处理动态扩容（当元素数量达到容量的特定比例时，扩大数组大小并重新哈希所有元素）。
• 假设 key 是非负整数（在更通用的场景中，可先通过哈希函数将任意对象映射为非负整数，但这里为简化，直接使用整数作为输入）。
• 要求操作的平均时间复杂度为 O(1)。

解题过程循序渐进讲解

第1步：理解哈希集合与开放地址法

哈希集合是基于哈希表实现的集合，每个元素唯一。
开放地址法处理冲突的策略是：当哈希位置被占用时，按某种探测序列寻找下一个空闲位置。
双重哈希是开放地址法的一种，它使用两个哈希函数来计算探测步长，减少聚集现象。

第2步：确定基本结构

我们需要：

• 一个数组 table 存储元素，数组大小（容量）为 capacity。
• 标记数组状态：因为开放地址法中删除元素不能直接置空（会破坏查找链），我们使用一个状态数组 state 标记每个位置是“空”、“已占用”还是“已删除”。
• 当前元素数量 size，用于判断是否需要扩容。

定义状态常量：

EMPTY = 0      # 位置为空
OCCUPIED = 1   # 位置有元素
DELETED = 2    # 位置元素被删除（惰性删除）

第3步：选择哈希函数

双重哈希需要两个哈希函数：

1. 第一个哈希函数：计算初始位置
   hash1(key) = key % capacity
2. 第二个哈希函数：计算探测步长（步长不能为0，且应与容量互质以保证遍历所有位置）
   hash2(key) = 1 + (key % (capacity - 1))
   这里 capacity - 1 保证步长在 [1, capacity-1] 范围内，且通常与容量互质（当容量为质数时更佳）。

探测序列：
位置 = (hash1(key) + i * hash2(key)) % capacity，其中 i 从 0 开始递增。

第4步：实现基本操作框架

初始化：

• 设置初始容量（如 5 或 7，质数利于分散）。
• 创建 table 数组和 state 数组。

查找位置（辅助函数）：

• 计算 hash1 和 hash2。
• 循环遍历，直到找到 key（返回位置）或遇到 EMPTY（说明 key 不存在）。
• 遇到 DELETED 时继续探测，但记录第一个删除位置（可用于插入优化）。

插入（add）：

1. 先检查是否存在（调用查找函数），存在则直接返回。
2. 如果不存在，在查找过程中记录第一个 DELETED 位置（如果有），否则使用最后找到的空位置。
3. 插入元素，更新状态为 OCCUPIED，size++。
4. 检查负载因子（size / capacity），超过阈值（如 0.7）则扩容。

查询（contains）：

• 调用查找函数，如果找到且状态为 OCCUPIED 则返回 True，否则 False。

删除（remove）：

• 调用查找函数找到位置，将状态改为 DELETED（注意：不置空，只改状态），size--。

第5步：动态扩容（再哈希）

当负载因子超过阈值（例如 0.7）时：

• 新建一个更大的数组（通常翻倍，并取一个质数作为新容量）。
• 遍历原数组，将所有状态为 OCCUPIED 的元素重新插入新数组（使用新的容量计算哈希）。
• 注意：DELETED 的元素不插入，从而被清理掉。

第6步：代码实现示例（Python）

class MyHashSet:
    def __init__(self, capacity=5):
        self.capacity = self._next_prime(capacity)
        self.table = [None] * self.capacity
        self.state = [0] * self.capacity  # 0=EMPTY, 1=OCCUPIED, 2=DELETED
        self.size = 0
        self.load_factor_threshold = 0.7

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

    def _hash2(self, key, capacity):
        return 1 + (key % (capacity - 1))

    def _next_prime(self, n):
        # 找一个 >= n 的质数（简单实现，可优化）
        def is_prime(x):
            if x < 2:
                return False
            for i in range(2, int(x**0.5) + 1):
                if x % i == 0:
                    return False
            return True
        while not is_prime(n):
            n += 1
        return n

    def _find_position(self, key):
        # 返回 (位置, 是否找到)
        cap = self.capacity
        h1 = self._hash1(key, cap)
        h2 = self._hash2(key, cap)
        first_deleted = -1
        i = 0
        while i < cap:
            pos = (h1 + i * h2) % cap
            if self.state[pos] == EMPTY:
                return (first_deleted if first_deleted != -1 else pos, False)
            elif self.state[pos] == DELETED:
                if first_deleted == -1:
                    first_deleted = pos
            elif self.state[pos] == OCCUPIED and self.table[pos] == key:
                return (pos, True)
            i += 1
        # 表满（理论上不会发生，因为会先扩容）
        return (-1, False)

    def add(self, key):
        if self.size / self.capacity >= self.load_factor_threshold:
            self._resize()
        pos, found = self._find_position(key)
        if not found:
            self.table[pos] = key
            self.state[pos] = OCCUPIED
            self.size += 1

    def remove(self, key):
        pos, found = self._find_position(key)
        if found:
            self.state[pos] = DELETED
            self.size -= 1

    def contains(self, key):
        _, found = self._find_position(key)
        return found

    def _resize(self):
        new_capacity = self._next_prime(self.capacity * 2)
        new_table = [None] * new_capacity
        new_state = [EMPTY] * new_capacity
        for i in range(self.capacity):
            if self.state[i] == OCCUPIED:
                key = self.table[i]
                cap = new_capacity
                h1 = self._hash1(key, cap)
                h2 = self._hash2(key, cap)
                j = 0
                while j < cap:
                    pos = (h1 + j * h2) % cap
                    if new_state[pos] == EMPTY:
                        new_table[pos] = key
                        new_state[pos] = OCCUPIED
                        break
                    j += 1
        self.table = new_table
        self.state = new_state
        self.capacity = new_capacity

# 状态常量
EMPTY, OCCUPIED, DELETED = 0, 1, 2

第7步：操作示例与复杂度分析

• 每个操作平均时间复杂度 O(1)，最坏 O(n)（当哈希函数极差或表几乎满时）。
• 双重哈希减少了聚集，但需要计算两个哈希值。
• 扩容代价为 O(n)，但摊还分析下仍为 O(1)。

总结：本题实现了基于双重哈希的哈希集合，重点在于理解开放地址法中双重哈希的探测序列、惰性删除的处理以及动态扩容的再哈希过程。