在 Python 中设计 HashSet
pythonserver side programmingprogramming更新于 2023/11/10 0:51:00
假设我们想要设计一个 HashSet 数据结构，而不使用任何内置哈希表库。将会有不同的函数，如 −
- add(x) − 将值 x 插入 HashSet。
- contains(x) − 检查值 x 是否存在于 HashSet 中。
- remove(x) − 从 HashSet 中删除 x。如果值在 HashSet 中不存在，则不执行任何操作。
因此，要测试它，请初始化哈希集，然后调用 add(1)、add(3)、contains(1)、contains(2)、add(2)、contains(2)、remove(2)、contains(2)。，则输出将分别为 true(1 存在)、false(2 不存在)、true(2 存在)、false(2 不存在)。
为了解决这个问题，我们将遵循以下步骤 −
- 定义一个名为 Bucket 的数据结构，像下面这样初始化它
- bucket := a new list
- 定义一个函数 update()。这将获取 key
- found := False
- 对于 bucket 中的每个索引 i 和 key k，执行
- 如果 key 与 k 相同，则
- bucket[i]:= key
- found:= True
- 退出循环
- 如果 found 为 false，则
- 在 bucket 末尾插入 key
- 如果 key 与 k 相同，则
- 定义一个函数 get() 。这将获取 key
- 对于 bucket 中的每个 k，执行
- 如果 k 与 key 相同，则
- 返回 True
- 返回 False
- 如果 k 与 key 相同，则
- 对于 bucket 中的每个 k，执行
- 定义一个函数 remove()。这将获取 key
- 对于 bucket 中的每个索引 i 和 key k，执行
- 如果 key 与 k 相同，则
- 删除 bucket[i]
- 如果 key 与 k 相同，则
- 对于 bucket 中的每个索引 i 和 key k，执行
- 现在创建自定义 hashSet。将会有以下几种方法
- 按如下方式初始化 −
- key_space := 2096
- hash_table:= 大小为 key_space 的 bucket 类型对象列表
- 定义一个函数 add()。这将采用 key
- hash_key:= key mod key_space
- 调用 hash_table[hash_key] 的 update(key)
- 定义一个函数 remove()。这将采用 key
- hash_key:= keymodkey_space
- 从 hash_table[hash_key] 中删除 key
- 定义一个函数 contains()。这将获取密钥
- hash_key:= keymodkey_space
- 返回 hash_table[hash_key] 的 get(key)
让我们看看下面的实现以便更好地理解 −
示例
class Bucket: def __init__(self): self.bucket=[] def update(self, key): found=False for i,k in enumerate(self.bucket): if key==k: self.bucket[i]=key found=True break if not found: self.bucket.append(key) def get(self, key): for k in self.bucket: if k==key: return True return False def remove(self, key): for i,k in enumerate(self.bucket): if key==k: del self.bucket[i] class MyHashSet: def __init__(self): self.key_space = 2096 self.hash_table=[Bucket() for i in range(self.key_space)] def add(self, key): hash_key=key%self.key_space self.hash_table[hash_key].update(key) def remove(self, key): hash_key=key%self.key_space self.hash_table[hash_key].remove(key) def contains(self, key): hash_key=key%self.key_space return self.hash_table[hash_key].get(key) ob = MyHashSet() ob.add(1) ob.add(3) print(ob.contains(1)) print(ob.contains(2)) ob.add(2) print(ob.contains(2)) ob.remove(2) print(ob.contains(2))
输入
ob = MyHashSet() ob.add(1) ob.add(3) print(ob.contains(1)) print(ob.contains(2)) ob.add(2) print(ob.contains(2)) ob.remove(2) print(ob.contains(2))
输出
True False True False
