Thiết kế HashSet bằng Python

Giả sử chúng ta muốn thiết kế một cấu trúc dữ liệu HashSet mà không sử dụng bất kỳ tablelibraries băm tích hợp nào. Sẽ có các chức năng khác nhau như -

• add (x) - Chèn giá trị x vào HashSet.
• chứa (x) - Kiểm tra xem giá trị x có trong HashSet hay không.
• remove (x) - Xóa x khỏi HashSet. Trong trường hợp giá trị không tồn tại trong HashSet, không làm gì cả.

Vì vậy, để kiểm tra nó Khởi tạo bộ băm, sau đó gọi thêm (1), thêm (3), chứa (1), chứa (2), thêm (2), chứa (2), loại bỏ (2), chứa (2 )., thì kết quả đầu ra sẽ lần lượt là true (1 là có), false (2 là không có), true (2 là), false (2 là không có).

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

• Xác định một cấu trúc dữ liệu được gọi là Nhóm, Khởi tạo cấu trúc đó như bên dưới
• bucket:=một danh sách mới
• Xác định một bản cập nhật chức năng (). Điều này sẽ quan trọng
• tìm thấy:=Sai
• đối với mỗi chỉ mục i và khóa k trong nhóm, hãy thực hiện
  • nếu khoá giống với k, thì
    • bucket [i]:=key
    • tìm thấy:=True
    • ra khỏi vòng lặp
  • nếu được tìm thấy là sai, thì
    • chèn khóa vào cuối nhóm
• Định nghĩa một hàm get (). Điều này sẽ lấy chìa khóa
  • đối với mỗi k trong thùng, thực hiện
    • nếu k giống với khóa, thì
      • trả về True
    • trả về Sai
• Xác định một hàm remove (). Điều này sẽ lấy chìa khóa
  • đối với mỗi chỉ mục i và khóa k trong nhóm, hãy thực hiện
    • nếu khoá giống với k, thì
      • xóa nhóm [i]
• Bây giờ hãy tạo hashSet tùy chỉnh. Sẽ có một số phương pháp như sau
• Khởi tạo điều này như sau -
• key_space:=2096
• hash_table:=danh sách đối tượng loại thùng có kích thước key_space
• Xác định một hàm add (). Điều này sẽ lấy chìa khóa
  • hash_key:=key mod key_space
  • cập nhật cuộc gọi (khóa) của hash_table [hash_key]
• Xác định một hàm remove (). Điều này sẽ lấy chìa khóa
  • hash_key:=keymodkey_space
  • xóa khóa khỏi hash_table [hash_key]
• Xác định một hàm chứa (). Điều này sẽ lấy chìa khóa
  • hash_key:=keymodkey_space
  • trả về get (key) của hash_table [hash_key]

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

Ví dụ

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

Đầu vào

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

Đầu ra

True
False
True
False