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

题目描述：
设计一个哈希集合（MyHashSet），需要实现以下功能：

• void add(key)：向集合中插入值 key
• void remove(key)：将值 key 从集合中移除
• bool contains(key)：返回集合中是否存在值 key

要求使用双重哈希（double hashing）来解决哈希冲突，这是开放地址法的一种高级形式。哈希表的大小应设置为质数（如1009），负载因子超过0.75时需要自动扩容。

解题步骤：

1. 初始化设计

   • 选择初始容量为1009（质数），创建数组bucket
   • 定义三个特殊标记：REMOVED标记已删除位置，None标记空位置，实际值标记已存储位置
   • 设置负载因子阈值为0.75，当已用位置比例超过此值时触发扩容

2. 哈希函数设计

   • 第一哈希函数：h₁(key) = key % capacity
   • 第二哈希函数：h₂(key) = 1 + (key % (capacity-2))
   • 双重哈希的探测序列：h(key, i) = (h₁(key) + i × h₂(key)) % capacity
   • 这种设计确保当容量与第二哈希函数的模数互质时，能遍历所有位置

3. 添加操作实现

   • 计算key的哈希起始位置，按探测序列查找：
     • 遇到空位置或REMOVED标记时插入key
     • 遇到已存在的相同key时直接返回（集合去重）
   • 插入后检查负载因子，超过阈值时调用resize()扩容

4. 查询操作实现

   • 按相同的探测序列查找key：
     • 遇到实际值且匹配key时返回True
     • 遇到空位置说明key不存在，返回False
     • 遇到REMOVED标记继续探测（因为key可能被后续插入到后面位置）

5. 删除操作实现

   • 查找key所在位置，找到后标记为REMOVED
   • 不能直接标记为空，否则会破坏后续元素的探测链

6. 动态扩容机制

   • 创建新数组（新容量为原容量两倍后的最小质数）
   • 遍历旧数组所有有效元素，重新插入到新数组
   • 重新计算所有元素的哈希位置，利用新的容量值

关键点说明：

• 双重哈希通过两个不同的哈希函数减少聚集现象
• REMOVED标记保持删除后探测链的连续性
• 质数容量确保第二哈希函数能覆盖所有位置
• 动态扩容维持操作的时间复杂度接近O(1)

这种实现平均时间复杂度为O(1)，最坏情况O(n)，但通过双重哈希和动态扩容，在实际使用中能保持高效性能。