Bảng băm tự cài đặt giải quyết xung đột bằng Linear Probing

Mục tiêu kiến thức

• Triển khai bảng băm định địa chỉ mở (Open Addressing) với thăm dò tuyến tính (Linear Probing).
• Hiểu và ứng dụng dấu hiệu bia mộ (Tombstone) khi xóa phần tử để bảo toàn chuỗi thăm dò.
• Tự động tái băm (Rehashing / Dynamic Resizing) gấp đôi kích thước khi hệ số tải (Load Factor) ≥ 0.70.

Mô tả bài toán

Viết lớp LinearProbingHashMap:

• __init__(self, initial_capacity: int = 8): Khởi tạo bảng băm với dung lượng ban đầu.
• put(self, key: str, value: any) -> None: Thêm hoặc cập nhật giá trị. Nếu load factor (số ô đang chứa khóa hợp lệ + số ô tombstone) / dung lượng ≥ 0.70, tự động tăng gấp đôi dung lượng và băm lại (rehash) toàn bộ các phần tử hợp lệ.
• get(self, key: str, default: any = None) -> any: Lấy giá trị theo khóa. Nếu không tìm thấy, trả về default.
• delete(self, key: str) -> bool: Xóa khóa. Nếu tìm thấy, đánh dấu ô là _TOMBSTONE và trả về True. Nếu không tìm thấy, trả về False.
• __len__(self) -> int: Trả về số lượng cặp khóa-giá trị hợp lệ đang lưu trong bảng.

Hàm băm khuyến nghị: hash(key) % capacity.

Ràng buộc

• Thời gian chạy tối đa: 1000ms.
• Giới hạn bộ nhớ: 256MB.
• Dữ liệu đầu vào tuân thủ đúng kiểu dữ liệu và miền giá trị được mô tả.