Thiết kế HashMap bằng Python

Giả sử chúng ta muốn thiết kế một HashMap mà không cần sử dụng bất kỳ thư viện bảng băm nào được tích hợp sẵn. Sẽ có các chức năng khác nhau như sau -

• put (key, value) - Thao tác này sẽ chèn một giá trị được liên kết với key vào HashMap. Nếu giá trị đã tồn tại trong HashMap, hãy cập nhật giá trị.
• get (key) - Thao tác này sẽ trả về giá trị mà khóa đã chỉ định được ánh xạ, ngược lại -1 khi bản đồ này không chứa ánh xạ cho khóa.
• remove (key) - Thao tác này sẽ Xóa ánh xạ cho khóa giá trị nếu bản đồ này chứa ánh xạ cho khóa.

Vì vậy, nếu đầu vào giống như Sau khi khởi tạo, hãy gọi phương thức put và get như sau -

• đặt (1, 1);
• đặt (2, 2);
• lấy (1);
• lấy (3);
• đặt (2, 1);
• lấy (2);
• loại bỏ (2);
• lấy (2);

thì đầu ra sẽ lần lượt là 1, -1 (không có), 1, -1 (không có).

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Tạo một cấu trúc dữ liệu mới được gọi là nút và để khởi tạo nó, sẽ có một số trường giống như (khóa, val, tiếp theo), tiếp theo ban đầu là rỗng
• Xác định một danh sách được Liên kết, có một số phương pháp như sau -
• Xác định một trình khởi tạo, điều này sẽ hoạt động như sau -
  • prehead:=a new node Node với key =null và val =null
• Xác định một hàm tìm kiếm (). Điều này sẽ quan trọng
• p:=prehead.next
• trong khi p không rỗng, hãy thực hiện
  • nếu p.key giống với key, thì
    • trả về p
  • p:=p.next
• trả lại Không có
• Xác định một hàm add (). Điều này sẽ quan trọng, val
• p:=search (key)
• nếu p không rỗng, thì
  • p.val:=val
• nếu không,
  • node:=new Node with (key, val)
  • prehead.next:=node, node.next:=prehead.next
• Định nghĩa một hàm get (). Điều này sẽ quan trọng
• p:=search (key)
• nếu p không rỗng, thì
  • trả về p.val
• nếu không,
  • trả về null
• Xác định một chức năng loại bỏ. Điều này sẽ quan trọng
• before:=prehead
• cur:=pres.next
• trong khi cur không phải là null, hãy thực hiện
  • nếu cur.key giống với key, thì
    • ra khỏi vòng lặp
  • prev:=curr, cur:=cur.next
  • nếu cur không null, thì
    • prev.next:=cur.next
• Xác định một hàm serialize ().
• p:=prehead.next
• ret:=một danh sách mới
• trong khi p không rỗng, hãy thực hiện
  • chèn [p.key, p.val] vào ret ở cuối
  • p:=p.next
• trả lời lại
• Từ bản đồ băm tùy chỉnh, xác định các phương pháp như sau -
• Xác định một trình khởi tạo.
• kích thước:=1033
• arr:=một mảng LinkedList () có độ dài bằng với kích thước
• Xác định một hàm _hash (). Điều này sẽ quan trọng
• trả về kích thước bản sửa đổi chính
• Định nghĩa một hàm put (). Điều này sẽ lấy chìa khóa, giá trị
• h:=_hash (phím)
• thêm (khóa, giá trị) của arr [h]
• Định nghĩa một hàm get (). Điều này sẽ quan trọng
• h:=_hash (phím)
• ret:=get (key) của arr [h]
• nếu ret không rỗng, thì
  • trả lời lại
• nếu không,
  • trả về -1
• Xác định một hàm remove (). Điều này sẽ quan trọng
• h:=_hash (phím)
• xóa khóa khỏi arr [h]

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

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))

Đầu vào

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))

Đầu ra

1
-1
1
-1