设计哈希集合

难度: Easy

不使用任何内建的哈希表库设计一个哈希集合（HashSet）。

实现 MyHashSet 类：

void add(key) 向哈希集合中插入值 key 。
bool contains(key) 返回哈希集合中是否存在这个值 key 。
void remove(key) 将给定值 key 从哈希集合中删除。如果哈希集合中没有这个值，什么也不做。

示例：

输入：
["MyHashSet", "add", "add", "contains", "contains", "add", "contains", "remove", "contains"]
[[], [1], [2], [1], [3], [2], [2], [2], [2]]
输出：
[null, null, null, true, false, null, true, null, false]

解释：
MyHashSet myHashSet = new MyHashSet();
myHashSet.add(1);      // set = [1]
myHashSet.add(2);      // set = [1, 2]
myHashSet.contains(1); // 返回 True
myHashSet.contains(3); // 返回 False ，（未找到）
myHashSet.add(2);      // set = [1, 2]
myHashSet.contains(2); // 返回 True
myHashSet.remove(2);   // set = [1]
myHashSet.contains(2); // 返回 False ，（已移除）

提示：

0 <= key <= 10⁶
最多调用 10⁴ 次 add、remove 和 contains

Submission

运行时间: 85 ms

内存: 21.3 MB

class MyHashSet:
    def __init__(self):
        self.size = 1000
        self.data = [[] for _ in range(self.size)]

    def add(self, key: int) -> None:
        if self.contains(key):
            return
        idx = self.hash(key)
        self.data[idx].append(key)

    def remove(self, key: int) -> None:
        if not self.contains(key):
            return
        idx = self.hash(key)
        self.data[idx].remove(key)

    def contains(self, key: int) -> bool:
        idx = self.hash(key)
        return any(v == key for v in self.data[idx])

    def hash(self, key) -> int:
        return key % self.size

Explain

这个解决方案通过使用一个数组data来模拟哈希表的功能，每个数组元素是一个列表，用来处理哈希冲突。初始时，数组的长度被设置为1000，并且每个槽位初始化为空列表。哈希函数通过取模运算将键值映射到一个数组索引。添加、删除和检查键值存在性的操作都依赖于这个哈希函数。如果键已存在于集合中，则忽略添加操作。删除操作只有在键存在时才进行。检查键的存在性通过遍历特定索引下的列表完成。

时间复杂度: O(N) in worst case; O(1) on average

空间复杂度: O(N)

class MyHashSet:
    def __init__(self):
        self.size = 1000  # 设定哈希表的基础大小
        self.data = [[] for _ in range(self.size)]  # 初始化哈希表的存储结构

    def add(self, key: int) -> None:
        if self.contains(key):
            return  # 如果key已存在则不重复添加
        idx = self.hash(key)
        self.data[idx].append(key)  # 将key添加到对应的列表

    def remove(self, key: int) -> None:
        if not self.contains(key):
            return  # 如果key不存在则不做操作
        idx = self.hash(key)
        self.data[idx].remove(key)  # 从对应的列表中移除key

    def contains(self, key: int) -> bool:
        idx = self.hash(key)
        return any(v == key for v in self.data[idx])  # 检查对应列表中是否存在key

    def hash(self, key) -> int:
        return key % self.size  # 哈希函数：使用取模运算

Explore

选择1000作为初始哈希表的大小是基于一般应用情境下的性能与空间效率的折中考虑。这个大小能够在保持较低的冲突率的同时，也不会占用过多的内存空间。此外，1000是一个足够大的数，可以减少哈希冲突，从而提高数据访问的速度。然而，这个值并不是固定的，实际应用中可以根据数据量和访问模式的不同进行调整。

链地址法相比开放寻址法，有几个显著的优点：首先，链地址法在处理哈希冲突时，通过链表可以容易地添加和删除元素，这使得操作相对简单；其次，链地址法不会因为删除操作而产生‘删除孔’，维持性能稳定；最后，链地址法对加载因子的敏感性较低，即使负载较高时也能维持较好的性能。而开放寻址法在负载因子增高时性能下降较快，且处理删除操作较为复杂。

是的，如果哈希集合中的元素数量远超过初始大小，将考虑实现动态扩容。动态扩容是通过创建一个更大的哈希表并重新散列所有现有元素来完成的。这样可以减少哈希冲突，维持或提升操作的效率。动态扩容通常会在加载因子（即元素数量与哈希表大小的比率）达到一定阈值时触发，例如常见的阈值是0.75。这样的设计可以使哈希集合在元素数量增加时仍然保持较高的性能。