用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：=键mod key_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