Đụng độ mã băm¶

Chương trước đã đề cập rằng, trong hầu hết các trường hợp, không gian đầu vào của hàm băm lớn hơn nhiều so với không gian đầu ra, vì vậy về mặt lý thuyết, đụng độ mã băm là không thể tránh khỏi. Ví dụ: nếu không gian đầu vào là tất cả các số nguyên và không gian đầu ra là kích thước dung lượng mảng, thì nhiều số nguyên chắc chắn sẽ được ánh xạ vào cùng một chỉ số ngăn.

Đụng độ mã băm có thể dẫn đến kết quả truy vấn sai, ảnh hưởng nghiêm trọng đến khả năng sử dụng của bảng băm. Để giải quyết vấn đề này, mỗi khi xảy ra đụng độ mã băm, chúng ta có thể thực hiện mở rộng bảng băm cho đến khi đụng độ biến mất. Cách tiếp cận này đơn giản, trực quan và hiệu quả, nhưng lại rất kém hiệu quả vì việc mở rộng bảng băm liên quan đến một lượng lớn dữ liệu cần di chuyển và việc tính toán lại giá trị băm. Để nâng cao hiệu suất, chúng ta có thể áp dụng các chiến lược sau:

Cải tiến cấu trúc dữ liệu của bảng băm để bảng băm có thể hoạt động bình thường khi xảy ra đụng độ mã băm.
Chỉ mở rộng khi cần thiết, nghĩa là chỉ khi đụng độ mã băm trở nên nghiêm trọng.

Các phương pháp chính để cải tiến cấu trúc của bảng băm là chuỗi kề và địa chỉ mở.

Chuỗi kề¶

Trong bảng băm ban đầu, mỗi ngăn chỉ có thể lưu trữ một cặp khóa-giá trị. Chuỗi kề (separate chaining) thay thế phần tử duy nhất trong mỗi ngăn bằng một danh sách liên kết, coi mỗi cặp khóa-giá trị là một nút và lưu trữ tất cả các cặp khóa-giá trị bị đụng độ trong cùng một danh sách liên kết. Hình bên dưới hiển thị một ví dụ về bảng băm triển khai bằng chuỗi kề.

Trong bảng băm được triển khai bằng chuỗi kề, các thao tác cơ bản hoạt động như sau:

Truy vấn phần tử: Nhập key, tính toán chỉ số ngăn bằng hàm băm, truy cập nút đầu của danh sách liên kết tương ứng và duyệt qua danh sách liên kết trong khi so sánh các khóa cho đến khi tìm thấy cặp khóa-giá trị mục tiêu.
Thêm phần tử: Đầu tiên sử dụng hàm băm để định vị danh sách liên kết tương ứng, sau đó chèn nút (cặp khóa-giá trị) vào danh sách liên kết.
Xóa phần tử: Sử dụng hàm băm để định vị danh sách liên kết tương ứng, sau đó duyệt qua danh sách liên kết đó để tìm và xóa nút mục tiêu.

Chuỗi kề có các hạn chế sau:

Tăng không gian sử dụng: Danh sách liên kết chứa các con trỏ nút, tiêu tốn nhiều bộ nhớ hơn so với mảng.
Giảm hiệu suất truy vấn: Do yêu cầu duyệt tuyến tính danh sách liên kết để tìm phần tử tương ứng.

Đoạn mã dưới đây cung cấp một triển khai đơn giản của bảng băm chuỗi kề, có hai lưu ý:

Danh sách (mảng động) được sử dụng thay cho danh sách liên kết để đơn giản hóa mã nguồn. Trong cấu hình này, bảng băm (mảng) chứa nhiều ngăn, mỗi ngăn là một danh sách.
Triển khai này bao gồm một phương thức mở rộng bảng băm. Khi hệ số tải vượt quá \(\frac{2}{3}\), chúng ta mở rộng bảng băm lên gấp \(2\) lần kích thước ban đầu.

[file]{hash_map_chaining}-[class]{hash_map_chaining}-[func]{}

Đáng chú ý là khi danh sách liên kết trở nên rất dài, thời gian truy vấn \(O(n)\) sẽ rất tệ. Trong trường hợp này, danh sách liên kết có thể được chuyển đổi thành cây AVL hoặc cây đỏ-đen, giúp giảm độ phức tạp thời gian tìm kiếm xuống còn \(O(\log n)\).

Địa chỉ mở¶

Địa chỉ mở (open addressing) không sử dụng thêm cấu trúc dữ liệu bổ sung bên ngoài. Thay vào đó, nó xử lý đụng độ mã băm thông qua việc dò liên tục. Các chiến lược dò phổ biến bao gồm dò tuyến tính, dò bậc hai và băm nhiều lần.

Hãy lấy dò tuyến tính làm ví dụ để giới thiệu cơ chế của bảng băm địa chỉ mở.

Dò tuyến tính¶

Dò tuyến tính sử dụng một bước dò cố định để dò tuần tự, vì vậy các thao tác của nó hơi khác so với bảng băm thông thường.

Chèn phần tử: Tính toán chỉ số ngăn bằng hàm băm. Nếu ngăn đó đã bị chiếm dụng, tiếp tục dò về phía trước từ vị trí đụng độ với một bước dò cố định (thường là \(1\)) cho đến khi tìm thấy một ngăn trống, sau đó chèn phần tử vào đó.
Tìm kiếm phần tử: Nếu xảy ra đụng độ, tiếp tục dò về phía trước với cùng bước dò đó cho đến khi tìm thấy phần tử tương ứng và trả về value của nó; nếu gặp một ngăn trống, điều đó có nghĩa là phần tử mục tiêu không có trong bảng băm, trả về None.

Hình bên dưới cho thấy sự phân bổ của các cặp khóa-giá trị trong bảng băm địa chỉ mở sử dụng dò tuyến tính. Dưới hàm băm này, các khóa có hai chữ số cuối giống nhau sẽ được ánh xạ vào cùng một ngăn. Dò tuyến tính sau đó sẽ đặt chúng vào ngăn đó và các ngăn tiếp theo.

Tuy nhiên, dò tuyến tính rất dễ dẫn đến hiện tượng kết cụm. Cụ thể, vùng chiếm dụng liên tục trong mảng càng dài thì đụng độ mới càng dễ xảy ra trong vùng đó. Điều này lại làm cho cụm đó phát triển lớn hơn nữa, tạo ra một vòng lặp luẩn quẩn dần dần làm giảm hiệu suất của các thao tác chèn, xóa, tìm kiếm và cập nhật.

Một điều quan trọng cần lưu ý là chúng ta không thể trực tiếp xóa các phần tử khỏi bảng băm địa chỉ mở. Việc xóa một phần tử sẽ tạo ra một ngăn trống None trong mảng. Khi tìm kiếm, khi việc dò tuyến tính gặp ngăn trống đó, nó sẽ dừng lại, nghĩa là bất kỳ phần tử nào được lưu trữ xa hơn trong chuỗi dò đều không thể truy cập được nữa. Do đó, chương trình có thể kết luận sai rằng các phần tử đó không tồn tại, như được minh họa trong hình dưới đây.

Để giải quyết vấn đề này, chúng ta có thể áp dụng chiến lược xóa lười (lazy deletion): thay vì xóa trực tiếp một phần tử khỏi bảng băm, sử dụng một hằng số TOMBSTONE để đánh dấu ngăn đó. Dưới cơ chế này, cả None và TOMBSTONE đều biểu thị các ngăn có thể nhận các cặp khóa-giá trị. Sự khác biệt là khi dò tuyến tính gặp TOMBSTONE, nó phải tiếp tục dò, vì các cặp khóa-giá trị vẫn có thể tồn tại xa hơn trong chuỗi.

Tuy nhiên, xóa lười có thể đẩy nhanh quá trình suy giảm hiệu suất của bảng băm. Mỗi thao tác xóa sẽ để lại một dấu mốc, và khi số lượng mục TOMBSTONE tăng lên, thời gian tìm kiếm cũng tăng theo, vì dò tuyến tính có thể cần phải nhảy qua nhiều "bia mộ" trước khi tìm thấy phần tử mục tiêu.

Để giải quyết vấn đề này, chúng ta có thể ghi lại chỉ số của TOMBSTONE đầu tiên gặp phải trong quá trình dò tuyến tính và tráo đổi phần tử mục tiêu tìm thấy vào vị trí đó. Lợi ích là mỗi lần truy vấn hoặc chèn có thể di chuyển các phần tử lại gần vị trí lý tưởng của chúng hơn, tức là gần nơi bắt đầu dò hơn, giúp cải thiện hiệu suất tìm kiếm.

Đoạn mã dưới đây triển khai bảng băm địa chỉ mở (dò tuyến tính) với cơ chế xóa lười. Để tận dụng tốt hơn không gian bảng băm, chúng ta coi bảng băm như một "mảng vòng". Khi đi quá cuối mảng, chúng ta quay lại đầu mảng và tiếp tục duyệt.

[file]{hash_map_open_addressing}-[class]{hash_map_open_addressing}-[func]{}

Dò bậc hai¶

Dò bậc hai tương tự như dò tuyến tính và là một trong những chiến lược phổ biến của địa chỉ mở. Khi xảy ra đụng độ, dò bậc hai không đơn thuần nhảy qua một số bước cố định mà nhảy qua số bước bằng "bình phương của số lần dò", tức là \(1, 4, 9, \dots\) bước.

Dò bậc hai có các ưu điểm sau:

Dò bậc hai cố gắng giảm bớt hiệu ứng kết cụm của dò tuyến tính bằng cách bỏ qua các khoảng cách bằng bình phương số lần dò.
Dò bậc hai bỏ qua khoảng cách lớn hơn để tìm các vị trí trống, giúp phân bổ dữ liệu đồng đều hơn.

Tuy nhiên, dò bậc hai không phải là hoàn hảo:

Hiện tượng kết cụm vẫn tồn tại, tức là một số vị trí vẫn có khả năng bị chiếm dụng cao hơn các vị trí khác.
Do sự tăng trưởng của bình phương, dò bậc hai có thể không dò được toàn bộ bảng băm, nghĩa là ngay cả khi có các ngăn trống trong bảng băm, dò bậc hai cũng có thể không truy cập được chúng.

Băm nhiều lần¶

Đúng như tên gọi, băm nhiều lần (multiple hashing) sử dụng nhiều hàm băm \(f_1(x)\), \(f_2(x)\), \(f_3(x)\), \(\dots\) để dò.

Chèn phần tử: Nếu hàm băm \(f_1(x)\) gặp xung đột, hãy thử \(f_2(x)\), và cứ tiếp tục như vậy cho đến khi tìm thấy vị trí trống và chèn phần tử vào.
Tìm kiếm phần tử: Tìm kiếm theo cùng thứ tự của các hàm băm cho đến khi tìm thấy phần tử mục tiêu và trả về nó; nếu gặp vị trí trống hoặc tất cả các hàm băm đã được thử, điều đó cho thấy phần tử không có trong bảng băm, trả về None.

So với dò tuyến tính, băm nhiều lần ít bị kết cụm hơn, nhưng việc sử dụng nhiều hàm băm sẽ phát sinh thêm chi phí tính toán.

Tip

Xin lưu ý rằng các bảng băm dựa trên địa chỉ mở, bao gồm dò tuyến tính, dò bậc hai và băm nhiều lần, đều gặp phải vấn đề là các phần tử không thể được xóa trực tiếp.

Lựa chọn của các Ngôn ngữ Lập trình¶

Các ngôn ngữ lập trình khác nhau áp dụng các chiến lược triển khai bảng băm khác nhau. Dưới đây là một vài ví dụ:

Python sử dụng địa chỉ mở. Từ điển dict sử dụng các số giả ngẫu nhiên để dò.
Java sử dụng chuỗi kề. Từ JDK 1.8, khi độ dài mảng trong HashMap đạt đến 64 và độ dài của một danh sách liên kết đạt đến 8, danh sách liên kết sẽ được chuyển đổi thành cây đỏ-đen để nâng cao hiệu suất tìm kiếm.
Go sử dụng chuỗi kề. Go quy định mỗi ngăn có thể lưu trữ tối đa 8 cặp khóa-giá trị, và nếu vượt quá dung lượng, một ngăn tràn (overflow bucket) sẽ được liên kết; khi có quá nhiều ngăn tràn, một thao tác mở rộng có cùng dung lượng đặc biệt sẽ được thực hiện để đảm bảo hiệu suất.