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+ 瀏覽量

開啟你的 職業生涯

透過完成課程獲得認證

立即開始
廣告

© . All rights reserved.