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

题目描述

设计一个哈希集合（MyHashSet），不使用任何内置的哈希表库。它应该包含以下功能：

• add(key): 向哈希集合中插入值 key。
• remove(key): 从哈希集合中移除值 key。如果集合中不存在该值，则什么也不做。
• contains(key): 返回哈希集合中是否存在这个值 key。

其中，key 的取值范围是 [0, 10^6]，且操作的总次数最多为 10^4 次。

题目解析

这是一个基础但重要的哈希算法设计题。题目要求我们自己实现一个哈希集合，其本质是模拟一个不存储重复元素的集合数据结构。由于我们不能使用编程语言内置的哈希集合（如 HashSet），所以需要自己处理核心问题：如何快速地将一个值映射到一个存储位置，并处理可能发生的哈希冲突。

核心思路

我们可以采用最经典的哈希表实现方法之一：链地址法。

1. 选择一个哈希函数：将任意范围的大数值（这里是 0 到 10^6）映射到一个固定大小的数组索引上。
2. 创建一个“桶”数组：数组的每个位置（我们称之为“桶”）不直接存储单个元素，而是存储一个链表（或其他动态结构，如列表）。
3. 处理冲突：当不同的 key 被哈希函数计算到同一个数组索引（即同一个桶）时，我们就把它们依次放入这个桶对应的链表中。这样，即使发生了冲突，我们也能在一个桶内部通过线性搜索找到目标元素。

逐步设计

第1步：确定数据结构与参数

• 设定一个固定大小的桶数组，每个桶是一个链表。在Java中可以用 LinkedList<Integer>，在Python中可以用列表 list，在C++中可以用 vector<int> 或 list<int>。
• 确定数组大小。这里操作次数是 10^4，为了平衡时间和空间效率，通常选择一个质数作为桶的数量，可以减少哈希冲突。我们可以选择 1009 或 997 等接近1000的质数。
• 选择一个简单的哈希函数。最常用且简单的是取模运算：hash(key) = key % BASE，其中 BASE 就是我们选择的桶数组大小。

第2步：详细设计操作

1. 初始化 (__init__ 或构造函数)：

   • 创建一个大小为 BASE 的数组 buckets，每个元素初始化为一个空的链表。

2. 添加 (add)：

   • 计算 key 的哈希值 index = key % BASE。
   • 找到对应的桶 buckets[index]。
   • 遍历这个链表，检查 key 是否已经存在。如果不存在，则将 key 添加到链表的末尾。这样做保证了集合元素的唯一性。

3. 删除 (remove)：

   • 计算 key 的哈希值 index = key % BASE。
   • 找到对应的桶 buckets[index]。
   • 遍历这个链表，找到第一个值等于 key 的节点，将其从链表中移除。如果没找到，就什么都不做。

4. 查询 (contains)：

   • 计算 key 的哈希值 index = key % BASE。
   • 找到对应的桶 buckets[index]。
   • 遍历这个链表，检查是否有节点的值等于 key。如果有，返回 true，否则返回 false。

第3步：复杂度分析

• 时间复杂度：平均情况下，每个操作的时间复杂度是 O(1)。这里的“平均”是基于哈希函数将元素均匀地分散到各个桶中，使得每个桶内的链表长度大致为 N / BASE（N 是元素个数）。在最坏情况下（所有元素都被哈希到同一个桶），时间复杂度会退化到 O(N)。
• 空间复杂度：O(BASE + N)，BASE 是桶数组的大小，N 是添加到集合中的不重复元素数量。

第4步：代码示例（Python）

class MyHashSet:

    def __init__(self):
        # 选择一个质数作为桶的数量
        self.BASE = 997
        # 初始化一个桶数组，每个桶是一个列表（作为链表使用）
        self.buckets = [[] for _ in range(self.BASE)]

    def _hash(self, key: int) -> int:
        """计算key的哈希值，即它应该放入哪个桶"""
        return key % self.BASE

    def add(self, key: int) -> None:
        index = self._hash(key)
        bucket = self.buckets[index]
        # 检查key是否已存在
        for item in bucket:
            if item == key:
                return  # 已存在，直接返回
        # 不存在，则添加
        bucket.append(key)

    def remove(self, key: int) -> None:
        index = self._hash(key)
        bucket = self.buckets[index]
        # 查找并移除key
        for i, item in enumerate(bucket):
            if item == key:
                # 找到了，移除它
                bucket.pop(i)
                return

    def contains(self, key: int) -> bool:
        index = self._hash(key)
        bucket = self.buckets[index]
        # 在桶中查找key
        for item in bucket:
            if item == key:
                return True
        return False

第5步：进一步思考与优化

1. 动态扩容：如果元素数量 N 远大于 BASE，会导致每个桶的链表变长，性能下降。一个更完善的实现应该包含动态扩容：当 N / BASE 超过某个阈值（如负载因子 0.75）时，就创建一个新的更大的桶数组（例如原来的两倍），然后将所有现有元素重新哈希到新数组中。这能维持平均 O(1) 的操作时间。本题由于操作次数有限，固定大小通常足够。
2. 更好的链表：可以用一个自定义的链表节点类来实现桶内的链表，这样删除操作（remove）的时间复杂度可以稳定在 O(1)，因为我们可以通过维护节点的前驱来快速删除。在上面的Python列表实现中，pop(i) 操作是 O(L) 的（L 是桶的大小），但在数据量不大时影响很小。
3. 哈希函数：对于整数键，取模运算简单有效。如果键是其他类型（如字符串），需要设计更复杂的哈希函数来保证良好的分布性。

通过这个练习，你掌握了哈希表最核心的实现原理之一：通过哈希函数将数据分散存储，用链表（链地址法）解决哈希冲突。这是理解更复杂哈希结构（如哈希映射、布隆过滤器等）的重要基础。