LeetCode 题解工作台
设计哈希集合
不使用任何内建的哈希表库设计一个哈希集合（HashSet）。 实现 MyHashSet 类： void add(key) 向哈希集合中插入值 key 。 bool contains(key) 返回哈希集合中是否存在这个值 key 。 void remove(key) 将给定值 key 从哈希集合中删…
5
题型
5
代码语言
3
相关题
当前训练重点
简单 · 数组·哈希·扫描
答案摘要
直接创建一个大小为 的数组，初始时数组中的每个元素都为 `false`，表示哈希集合中不存在该元素。 往哈希集合添加元素时，将数组中对应位置的值置为 `true`；删除元素时，将数组中对应位置的值置为 `false`；当查询元素是否存在时，直接返回数组中对应位置的值即可。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·哈希·扫描 题型思路
题目描述
不使用任何内建的哈希表库设计一个哈希集合（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 <= 106- 最多调用
104次add、remove和contains
解题思路
方法一：静态数组实现
直接创建一个大小为 的数组，初始时数组中的每个元素都为 false，表示哈希集合中不存在该元素。
往哈希集合添加元素时，将数组中对应位置的值置为 true；删除元素时，将数组中对应位置的值置为 false；当查询元素是否存在时，直接返回数组中对应位置的值即可。
以上操作的时间复杂度均为 。
class MyHashSet:
def __init__(self):
self.data = [False] * 1000001
def add(self, key: int) -> None:
self.data[key] = True
def remove(self, key: int) -> None:
self.data[key] = False
def contains(self, key: int) -> bool:
return self.data[key]
# Your MyHashSet object will be instantiated and called as such:
# obj = MyHashSet()
# obj.add(key)
# obj.remove(key)
# param_3 = obj.contains(key)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity depends on bucket count and hash distribution: average O(1) for add, remove, and contains if collisions are minimal; worst-case O(n) if all keys hash to one bucket. Space complexity is proportional to the number of buckets plus the total stored keys. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
They may ask about handling collisions and why a linked list in each bucket works.
- question_mark
Expect questions on trade-offs between array scanning and hash table performance.
- question_mark
You might be prompted to explain worst-case scenarios when all keys hash to one bucket.
常见陷阱
外企场景- error
Not handling duplicate keys correctly in add operations, causing redundant entries.
- error
Ignoring collision handling, which can lead to incorrect contains or remove results.
- error
Choosing too few buckets, increasing linear scanning time and degrading performance.
进阶变体
外企场景- arrow_right_alt
Implement a HashSet with open addressing instead of linked list buckets.
- arrow_right_alt
Support dynamic resizing of buckets when load factor exceeds a threshold.
- arrow_right_alt
Implement a HashMap variant that stores key-value pairs with similar hashing strategy.