题目大意
#
要求不使用内建的哈希表库，自行实现一个哈希集合（HashSet）。
满足以下操作：
- void add(key) 向哈希集合中插入值 key 。
- bool contains(key) 返回哈希集合中是否存在这个值 key 。
- void remove(key) 将给定值 key 从哈希集合中删除。如果哈希集合中没有这个值，什么也不做。
解题思路
#
可以利用「数组+链表」的方式实现哈希集合。
定义一个一维长度为 buckets 的二维数组 table。第一维度用于计算哈希函数，为 key 分桶。第二个维度用于寻找 key 存放的具体位置。第二维度的数组会根据 key 值动态增长，模拟真正的链表。
代码
#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
|
class MyHashSet:
def __init__(self):
self.buckets = 1003
self.table = [[] for _ in range(self.buckets)]
def hash(self, key):
return key % self.buckets
def add(self, key: int) -> None:
hash_key = self.hash(key)
if key in self.table[hash_key]:
return
self.table[hash_key].append(key)
def remove(self, key: int) -> None:
hash_key = self.hash(key)
if key not in self.table[hash_key]:
return
self.table[hash_key].remove(key)
def contains(self, key: int) -> bool:
hash_key = self.hash(key)
return key in self.table[hash_key]
|