Thiết Kế HashSet (Design HashSet) trong Python

Giả sử 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ỳ thư viện bảng băm tích hợp sẵn nào. Sẽ có các hàm như:

• add(x) - Chèn giá trị x vào HashSet.
• contains(x) - Kiểm tra xem giá trị x có hiện diện trong HashSet hay không.
• remove(x) - Xóa x khỏi HashSet. Nếu giá trị không tồn tại, không làm gì.

Ví dụ, để kiểm tra: Khởi tạo hash set, sau đó gọi add(1), add(3), contains(1), contains(2), add(2), contains(2), remove(2), contains(2)., thì đầu ra sẽ là true (1 có mặt), false (2 không có), true (2 có mặt), false (2 không có) lần lượt.

Để giải quyết, ta thực hiện các bước sau:

• Định nghĩa một cấu trúc dữ liệu gọi là Bucket, khởi tạo như sau
  • bucket := một danh sách mới
• Định nghĩa hàm update(). Nhận key
  • found := False
  • Với mỗi chỉ số i và key k trong bucket, thực hiện:
    • Nếu key bằng k, thì:
      • bucket[i] := key
      • found := True
      • Thoát khỏi vòng lặp
    • Nếu found false, thì:
      • Thêm key vào cuối bucket
  • Định nghĩa hàm get(). Nhận key
    • Với mỗi k trong bucket, thực hiện:
      • Nếu k bằng key, thì:
        • Trả về True
      • Trả về False
  • Định nghĩa hàm remove(). Nhận key
    • Với mỗi chỉ số i và key k trong bucket, thực hiện:
      • Nếu key bằng k, thì:
        • Xóa bucket[i]
  • Tạo HashSet tùy chỉnh. Có các phương thức:
    • Khởi tạo như sau:
      • key_space := 2096
      • hash_table := danh sách đối tượng bucket loại size key_space
    • Định nghĩa hàm add(). Nhận key
      • hash_key := key mod key_space
      • Gọi update(key) của hash_table[hash_key]
    • Định nghĩa hàm remove(). Nhận key
      • hash_key := key mod key_space
      • Xóa key khỏi hash_table[hash_key]
    • Định nghĩa hàm contains(). Nhận key
      • hash_key := key mod key_space
      • Trả về get(key) của hash_table[hash_key]

  Hãy xem 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