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。
  • 定義一個連結串列，包含以下幾個方法：
  • 定義一個初始化器，其工作原理如下：
    • prehead := 一個新的節點 Node，其中 key = null，val = null
  • 定義一個函式 search()。這將採用鍵。
  • p := prehead.next
  • 當 p 不為 null 時，執行以下操作：
    • 如果 p.key 與 key 相同，則
      • 返回 p
    • p := p.next
  • 返回 None
  • 定義一個函式 add()。這將採用鍵和值。
  • p := search(key)
  • 如果 p 不為 null，則
    • p.val := val
  • 否則，
    • node := 一個新的節點，包含 (key, val)
    • prehead.next := node，node.next := prehead.next
  • 定義一個函式 get()。這將採用鍵。
  • p := search(key)
  • 如果 p 不為 null，則
    • 返回 p.val
  • 否則，
    • 返回 null
  • 定義一個函式 remove。這將採用鍵。
  • 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
  • 返回 ret
  • 從自定義雜湊對映中，定義以下方法：
  • 定義一個初始化器。
  • size := 1033
  • arr := 一個 LinkedList 陣列，其長度與 size 相同
  • 定義一個函式 _hash()。這將採用鍵。
  • 返回 key mod size
  • 定義一個函式 put()。這將採用鍵和值。
  • h := _hash(key)
  • arr[h] 的 add(key, value)
  • 定義一個函式 get()。這將採用鍵。
  • h := _hash(key)
  • ret := arr[h] 的 get(key)
  • 如果 ret 不為 null，則
    • 返回 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

更新於：2020年7月4日

2K+ 次瀏覽

啟動您的 職業生涯

透過完成課程獲得認證

開始
廣告
© . All rights reserved.