用Python设计HashSet
假设我们要设计一个HashSet数据结构而不使用任何内置的哈希表库。将有不同的功能，例如-
add(x)-将值x插入HashSet中。
contains(x)-检查HashSet中是否存在值x。
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：=一个新列表
定义一个功能update()。这将需要关键
发现：=错误
对于存储桶中的每个索引i和键k，
在存储桶末尾插入键
bucket[i]：=键
找到：=真
从循环中出来
如果键与k相同，则
如果发现错误，则
定义一个功能get()。这将需要关键
如果k与键相同，则
返回False
返回True
对于存储桶中的每个k，
定义一个功能remove()。这将需要关键
如果键与k相同，则
删除存储桶[i]
对于存储桶中的每个索引i和键k，
现在创建自定义hashSet。几种方法如下
初始化如下-
key_space：=2096
hash_table：=大小为key_space的存储桶类型对象的列表
定义一个功能add()。这将需要关键
hash_key：=键modkey_space
调用hash_table[hash_key]的update(key)
定义一个功能remove()。这将需要关键
hash_key：=keymodkey_space
从hash_table删除键[hash_key]
定义一个功能contains()。这将需要关键
hash_key：=keymodkey_space
返回hash_table的get(key)[hash_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