Python 设计 HashSet

假设我们想要设计一个 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 := 新列表
  • 定义一个函数 update()。它将接收键作为参数
  • found := False
  • 对于 bucket 中的每个索引 i 和键 k，执行以下操作：
    • 如果键与 k 相同，则
      • bucket[i]:= 键
      • found:= True
      • 退出循环
    • 如果 found 为 false，则
      • 在 bucket 的末尾插入键
  • 定义一个函数 get()。它将接收键作为参数
    • 对于 bucket 中的每个 k，执行以下操作：
      • 如果 k 与键相同，则
        • 返回 True
      • 返回 False
  • 定义一个函数 remove()。它将接收键作为参数
    • 对于 bucket 中的每个索引 i 和键 k，执行以下操作：
      • 如果键与 k 相同，则
        • 删除 bucket[i]
  • 现在创建自定义 hashSet。它将包含以下几个方法：
  • 如下所示进行初始化：
  • key_space := 2096
  • hash_table:= 一个大小为 key_space 的 Bucket 类型对象的列表
  • 定义一个函数 add()。它将接收键作为参数
    • hash_key:= 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[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

更新于: 2020-07-04

4K+ 浏览量

开启你的 职业生涯

通过完成课程获得认证

立即开始
广告