PythonでHashMapを設計する

組み込みのハッシュテーブルライブラリを使用せずにHashMapを設計するとします。次のようにさまざまな機能があります-

• put（key、value）-これにより、キーに関連付けられた値がHashMapに挿入されます。値がHashMapにすでに存在する場合は、値を更新します。
• get（key）-これは、指定されたキーがマップされている値を返します。それ以外の場合、このマップにキーのマッピングが含まれていない場合は-1を返します。
• remove（key）-このマップにキーのマッピングが含まれている場合、これにより値キーのマッピングが削除されます。

したがって、入力が「初期化後」のようになっている場合は、次のようにputメソッドとgetメソッドを呼び出します-

• put（1、1）;
• put（2、2）;
• get（1）;
• get（3）;
• put（2、1）;
• get（2）;
• remove（2）;
• get（2）;

その場合、出力はそれぞれ1、-1（存在しない）、1、-1（存在しない）になります。

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

• nodeと呼ばれる新しいデータ構造を作成し、それを初期化するために、（key、val、next）のようないくつかのフィールドがあり、nextは最初はnullです
• リンクリストを1つ定義します。次のように、いくつかの方法があります-
• 初期化子を1つ定義します。これは、次のように機能します-
  • prehead：=key=nullおよびval=nullの新しいノードノード
• 関数search（）を定義します。これが鍵となります
• p：=prehead.next
• pがnullでない場合は、
  • p.keyがkeyと同じ場合、
    • return p
  • p：=p.next
• 戻り値なし
• 関数add（）を定義します。これには鍵がかかります、val
• p：=search（key）
• pがnullでない場合、
  • p.val：=val
• それ以外の場合、
  • node：=（key、val）を使用した新しいノード
  • prehead.next：=node、node.next：=prehead.next
• 関数get（）を定義します。これが鍵となります
• p：=search（key）
• pがnullでない場合、
  • return p.val
• それ以外の場合、
  • nullを返す
• 関数の削除を定義します。これが鍵となります
• prev：=prehead
• cur：=prev.next
• curがnullでない場合は、
  • cur.keyがkeyと同じ場合、
    • ループから抜け出す
  • prev：=curr、cur：=cur.next
  • curがnullでない場合、
    • prev.next：=cur.next
• 関数serialize（）を定義します。
• p：=prehead.next
• ret：=新しいリスト
• pがnullでない場合は、
  • 最後に[p.key、p.val]をretに挿入します
  • p：=p.next
• return ret
• カスタムハッシュマップから、次のようにメソッドを定義します-
• 初期化子を1つ定義します。
• サイズ：=1033
• arr：=長さがサイズと同じLinkedList（）の配列
• 関数_hash（）を定義します。これが鍵となります
• リターンキーのmodサイズ
• 関数put（）を定義します。これには重要な価値があります
• h：=_hash（key）
• arr [h]のadd（key、value）
• 関数get（）を定義します。これが鍵となります
• h：=_hash（key）
• ret：=arr [h]のget（key）
• retがnullでない場合、
  • return ret
• それ以外の場合、
  • 戻り値-1
• 関数remove（）を定義します。これが鍵となります
• h：=_hash（key）
• arr[h]からキーを削除します

理解を深めるために、次の実装を見てみましょう-

例

class Node:
   def __init__(self, key, val):
      self.key = key
      self.val = val
      self.next = None
class LinkedList:
   def __init__(self):
      self.prehead = Node(None, None)
   def search(self, key):
      p = self.prehead.next
      while p:
         if p.key == key:
            return p
         p = p.next
      return None
   def add(self, key, val):
      p = self.search(key)
      if p:
         p.val = val
      else:
         node = Node(key, val)
         self.prehead.next, node.next = node, self.prehead.next
   def get(self, key):
      p = self.search(key)
      if p:
         return p.val
      else:
         return None
   def remove(self, key):
      prev = self.prehead
      cur = prev.next
      while cur:
         if cur.key == key:
            break
         prev, cur = cur, cur.next
      if cur:
         prev.next = cur.next
   def serialize(self):
      p = self.prehead.next
      ret = []
      while p:
         ret.append([p.key, p.val])
         p = p.next
      return ret
class MyHashMap:
   def __init__(self):
      self.size = 1033
      self.arr = [LinkedList() for _ in range(self.size)]
   def _hash(self, key):
      return key % self.size
   def put(self, key, value):
      h = self._hash(key)
      self.arr[h].add(key, value)
   def get(self, key):
      h = self._hash(key)
      ret = self.arr[h].get(key)
      if ret is not None:
         return ret
      else:
         return -1
   def remove(self, key):
      h = self._hash(key)
      self.arr[h].remove(key)
ob = MyHashMap()
ob.put(1, 1)
ob.put(2, 2)
print(ob.get(1))
print(ob.get(3))
ob.put(2, 1)
print(ob.get(2))
ob.remove(2)
print(ob.get(2))

入力

ob = MyHashMap()
ob.put(1, 1)
ob.put(2, 2)
print(ob.get(1))
print(ob.get(3))
ob.put(2, 1)
print(ob.get(2))
ob.remove(2)
print(ob.get(2))

出力

1
-1
1
-1