哈希算法题目：设计哈希集合

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

• add(key): 向哈希集合中插入值 key
• remove(key): 将哈希集合中值为 key 的元素移除
• contains(key): 判断哈希集合中是否包含值为 key 的元素

解题过程：

1. 基础设计思路
   哈希集合的核心是通过哈希函数将键映射到存储位置。由于不同的键可能映射到同一位置（哈希冲突），我们需要解决冲突的方案。常见方法有链地址法（拉链法）和开放地址法，这里我们使用链地址法。

2. 选择哈希函数和数据结构

• 哈希函数：选择简单的取模运算 key % base，其中 base 是一个质数（如 769），以减少冲突
• 存储结构：每个位置使用链表（或数组）存储实际元素，冲突的键会被放入同一位置的链表中

3. 详细步骤
   a. 初始化：

   • 定义一个固定大小（如 769）的数组 buckets
   • 每个数组元素初始化为空链表（Python 中用列表模拟）

   b. 哈希计算：

   • 对任意键 key，计算 index = key % 769
   • 此索引决定键应存入哪个桶（bucket）

   c. 添加元素（add）：

   • 计算 key 的哈希索引
   • 检查该索引对应的链表中是否已存在 key
   • 若不存在，则将 key 添加到链表末尾

   d. 删除元素（remove）：

   • 计算 key 的哈希索引
   • 遍历该索引对应的链表，找到并删除 key

   e. 判断包含（contains）：

   • 计算 key 的哈希索引
   • 遍历对应链表，检查 key 是否存在

4. 复杂度分析

   • 平均情况：假设键均匀分布，每个桶大小为 n/base，操作时间复杂度为 O(n/base)
   • 最坏情况：所有键冲突，退化为单链表，时间复杂度 O(n)
   • 空间复杂度：O(base + n)，base 是桶的数量，n 是元素数量

5. 优化考虑

   • 动态调整桶数量：当元素数量过多时，扩容并重新哈希，保持低负载因子
   • 链表优化：可将链表替换为平衡二叉搜索树，确保最坏情况时间复杂度为 O(log n)

通过以上步骤，我们实现了一个高效、可靠的哈希集合结构。