Bảng băm là gì?

Bảng băm là một cấu trúc dữ liệu lưu trữ các cặp khóa-giá trị, giống như một từ điển tra cứu mục bằng khóa. Điều kỳ diệu nằm ở tốc độ: một bảng băm được xây dựng tốt có thể tìm, thêm hoặc xóa một mục trong thời gian trung bình O(1), bất kể bảng chứa bao nhiêu mục.

Bí quyết nằm ở hàm băm (hash function). Mỗi khóa được chuyển thành chỉ số của một ngăn, nhờ đó ta biết chính xác cần tìm ở đâu mà không phải duyệt toàn bộ bảng. Khi hai khóa khác nhau rơi vào cùng một ngăn (xung đột (collision)), ta lưu chúng cùng nhau trong một danh sách tại ngăn đó. Chiến lược này gọi là nối chuỗi (chaining).

Năm thao tác chính trên bảng băm là:

1. Thêm: Lưu một cặp khóa-giá trị hoặc cập nhật giá trị nếu khóa đã tồn tại.
2. Lấy: Tra cứu giá trị tương ứng với một khóa cho trước.
3. Kiểm tra khóa: Kiểm tra xem khóa có được lưu trong bảng hay không.
4. Xóa: Xóa một cặp khóa-giá trị.
5. Kích thước: Trả về số lượng cặp hiện đang được lưu.

Hãy tạo một lớp HashMap!