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が存在しない）になります。

これを解決するには、次の手順に従います-

• バケットと呼ばれる1つのデータ構造を定義し、以下のように初期化します
• バケット：=新しいリスト
• 関数update（）を定義します。これが鍵となります
• found：=False
• バケット内の各インデックスiとキーkについて、実行します
  • キーがkと同じ場合、
    • バケツ[i]：=キー
    • found：=True
    • ループから抜け出す
  • falseが見つかった場合は、
    • バケットの最後にキーを挿入します
• 関数get（）を定義します。これには鍵がかかります
  • バケット内のkごとに、
    • kがキーと同じ場合、
      • Trueを返す
    • Falseを返す
• 関数remove（）を定義します。これには鍵がかかります
  • バケット内の各インデックスiとキーkについて、実行します
    • キーがkと同じ場合、
      • バケットを削除[i]
• 次に、カスタムhashSetを作成します。次のような方法がいくつかあります
• これを次のように初期化します-
• key_space：=2096
• hash_table：=サイズkey_spaceのバケットタイプオブジェクトのリスト
• 関数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