Bảng băm là một cấu trúc dữ liệu lưu trữ dữ liệu theo cách liên kết. Trong bảng băm, dữ liệu được lưu trữ ở định dạng mảng, trong đó mỗi giá trị dữ liệu có giá trị chỉ mục duy nhất của riêng nó. Việc truy cập vào dữ liệu trở nên rất nhanh nếu chúng ta biết chỉ mục của dữ liệu mong muốn.
Do đó, nó trở thành một cấu trúc dữ liệu trong đó các thao tác chèn và tìm kiếm rất nhanh bất kể kích thước của dữ liệu. Bảng băm sử dụng một mảng làm phương tiện lưu trữ và sử dụng kỹ thuật băm để tạo chỉ mục nơi một phần tử sẽ được chèn hoặc sẽ được định vị từ đó.
Băm
Hashing là một kỹ thuật để chuyển đổi một loạt các giá trị khóa thành một loạt các chỉ mục của một mảng. Chúng ta sẽ sử dụng toán tử modulo để nhận một loạt các giá trị chính. Hãy xem xét một ví dụ về bảng băm có kích thước 20 và các mục sau đây sẽ được lưu trữ. Mục ở định dạng (khóa, giá trị).
Ở đây chúng ta có một hàm băm nhận các khóa và tạo các chỉ số cho một bảng. Các chỉ số này cho chúng tôi biết giá trị được lưu trữ ở đâu. Giờ đây, bất cứ khi nào chúng ta muốn tìm kiếm giá trị được liên kết với một khóa, chúng ta chỉ cần chạy lại hàm băm trên khóa đó và nhận giá trị đó trong thời gian gần như không đổi.
Mặc dù vậy, hàm băm khá khó thiết kế. Hãy lấy một ví dụ -
Giả sử chúng ta có hàm băm sau -
Ví dụ
function modBy11(key) {
return key % 11;
} Và chúng tôi bắt đầu chạy điều này trên các cặp khóa-giá trị mà chúng tôi muốn lưu trữ, chẳng hạn như -
- (15, 20) - Mã băm:4
- (25, 39) - Mã băm:3
- (8, 55) - Mã băm:8
- (26, 84) - Mã băm:4
Ở đây chúng ta thấy rằng chúng ta có một va chạm, tức là, nếu chúng ta lưu trữ 15 trước và sau đó gặp khóa 26 với hàm băm này, nó sẽ cố gắng sửa mục nhập này trong cùng một lỗ. Đây được gọi là va chạm. Và để xử lý những tình huống như vậy, chúng ta cần xác định 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 được xác định rõ ràng. Ví dụ -
- Đầu dò tuyến tính:Trong thuật toán này, chúng ta có thể tìm kiếm vị trí trống tiếp theo trong mảng bằng cách nhìn vào ô tiếp theo cho đến khi chúng ta tìm thấy một ô trống. Trong ví dụ của chúng tôi, vì lỗ ở số 4 được lấy đi, chúng tôi có thể lấp nó ở số 5.
- Chuỗi riêng:Trong cách triển khai này:Chúng tôi liên kết mỗi vị trí trong bảng băm với một danh sách. Bất cứ khi nào chúng tôi gặp va chạm, chúng tôi sẽ 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 nhiều nếu chuỗi tiếp tục dài hơn.
Bây giờ chúng ta đã hiểu cách hoạt động của bảng băm và cách chúng ta có thể sử dụng giải pháp xung đột, hãy triển khai lớp HashTable.
Các phương pháp chúng tôi sẽ triển khai
Chúng tôi sẽ triển khai các phương pháp này trong quá trình triển khai của mình -
- put (key, value):Thêm một cặp khóa-giá trị mới vào bảng băm
- get (key):Nhận giá trị được liên kết với một khóa
- remove (key):Xóa cặp khóa-giá trị khỏi bảng
- forEach ():Cho phép lặp lại trên tất cả các cặp khóa-giá trị
- static join ():Phương thức tĩnh để nối 2 bảng băm thành một bảng mới