Hash Table là một cấu trúc dữ liệu lưu trữ dữ liệu theo cách liên kết. Trong Hash Table, dữ liệu được lưu trong dạng mảng, nơi mỗi giá trị dữ liệu có chỉ số (index) duy nhất riêng. Truy cập dữ liệu trở nên rất nhanh nếu biết chỉ số của dữ liệu mong muốn.
Do đó, nó trở thành một cấu trúc dữ liệu mà các thao tác chèn và tìm kiếm rất nhanh bất kể kích thước dữ liệu. Hash Table sử dụng mảng làm phương tiện lưu trữ và dùng kỹ thuật hash để tạo ra chỉ số nơi phần tử sẽ được chèn hoặc định vị.
Hashing (Băm)
Hashing là kỹ thuật chuyển đổi một dải giá trị khóa thành một dải chỉ số của mảng. Chúng ta sẽ dùng toán tử modulo để lấy dải giá trị khóa. Xét ví dụ một Hash Table kích thước 20, và các mục sau cần lưu trữ. Mục ở dạng (khóa, giá trị).
Ở đây chúng ta có một hàm hash nhận khóa và tạo ra chỉ số cho bảng. Các chỉ số này cho biết giá trị được lưu ở đâu. Bây giờ khi muốn tìm giá trị liên quan đến một khóa, chỉ cần chạy lại hàm hash trên khóa đó và lấy giá trị trong thời gian gần như hằng số.
Hàm hash khá khó thiết kế. Hãy lấy ví dụ:
Giả sử chúng ta có hàm hash sau:
Ví dụ
function modBy11(key) {
return key % 11;
}
Và chạy hàm này trên các cặp khóa-giá trị muốn lưu, ví dụ:
- (15, 20) - Mã hash: 4
- (25, 39) - Mã hash: 3
- (8, 55) - Mã hash: 8
- (26, 84) - Mã hash: 4
Ở đây ta thấy có va chạm (collision), tức là nếu lưu 15 trước rồi gặp khóa 26 với hàm hash này, nó sẽ cố gắng đặt entry này vào cùng một ô. Đây gọi là va chạm. Để xử lý tình huống này, cần định nghĩa cơ chế xử lý va chạm. Có một số thuật toán giải quyết va chạm đơn giản và rõ ràng. Ví dụ:
- Linear Probing (Dò tuyến tính): Trong thuật toán này, ta tìm vị trí trống tiếp theo trong mảng bằng cách xem ô tiếp theo cho đến khi tìm thấy ô trống. Trong ví dụ, vì ô 4 đã bị chiếm, ta có thể điền vào ô 5.
- Separate Chaining (Chaining riêng biệt): Trong triển khai này: Mỗi vị trí trong Hash Table liên kết với một danh sách. Khi có va chạm, ta thêm cặp khóa-giá trị vào cuối danh sách này. Điều này có thể dẫn đến thời gian tìm kiếm lâu hơn nếu các chain ngày càng dài.
Bây giờ đã hiểu cách Hash Table hoạt động và cách dùng giải quyết va chạm, hãy triển khai class HashTable.
Các phương thức sẽ triển khai
Chúng ta sẽ triển khai các phương thức sau:
- put(key, value): Thêm cặp khóa-giá trị mới vào Hash Table
- get(key): Lấy giá trị liên quan đến một khóa
- remove(key): Xóa cặp khóa-giá trị khỏi bảng
- forEach(): Cho phép lặp qua tất cả các cặp khóa-giá trị
- static join(): Phương thức tĩnh để gộp 2 Hash Table thành một cái mới