Giả sử ta muốn thiết kế một HashMap 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 khác nhau như sau:
- put(key, value) - Chèn một giá trị liên kết với key vào HashMap. Nếu giá trị đã tồn tại, cập nhật giá trị.
- get(key) - Trả về giá trị mà key chỉ định ánh xạ tới, trả về -1 nếu bản đồ không chứa ánh xạ cho key.
- remove(key) - Xóa ánh xạ cho key nếu bản đồ chứa ánh xạ cho key.
Ví dụ, nếu đầu vào là sau khi khởi tạo, gọi put và get như sau:
- put(1, 1);
- put(2, 2);
- get(1);
- get(3);
- put(2, 1);
- get(2);
- remove(2);
- get(2);
thì đầu ra sẽ là 1, -1(không có), 1, -1(không có) lần lượt.
Để giải quyết, ta thực hiện các bước sau:
- Tạo cấu trúc dữ liệu mới gọi là node, khởi tạo với các trường (key, val, next), next ban đầu là null
- Định nghĩa một Danh sách liên kết (Linked List), có các phương thức:
- Định nghĩa một hàm khởi tạo, hoạt động như sau:
- prehead := một node Node mới với key = null và val = null
- Định nghĩa hàm search(). Nhận key
- p := prehead.next
- Khi p không phải null, thực hiện:
- Nếu p.key bằng key, thì:
- Trả về p
- p := p.next
- Nếu p.key bằng key, thì:
- Trả về None
- Định nghĩa hàm add(). Nhận key, val
- p := search(key)
- Nếu p không phải null, thì:
- p.val := val
- Ngược lại:
- node := Node mới với (key, val)
- prehead.next := node, node.next := prehead.next
- Định nghĩa hàm get(). Nhận key
- p := search(key)
- Nếu p không phải null, thì:
- Trả về p.val
- Ngược lại:
- Trả về null
- Định nghĩa hàm remove. Nhận key
- prev := prehead
- cur := prev.next
- Khi cur không phải null, thực hiện:
- Nếu cur.key bằng key, thì:
- Thoát khỏi vòng lặp
- prev := curr, cur := cur.next
- Nếu cur không phải null, thì:
- prev.next := cur.next
- Nếu cur.key bằng key, thì:
- Định nghĩa hàm serialize().
- p := prehead.next
- ret := một danh sách mới
- Khi p không phải null, thực hiện:
- Chèn [p.key, p.val] vào cuối ret
- p := p.next
- Trả về ret
- Từ HashMap tùy chỉnh, định nghĩa các phương thức:
- Định nghĩa một hàm khởi tạo.
- size := 1033
- arr := mảng LinkedList() có độ dài bằng size
- Định nghĩa hàm _hash(). Nhận key
- Trả về key mod size
- Định nghĩa hàm put(). Nhận key, value
- h := _hash(key)
- Gọi add(key, value) của arr[h]
- Định nghĩa hàm get(). Nhận key
- h := _hash(key)
- ret := get(key) của arr[h]
- Nếu ret không phải null, thì:
- Trả về ret
- Ngược lại:
- Trả về -1
- Định nghĩa hàm remove(). Nhận key
- h := _hash(key)
- Xóa key khỏi arr[h]
Hãy xem 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
- Định nghĩa một hàm khởi tạo, hoạt động như sau: