文章目录
1. 题目
不使用任何内建的哈希表库设计一个哈希集合（HashSet）。
实现 MyHashSet 类：
-
void add(key)向哈希集合中插入值key； -
bool contains(key)返回哈希集合中是否存在这个值key； -
void remove(key)将给定值key从哈希集合中删除。如果哈希集合中没有这个值，什么也不做。
1.1 示例
输入：
["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 ，（已移除）
1.2 说明
- **来源：**力扣（LeetCode）
- 链接：https://leetcode-cn.com/problems/design-hashset
1.3 限制
- 0 ≤ key ≤ 1 0 6 0 \le \text{key} \le 10^6 0≤key≤106
- 最多调用
1
0
4
10^4
104 次
add、contains和remove方法
2. 解法一（分离链接法）
2.1 分析
实际上，基于哈希表实现的集合与映射，二者的实现原理基本相同，区别基本仅在于映射中保存的是键值对，而集合中保存的只有键。
因此，本文给出的两种实现和【LeetCode 哈希表专项】设计哈希映射（706）中的解答基本一致，详细分析同样请参考：【数据结构Python描述】仿照Python解释器使用哈希表手动实现一个字典。
2.2 解答
下面使用链表作为每个 bucket 发生哈希碰撞时所使用的二级容器。
from random import randrange
class _ListNode:
def __init__(self, key=0, next=None):
self.key = key
self.next = next
class _LinkedList:
def __init__(self):
self.head = None
self.tail = None
self.n = 0
def append(self, key: int):
node = _ListNode(key)
if self.head is None:
self.head = node
self.tail = node
else:
self.tail.next = node
self.tail = self.tail.next
self.n += 1
def remove(self, key: int):
dummy = _ListNode()
dummy.next = self.head
predecessor, cursor = dummy, dummy.next
while cursor:
if cursor.key == key:
predecessor.next = cursor.next
self.n -= 1
self.head = dummy.next
return
predecessor, cursor = cursor, cursor.next
raise KeyError('Key does not exist!')
def __len__(self):
return self.n
class MyHashSet:
def __init__(self, cap=11, p=109345121):
"""创建一个空的映射"""
self._table = [_LinkedList() for _ in range(cap)]
self._n = 0
self._prime = p # MAD压缩函数中大于哈希表容量的大质数
self._scale = 1 + randrange(p - 1) # MAD压缩函数中的缩放系数a
self._shift = randrange(p) # MAD压缩函数中的偏移系数b
def _hash_function(self, key):
"""哈希函数"""
return (self._scale * hash(key) + self._shift) % self._prime % len(self._table)
def __len__(self):
return self._n
def contains(self, key):
j = self._hash_function(key)
bucket = self._table[j]
cursor = bucket.head
while cursor:
if cursor.key == key:
return True
cursor = cursor.next
return False
def add(self, key):
j = self._hash_function(key)
size = len(self._table[j])
bucket = self._table[j]
cursor = bucket.head
while cursor:
if cursor.key == key:
return
cursor = cursor.next
self._table[j].append(key) # 集合中不存在键key
if len(self._table[j]) > size: # key为新的元素
self._n += 1
if self._n > len(self._table) // 2: # 确保负载系数小于0.5
self._resize(2 * len(self._table) - 1) # 通常2 * n - 1为质数
def remove(self, key):
j = self._hash_function(key)
bucket = self._table[j]
try:
bucket.remove(key)
self._n -= 1
return
except KeyError:
return
def _resize(self, cap):
"""将哈希表容量调整为cap"""
old = list(self) # 通过迭代获得已有的所有键值对
self._table = [_LinkedList() for _ in range(cap)]
self._n = 0
for key in old:
self.add(key)
def __iter__(self):
for bucket in self._table:
cursor = bucket.head
while cursor:
yield cursor.key
cursor = cursor.next
需要注意的是，上述解法在 LeetCode 提交时，有时可以通过有时不可以通过，但单独考察不通过的测试案例时，对比上述解答的输出和期望输出又没有发现区别，希望和看到的小伙伴一起交流一下。
3. 解法二（线性查找法）
3.1 分析
详细分析请参考：【数据结构Python描述】仿照Python解释器使用哈希表手动实现一个字典。
3.2 解答
from random import randrange
class MyHashSet:
_AVAIL = object() # 哨兵标识，用于标识被键值对被删除的哈希表单元
def __init__(self, cap=11, p=109345121):
"""初始化一个空集合"""
self._table = [None for _ in range(cap)]
self._n = 0
self._prime = p
self._scale = 1 + randrange(p - 1)
self._shift = randrange(p)
def _hash_function(self, key):
"""哈希函数"""
return (self._scale * hash(key) + self._shift) % self._prime % len(self._table)
def _is_available(self, j):
"""判断哈希表索引为j的单元处是否引用None或者引用的业务元素被删除"""
return self._table[j] is None or self._table[j] is MyHashSet._AVAIL
def _find_slot(self, j, key):
"""
查找哈希表索引为j的单元处是否有元素key，
该方法的返回值为一个二元组，且返回情况如下：
- 当在索引为j的哈希表单元处找到元素key，则返回(True, j)，
- 当未在哈希表任何单元处找到元素key，则返回(False, index)，index表示第一个可用单元
"""
first_avail = None
while True:
if self._is_available(j):
if first_avail is None:
first_avail = j
if self._table[j] is None:
return False, first_avail
elif key == self._table[j]:
return True, j
j = (j + 1) % len(self._table)
def add(self, key: int) -> None:
j = self._hash_function(key)
found, s = self._find_slot(j, key)
if not found:
self._table[s] = key
self._n += 1
else:
return
if self._n > len(self._table) // 2:
self._resize(2 * len(self._table) - 1)
def _resize(self, cap: int):
old = list(self)
self._table = [None for _ in range(cap)]
self._n = 0
for key in old:
self.add(key)
def remove(self, key: int) -> None:
j = self._hash_function(key)
found, s = self._find_slot(j, key)
if not found:
return
self._table[s] = MyHashSet._AVAIL
self._n -= 1
if self._n // 2 < len(self._table):
self._resize((len(self._table) + 1) // 2)
def contains(self, key: int) -> bool:
j = self._hash_function(key)
found, s = self._find_slot(j, key)
if not found:
return False
else:
return True
def __iter__(self):
size = len(self._table)
for j in range(size):
if not self._is_available(j):
yield self._table[j]