文章目录1. 题目1. 题目
1.1 示例1.2 说明1.3 限制 2. 解法一(分离链接法)
2.1 分析2.2 解答 3. 解法二(线性查找法)
3.1 分析3.2 解答
不使用任何内建的哈希表库设计一个哈希集合(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]
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)