ออกแบบ HashMap ใน Python

สมมติว่าเราต้องการออกแบบ HashMap โดยไม่ต้องใช้ไลบรารีตารางแฮชในตัว โดยจะมีฟังก์ชันต่างๆ ดังนี้ -

• put(key, value) − สิ่งนี้จะแทรกค่าที่เกี่ยวข้องกับคีย์ลงใน HashMap หากค่ามีอยู่แล้วใน HashMap ให้อัปเดตค่า
• get(key) − สิ่งนี้จะคืนค่าที่คีย์ที่ระบุถูกจับคู่ มิฉะนั้น -1เมื่อแผนที่นี้ไม่มีการแมปสำหรับคีย์
• remove(key) − สิ่งนี้จะลบการแมปสำหรับคีย์ค่า หากแผนที่นี้มีการจับคู่สำหรับคีย์

ดังนั้นหากอินพุตเป็นเหมือน After initialization ให้เรียกใช้เมธอด put and get ดังนี้ −

• ใส่(1, 1);
• ใส่(2, 2);
• get(1);
• get(3);
• ใส่(2, 1);
• get(2);
• ลบ(2);
• get(2);

จากนั้นผลลัพธ์จะเป็น 1, -1(ไม่แสดง), 1, -1(ไม่แสดง) ตามลำดับ

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• สร้างโครงสร้างข้อมูลใหม่ที่เรียกว่า node และเพื่อเริ่มต้น จะมีบาง fieldlike(key, val, next) , next เป็นค่าว่างในขั้นต้น
• กำหนดหนึ่งรายการที่เชื่อมโยง มีไม่กี่วิธีดังต่อไปนี้ −
• กำหนดตัวเริ่มต้นหนึ่งตัว ซึ่งจะทำงานดังนี้ −
  • prehead :=โหนดโหนดใหม่ที่มีคีย์ =null และ val =null
• กำหนดฟังก์ชันการค้นหา () นี่จะใช้เวลาที่สำคัญ
• p :=prehead.next
• ในขณะที่ p ไม่เป็นค่าว่าง ให้ทำ
  • ถ้า p.key เหมือนกับ key แล้ว
    • คืนสินค้า
  • p :=p.next
• ไม่ส่งคืน
• กำหนดฟังก์ชัน add() นี่จะใช้เวลาที่สำคัญ val
• p :=ค้นหา(คีย์)
• ถ้า p ไม่เป็นค่าว่าง
  • p.val :=วาล
• มิฉะนั้น
  • โหนด :=โหนดใหม่พร้อม (คีย์ val)
  • prehead.next :=โหนด node.next :=prehead.next
• กำหนดฟังก์ชัน get() นี่จะใช้เวลาที่สำคัญ
• p :=ค้นหา(คีย์)
• ถ้า p ไม่เป็นค่าว่าง
  • คืน p.val
• มิฉะนั้น
  • คืนค่า null
• กำหนดฟังก์ชันลบ นี่จะใช้เวลาที่สำคัญ
• ก่อนหน้า :=พรีเฮด
• cur :=prev.next
• ในขณะที่ cur ไม่เป็นค่าว่าง ให้ทำ
  • ถ้า cur.key เหมือนกับ key แล้ว
    • ออกมาจากวงจร
  • prev :=curr, cur :=cur.next
  • ถ้า cur ไม่เป็นค่าว่าง
    • prev.next :=cur.next
• กำหนดฟังก์ชัน serialize()
• p :=prehead.next
• ret :=รายการใหม่
• ในขณะที่ p ไม่เป็นค่าว่าง ให้ทำ
  • ใส่ [p.key, p.val] ลงใน ret ตอนท้าย
  • p :=p.next
• คืนสินค้า
• จาก hashmap ที่กำหนดเอง ให้กำหนดวิธีการดังต่อไปนี้ −
• กำหนดตัวเริ่มต้นหนึ่งตัว
• ขนาด :=1033
• arr :=อาร์เรย์ของ LinkedList() ที่มีความยาวเท่ากับขนาด
• กำหนดฟังก์ชัน _hash() นี่จะใช้เวลาที่สำคัญ
• คืนขนาดม็อดคีย์
• กำหนดฟังก์ชัน put() นี้จะใช้เวลาที่สำคัญค่า
• h :=_hash(คีย์)
• เพิ่ม (คีย์, ค่า) ของ arr[h]
• กำหนดฟังก์ชัน get() นี่จะใช้เวลาที่สำคัญ
• h :=_hash(คีย์)
• ret :=get(key) ของ arr[h]
• ถ้า ret ไม่ใช่ null แล้ว
  • คืนสินค้า
• มิฉะนั้น
  • คืน -1
• กำหนดฟังก์ชัน remove() นี่จะใช้เวลาที่สำคัญ
• h :=_hash(คีย์)
• ลบคีย์จาก 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