哈希集合设计

题目描述：请你设计一个哈希集合（HashSet），实现以下功能：

• add(key)：向集合中插入一个值
• remove(key)：从集合中删除一个值
• contains(key)：判断集合中是否包含该值

要求：不使用任何内置的哈希表库，需要处理哈希冲突。

解题过程：

1. 基础设计思路

   • 哈希集合的核心是使用数组存储数据，通过哈希函数将键映射到数组索引
   • 由于不同的键可能映射到相同索引（哈希冲突），需要解决冲突的方法
   • 这里我们选择"链地址法"：每个数组位置存储一个链表，相同索引的键值对放在同一链表中

2. 选择哈希函数和确定桶数量

   • 选择简单的取模哈希函数：hash(key) = key % base
   • 桶数量（base）选择质数769，可以减少哈希冲突的概率

3. 数据结构定义

   class MyHashSet:
       def __init__(self):
           self.base = 769  # 桶数量
           self.data = [[] for _ in range(self.base)]  # 初始化空链表数组
   

4. 哈希函数实现

   def _hash(self, key):
       return key % self.base
   

5. add操作实现

   • 计算key的哈希值，确定在哪个桶（链表）
   • 遍历该链表：
     • 如果找到相同的key，直接返回（集合元素唯一性）
     • 如果没找到，在链表末尾添加新key

   def add(self, key):
       h = self._hash(key)
       for item in self.data[h]:
           if item == key:  # 已存在，不重复添加
               return
       self.data[h].append(key)  # 不存在，添加到链表末尾
   

6. remove操作实现

   • 计算哈希值，定位到对应桶
   • 遍历链表，找到要删除的key并移除

   def remove(self, key):
       h = self._hash(key)
       for i, item in enumerate(self.data[h]):
           if item == key:
               del self.data[h][i]  # 删除找到的元素
               return
   

7. contains操作实现

   • 计算哈希值，在对应链表中线性搜索

   def contains(self, key):
       h = self._hash(key)
       for item in self.data[h]:
           if item == key:
               return True
       return False
   

8. 时间复杂度分析

   • 理想情况（均匀分布）：每个桶的链表长度接近O(1)
   • 最坏情况（所有key哈希冲突）：退化为O(n)的链表操作
   • 通过选择合适的桶数量和哈希函数，可以保持平均O(1)的时间复杂度

这个设计平衡了空间效率和时间效率，通过链地址法优雅地解决了哈希冲突问题。