Hàm băm và va chạm
Hàm băm và va chạm
Bảng băm nhanh vì nó nhảy thẳng tới ô cần tìm. Nó chỉ nhanh khi các khoá rơi tương đối đều. Bài này bắt bạn đo xem chúng có rơi đều thật không, trên đúng danh sách khoá bạn gõ vào.
Ở bài đếm chi phí thay vì đoán bạn đã thấy bảng băm xuất hiện như một cách tìm cặp nhanh hơn hai vòng lặp lồng nhau, và cũng đã thấy nó không miễn phí. Ở Set và Map trong Java bạn dùng nó như một hộp đen: cứ gọi put rồi get là xong. Bài này mở hộp đen ra đúng một tầng.
Ý tưởng của bảng băm chỉ có một câu: biến khoá thành một số, lấy số đó chia lấy dư cho số ô bảng, rồi đặt khoá vào ô ứng với số dư. Tìm lại thì tính đúng phép đó một lần nữa và nhảy thẳng tới ô đó. Nếu mỗi ô chỉ giữ một khoá thì tìm kiếm tốn đúng một phép so sánh, bất kể bảng có một trăm hay một triệu khoá. Đó là lời hứa.
Chỗ lời hứa gãy gọi là va chạm: hai khoá khác nhau ra cùng một ô. Lúc đó ô phải giữ cả hai và việc tìm kiếm biến thành duyệt danh sách. Sim dưới đây không giải thích va chạm bằng lời, nó băm thật từng khoá rồi đếm.
1 · Khoá, hàm băm, cỡ bảng ✎ sửa được
h = (mã[0] + mã[1] + ... + mã[L-1]) mod mXem từng khoá: mã băm và ô nó rơi vào
| khoá | số ký tự | mã băm | mã mod 16 | số khoá trong ô đó |
|---|---|---|---|---|
an | 2 | 207 | 15 | 2 |
bình | 4 | 548 | 4 | 2 |
châu | 4 | 546 | 2 | 3 |
dũng | 4 | 674 | 2 | 3 |
giang | 5 | 518 | 6 | 5 |
hà | 2 | 328 | 8 | 2 |
hải | 3 | 8.052 | 4 | 2 |
hạnh | 4 | 8.159 | 15 | 2 |
hiếu | 4 | 8.197 | 5 | 2 |
hoa | 3 | 312 | 8 | 2 |
hùng | 4 | 566 | 6 | 5 |
khánh | 5 | 650 | 10 | 1 |
lan | 3 | 315 | 11 | 2 |
linh | 4 | 427 | 11 | 2 |
long | 4 | 432 | 0 | 2 |
mai | 3 | 311 | 7 | 1 |
minh | 4 | 428 | 12 | 5 |
nam | 3 | 316 | 12 | 5 |
ngọc | 4 | 8.197 | 5 | 2 |
nhung | 5 | 544 | 0 | 2 |
phong | 5 | 540 | 12 | 5 |
quân | 4 | 566 | 6 | 5 |
sơn | 3 | 642 | 2 | 3 |
thảo | 4 | 8.174 | 14 | 1 |
trang | 5 | 540 | 12 | 5 |
tuấn | 4 | 8.188 | 12 | 5 |
vân | 3 | 454 | 6 | 5 |
yến | 3 | 8.102 | 6 | 5 |
2 · Số nguyên tố hay luỹ thừa của 2 đo trực tiếp
Ba cặp cỡ bảng gần bằng nhau, chạy trên đúng bộ khoá và đúng hàm băm bạn đang chọn. Bấm đổi preset khoá ở đầu sim rồi đọc lại bảng này: kết luận đổi theo dữ liệu chứ không phải là một câu ghi sẵn.
| cặp cỡ bảng | va chạm | ô trống | ô đông nhất | độ lệch | so sánh TB |
|---|---|---|---|---|---|
| m = 17 · nguyên tố | 13 | 2 | 4 | 0,91 | 1,75 |
| m = 16 · luỹ thừa của 2 | 16 | 4 | 5 | 1,41 | 2,04 |
| chênh lệch | số nguyên tố 17 thắng: ít hơn 3 va chạm | ||||
| m = 31 · nguyên tố | 9 | 12 | 4 | 1,06 | 1,46 |
| m = 32 · luỹ thừa của 2 | 9 | 13 | 4 | 1,16 | 1,50 |
| chênh lệch | hoà: cả hai cùng 9 va chạm, dù bảng 32 ô có nhiều hơn 1 ô | ||||
| m = 61 · nguyên tố | 6 | 39 | 3 | 1,13 | 1,29 |
| m = 64 · luỹ thừa của 2 | 6 | 42 | 2 | 1,01 | 1,21 |
| chênh lệch | hoà: cả hai cùng 6 va chạm, dù bảng 64 ô có nhiều hơn 3 ô | ||||
3 · Nghịch lý ngày sinh ✎ sửa được
Câu hỏi: bảng có m ô, ném vào k khoá, mỗi khoá rơi vào một ô bất kỳ với cùng xác suất. Cần bao nhiêu khoá thì khả năng có ít nhất một va chạm vượt quá một nửa? Trực giác nói phải gần m. Số thật thì nhỏ hơn nhiều.
- Không có hàm băm mật mã nào ở đây. Bốn hàm trên đều dễ bị dựng va chạm có chủ ý: chỉ cần cộng hoặc bớt vài ký tự là ra một khoá khác cùng ô. Băm để tra cứu lo chuyện chia đều và nhanh; băm để bảo mật phải chống được người cố tình tấn công, và đó là bài toán khác hẳn với yêu cầu khác hẳn. Đừng bao giờ lấy hàm ở đây đi băm mật khẩu.
- Sim đếm va chạm và phép so sánh. Nó không đo thời gian chạy: một hàm băm ít va chạm hơn vẫn có thể chậm hơn vì tính lâu hơn, và bộ nhớ đệm của máy còn có tiếng nói riêng.
- Cách xử lý va chạm ở đây là nối chuỗi: các khoá cùng ô nằm trong một danh sách và tìm tuyến tính. Cách dò tuyến tính hay băm kép cho con số khác, và đó là bài sau.
- Chữ tiếng Việt gõ được theo hai cách (dựng sẵn hoặc tổ hợp dấu rời). Cùng một chữ trên màn hình nhưng khác chuỗi thì khác mã băm và khác ô. Sim băm đúng chuỗi bạn gõ và không chuẩn hoá gì cả, vì đó chính là cái bẫy hay gặp khi làm dữ liệu tiếng Việt thật.
- Cột độ lệch là thống kê mô tả, không phải một phép kiểm định. Nó so số khoá mỗi ô với mức chia đều rồi chia cho
m - 1, vì một hàm băm ngẫu nhiên công bằng có kỳ vọng đúng bằngm - 1. Bộ khoá ở đây là cố định chứ không phải mẫu ngẫu nhiên, nên đừng đọc nó như một giá trị p. - Khoá bị cắt còn 24 ký tự và danh sách bị cắt còn 40 khoá là giới hạn của sim để lưới còn nhìn được. Cả hai lần cắt đều hiện thành chữ ngay trên đầu sim chứ không làm lặng lẽ, vì cắt khoá là đổi mã băm.
Bốn hàm băm, công thức bày ra hết
Không hàm nào ở đây là bí mật. Bạn tính lại bằng tay được cả bốn.
Cộng mã ký tự. Lấy mã của từng ký tự cộng dồn, rồi chia lấy dư cho m. Với abc thì 97 + 98 + 99 = 294. Hàm này dễ viết nhất và có một lỗ rất lớn: nó không nhìn thấy thứ tự. Khoá cba cũng ra 294, nên abc và cba nằm cùng ô ở mọi cỡ bảng, không cỡ nào cứu được. Bấm sang preset hoán vị chữ cái để thấy: 12 khoá gồm 6 hoán vị của abc và 6 hoán vị của xyz, hàm cộng chỉ sinh ra đúng 2 mã phân biệt, nên 10 va chạm là sàn không thể phá.
Nhân dồn với 31. Bắt đầu từ 0, với mỗi ký tự thì h = h × 31 + mã, giữ trong 32 bit, cuối cùng chia lấy dư cho m. Với abc thì 97 × 31 + 98 = 3105, rồi 3105 × 31 + 99 = 96354. Đây đúng là String.hashCode của Java, và con số 96354 là con số Java in ra. Vì mỗi vị trí được nhân với một luỹ thừa khác của 31 nên hàm này có nhìn thấy thứ tự: cba ra 98274, khác 96354. Trên bộ hoán vị nó tách được cả 12 mã phân biệt.
Nhân dồn không phải là phép màu. Cặp Ea và FB cùng ra 2236, vì 69 × 31 + 97 và 70 × 31 + 66 bằng nhau. Hai khoá đó va nhau ở mọi cỡ bảng, y như cặp hoán vị của hàm cộng. Khác biệt là hàm cộng đụng chuyện đó liên tục, còn nhân dồn thì hiếm.
Chỉ lấy ký tự đầu, và chỉ lấy độ dài. Hai hàm này xấu có chủ ý, và cái xấu của chúng đo được rất gọn. Trên 28 tên tiếng Việt, hàm ký tự đầu chỉ sinh 16 mã phân biệt vì bộ tên chỉ có 16 chữ cái đầu khác nhau; hàm độ dài chỉ sinh 4 mã vì các tên chỉ dài 2 tới 5 ký tự. Số mã phân biệt chính là trần: 12 va chạm với hàm ký tự đầu và 24 va chạm với hàm độ dài là con số không cỡ bảng nào hạ xuống được.
Hãy tự làm thí nghiệm này, nó là chỗ bài học nằm: chọn hàm ký tự đầu, rồi kéo số ô từ 31 lên 32, lên 61, lên 64. Bảng rộng gấp đôi, va chạm vẫn đúng 12. Ô đông nhất vẫn giữ 6 khoá, và sáu khoá đó là hà, hải, hạnh, hiếu, hoa, hùng. Với hàm độ dài thì từ 4 ô trở lên số va chạm đứng nguyên ở 24 và số phép so sánh trung bình đứng nguyên ở 5,18. Nới bảng rộng thêm không mua được gì cả khi hàm băm đã vứt mất thông tin từ đầu.
Trạng thái mở bài nói gì
Sim mở ra với 28 tên tiếng Việt, hàm cộng mã ký tự, bảng 16 ô. Kết quả đếm được:
- 16 va chạm: 28 khoá nhưng chỉ 12 ô được dùng tới, nên
28 - 12 = 16khoá rơi vào ô đã có người. Để so, một hàm băm ngẫu nhiên công bằng trên đúng 28 khoá và 16 ô trung bình cho 14,63 va chạm, nên hàm cộng đang thua may rủi một chút. - 4 ô trống, dù trung bình mỗi ô đáng ra phải giữ
28 / 16 = 1,75khoá. - Ô đông nhất là ô số 6 với 5 khoá, gấp gần ba lần mức chia đều.
- Đầy đủ 16 ô là
2, 0, 3, 0, 2, 2, 5, 1, 2, 0, 1, 2, 5, 0, 1, 2. Cộng lại đúng 28. - Độ lệch so với chia đều: 1,41.
- Tìm thấy một khoá tốn trung bình 2,04 phép so sánh. Con số này không phải ước lượng: tổng số phép so sánh để tìm lần lượt cả 28 khoá là 57, và
57 / 28 = 2,04. - Tìm hụt tốn trung bình 1,75 phép, đúng bằng hệ số tải, vì tìm hụt nghĩa là duyệt hết ô rồi không thấy gì.
Cột độ lệch đáng dừng lại một chút. Nó lấy chênh lệch giữa số khoá thật trong mỗi ô và mức chia đều, bình phương lên, chia cho mức chia đều, cộng hết lại, rồi chia cho m - 1. Cái chia cuối cùng không phải để cho đẹp: một hàm băm ngẫu nhiên công bằng có kỳ vọng của tổng đó đúng bằng m - 1. Vậy nên đọc con số này rất dễ. Số 0 là chia đều tuyệt đối, khoảng 1,00 là mức mà may rủi thuần tuý cũng cho được, còn lớn hơn 1 nhiều là dồn cục. Trạng thái mở bài ra 1,41, tức hơi tệ hơn ngẫu nhiên, chứ chưa phải thảm hoạ.
Có một con số nữa nên để ý: hàm cộng chỉ sinh 25 mã phân biệt cho 28 tên, vì ba cặp trùng mã. hiếu và ngọc cùng ra 8197, hùng và quân cùng ra 566, phong và trang cùng ra 540. Vậy 3 va chạm là sàn: dù bạn kéo bảng lên 64 ô cũng không xuống dưới được.
Số nguyên tố hay luỹ thừa của 2
Câu người ta hay dạy là: số ô bảng nên là số nguyên tố, đừng lấy luỹ thừa của 2. Mục 2 của sim bày sẵn ba cặp cỡ bảng gần bằng nhau để bạn tự kiểm câu đó, trên đúng bộ khoá và đúng hàm băm bạn đang chọn.
Trên 28 tên với hàm cộng, câu đó gần như không đúng. Đây là số đo:
| cặp cỡ bảng | va chạm với số nguyên tố | va chạm với luỹ thừa của 2 |
|---|---|---|
| 17 và 16 | 13 | 16 |
| 31 và 32 | 9 | 9 |
| 61 và 64 | 6 | 6 |
Hai cặp trên ba là hoà tuyệt đối, mà bảng luỹ thừa của 2 còn có nhiều ô hơn: 32 hơn 31 một ô, 64 hơn 61 ba ô. Nếu có một quy luật lớn thì nó đã phải hiện ra ở đây rồi. Nói cho công bằng, tôi đã kỳ vọng thấy chênh lệch lớn và không thấy, nên bài này ghi lại đúng cái đo được.
Bây giờ bấm sang preset khoá đều bước 4 rồi đọc lại đúng bảng đó. Bộ khoá này là 26 khoá bốn chữ giống nhau, từ aaaa tới zzzz, nên tổng mã ký tự đi từ 388 tới 488 đúng bước 4. Cùng hàm cộng, cùng ba cặp cỡ bảng:
| cặp cỡ bảng | va chạm với số nguyên tố | va chạm với luỹ thừa của 2 |
|---|---|---|
| 17 và 16 | 9 | 22 |
| 31 và 32 | 0 | 18 |
| 61 và 64 | 0 | 10 |
Đây không còn là chênh lệch, đây là hai thế giới. Và cơ chế thì tính được bằng tay: mọi mã đều chia hết cho 4, nên số dư của chúng khi chia cho m chỉ nằm trong nhóm bội của ước chung lớn nhất của 4 và m. Số ô thật sự với tới được đúng bằng m chia cho ước chung đó. Bảng 32 ô chỉ dùng được 8 ô, bảng 64 ô chỉ dùng được 16 ô, bảng 16 ô chỉ dùng được 4 ô. Còn 17 và 31 là số nguyên tố, chúng không có ước chung nào với 4 ngoài 1, nên cả bảng đều với tới được: 17 ô dùng cả 17, và 31 ô xếp gọn 26 khoá mỗi ô một khoá.
Kết luận đúng vì thế không phải là "số nguyên tố băm tốt hơn". Nó là: số nguyên tố là bảo hiểm cho thứ cấu trúc mà bạn không biết dữ liệu của mình đang có. Khi khoá không có cấu trúc số học nào thì bảo hiểm đó vô dụng và bạn không mất gì khi bỏ qua. Khi khoá có cấu trúc, và dữ liệu thật thì rất hay có, bảo hiểm đó cứu cả bảng. Bạn không biết trước mình đang ở trường hợp nào, và đó chính là lý do người ta khuyên chọn số nguyên tố.
Cùng chuyện đó, nhưng với hàm nhân dồn
Đổi sang hàm nhân dồn với 31 rồi so bảng 31 ô với bảng 32 ô, vẫn trên 28 tên:
- 31 ô: 18 va chạm, ô đông nhất 7 khoá, độ lệch 4,09, tìm một khoá tốn 2,93 phép so sánh.
- 32 ô: 9 va chạm, ô đông nhất 3 khoá, độ lệch 0,87, tìm một khoá tốn 1,36 phép.
Lần này bảng luỹ thừa của 2 thắng đậm, và số nguyên tố là bên thua. Lý do rất đẹp: bội số của hàm là 31, mà 31 × bất cứ gì đều chia hết cho 31. Nên khi lấy dư cho 31, toàn bộ phần nhân dồn biến mất và chỉ còn lại phép cộng cuối cùng, tức mã của ký tự cuối khoá. Tôi đã kiểm điều này trên cả 94 khoá của bốn preset: đúng không sót khoá nào. Mà 28 cái tên chỉ kết thúc bằng 10 mã khác nhau, nên bảng 31 ô lập tức sụp về mức của một hàm băm xấu.
Chiều ngược lại cũng có. Vẫn hàm nhân dồn, bấm sang khoá đều bước 4 rồi đặt bảng 64 ô: cả 26 khoá vào đúng một ô, 25 va chạm, 63 ô trống. Cũng tính được bằng tay: khoá cccc cho mã × (31³ + 31² + 31 + 1), mà 31³ + 31² + 31 + 1 = 30784 = 64 × 481, nên mọi khoá kiểu đó chia hết cho 64 và rơi vào ô 0.
Cái rút ra không phải là số nào tốt hơn số nào. Là: cỡ bảng và hàm băm không độc lập nhau. Chọn cỡ bảng chia sẻ thừa số với thứ gì đó bên trong hàm băm, hoặc bên trong dữ liệu, thì bảng sụp. Và cũng đừng tưởng bảng to hơn thì luôn đỡ hơn: với hàm nhân dồn trên 28 tên, đi từ 16 ô lên 17 ô làm va chạm tăng từ 14 lên 16.
Nghịch lý ngày sinh, chỗ trực giác sai nặng nhất
Hỏi thẳng: bảng có 365 ô, bạn nghĩ phải ném vào bao nhiêu khoá thì khả năng có ít nhất một va chạm vượt quá một nửa? Hầu hết mọi người trả lời một con số cỡ trăm rưởi, tức khoảng nửa bảng. Đáp án là 23.
Mục 3 của sim tính con số đó cho bất cứ cỡ bảng nào bạn gõ vào. Với 365 ô, 23 khoá cho khả năng va chạm 50,73%, còn 22 khoá thì mới 47,57%. Hai mươi ba khoá chỉ chiếm 6,30% số ô. Bảng còn trống 93,7% mà va chạm đã là chuyện nhiều khả năng hơn không.
Với bảng 16 ô mà sim đang vẽ ở mục 1 thì còn dữ hơn: chỉ cần 5 khoá, tức 31,25% số ô, là khả năng va chạm đã lên 50,01%. Còn bạn đang có 28 khoá.
Vì sao lại nhỏ như vậy? Vì cái tăng nhanh không phải số khoá mà là số cặp khoá. k khoá tạo ra k(k-1)/2 cặp, và mỗi cặp là một cơ hội va chạm. Với k = 23 thì đã có 253 cặp, so với 365 ô. Cân bằng xảy ra khi số cặp xấp xỉ số ô, tức khi k xấp xỉ căn của m, chứ không phải khi k xấp xỉ m. Quy tắc nhẩm thường gặp là 1,1774 × căn(m), trong đó hằng số là căn của 2 ln 2.
Quy tắc nhẩm đó tốt tới đâu thì cũng nên đo chứ đừng tin. Tôi cho sim so nó với đáp án đúng trên 20.000 cỡ bảng: nó thấp hơn đáp án đúng đúng một đơn vị ở 5.389 cỡ bảng, và chưa bao giờ cao hơn, cũng chưa bao giờ lệch quá 1. Nói cách khác nó là một cận dưới khá chặt chứ không phải một xấp xỉ hai chiều. Với m = 365 thì nó cho đúng 23, còn với m = 17 nó cho 5 trong khi đáp án đúng là 6.
Một chi tiết về cách phát biểu, và nó không nhỏ. "Vượt quá một nửa" ở đây là lớn hơn hẳn 0,5, không phải "đạt tới" 0,5. Ranh giới này có chỗ cắn thật: với bảng 2 ô và 2 khoá thì xác suất va chạm bằng đúng 0,5, không xấp xỉ mà bằng chính xác. Nên quy ước chặt trả lời 3 khoá, còn quy ước lỏng sẽ trả lời 2. Cổng kiểm số của bài này khoá cả hai vế của ranh giới đó, và trên toàn dải từ 1 tới 2000 thì m = 2 là cỡ bảng duy nhất mà hai quy ước cho đáp án khác nhau.
Con số ngày sinh tính trên giả thiết hàm băm hoàn hảo: mỗi khoá rơi vào một ô bất kỳ với cùng xác suất và độc lập nhau. Không hàm nào trong bốn hàm ở mục 1 đạt được giả thiết đó, nên phải nói cho chính xác. Con số này không phải cận trên và cũng không phải cận dưới cho hàm băm thật của bạn: nó tả một hàm băm trung bình chứ không tả hàm băm của bạn. Cả hai chiều đều đo được ngay trong sim này.
- Chiều xấu. Hàm nhân dồn trên 28 tên với bảng 31 ô cho 18 va chạm, trong khi một hàm băm ngẫu nhiên công bằng trên cùng số khoá và số ô trung bình chỉ cho 9,38. Thua may rủi gần gấp đôi.
- Chiều tốt. Hàm cộng trên 26 khoá bước đều với bảng 31 ô cho đúng 0 va chạm, trong khi mô hình ngẫu nhiên bảo rằng khả năng có ít nhất một va chạm, làm tròn tới bốn chữ số thập phân, đã là 100,0000%. Một hàm băm hợp với dữ liệu thắng may rủi rất xa.
Nên đừng dùng con số ngày sinh như một lời bảo đảm theo chiều nào cả. Cái nó nói được, và nói rất chắc, chỉ là chuyện này: đừng thiết kế bảng băm như thể va chạm là sự cố hiếm cần phòng. Va chạm là chuyện phải có cách xử lý ngay từ đầu, và phần quan trọng của một bảng băm chính là cách nó xử lý va chạm.
Cũng vì thế mà thẻ đầu tiên trong sim in kèm con số may rủi ngay cạnh số va chạm thật. Ở trạng thái mở bài, 28 khoá trong 16 ô: hàm cộng cho 16 va chạm còn may rủi thuần tuý trung bình cho 14,63, nên hàm này đang thua may rủi một chút. Đó là cách biến câu "hàm băm này tốt hay xấu" từ một ý kiến thành một phép so sánh.
Dấu tiếng Việt có đổi gì không
Câu hỏi này đáng hỏi vì mã ký tự tiếng Việt lớn hơn hẳn chữ Latin trơn. Mã lớn nhất trong bộ tên có dấu là 7885, còn bộ bỏ dấu chỉ tới 121. Tổng mã của hiếu là 8197 trong khi hieu chỉ là 427, tức lớn hơn 19,20 lần.
Đo ra thì kết quả thế này, và nó không giống cái người ta hay đoán:
- Hàm ký tự đầu và hàm độ dài cho kết quả y hệt nhau, ở cả 64 cỡ bảng. Không lệch một va chạm nào. Lý do đơn giản: bỏ dấu không đổi độ dài khoá, và không tên nào trong bộ này bắt đầu bằng chữ có dấu.
- Hàm cộng lệch nhiều nhất 4 va chạm trên tổng 28 khoá, và chỗ lệch nhiều nhất đó là bảng 24 ô. Ở hai cỡ bảng 31 và 32, cả hai bộ khoá đều cho đúng 9 va chạm.
- Hàm nhân dồn lệch nhiều nhất 7 va chạm, ở bảng 37 ô.
Kết luận trung thực: dấu tiếng Việt làm mã băm thay đổi rất nhiều nhưng làm số va chạm thay đổi rất ít, và thay đổi theo cả hai chiều chứ không tốt lên hay xấu đi một cách có hệ thống. Phép chia lấy dư xoá gần hết chuyện mã lớn hay mã nhỏ; cái nó giữ lại là mã có phân biệt được các khoá hay không. Đó mới là thứ đáng lo.
Có một chuyện về tiếng Việt thì đáng lo thật, và sim cố tình không giấu. Cùng một chữ trên màn hình có thể được gõ theo hai cách: chữ dựng sẵn một mã, hoặc chữ gốc cộng dấu rời hai mã. Nhìn giống hệt nhau nhưng là hai chuỗi khác nhau, nên khác mã băm và rơi vào hai ô khác nhau. Sim băm đúng chuỗi bạn gõ và không chuẩn hoá gì cả, vì đây chính là cái bẫy hay gặp nhất khi làm dữ liệu tiếng Việt thật: khoá tra không ra dù nhìn bằng mắt thì giống nhau y đúc.
Bốn mốc biên
Bốn cấu hình này nhìn thì tầm thường, nhưng chúng là chỗ code bảng băm hay vỡ nhất.
Danh sách rỗng. 0 khoá, 16 ô: 0 va chạm, 16 ô trống, số phép so sánh trung bình là 0. Chỗ dễ hỏng là phép chia cho số khoá, và sim trả về 0 thay vì để lộ một số vô nghĩa.
Đúng một khoá. 0 va chạm, 15 ô trống, tìm nó tốn đúng 1 phép so sánh. Cột độ lệch ở đây có đáp án đóng đẹp: một ô giữ 1 khoá và tất cả ô còn lại rỗng cho tổng đúng bằng m - 1, nên độ lệch ra đúng 1,00 với mọi m. Đây cũng là cách thứ hai để kiểm cái chia m - 1 là đúng.
Bảng một ô. Mọi khoá vào chung một chỗ, không cỡ nào tránh được: 27 va chạm cho 28 khoá, 0 ô trống, ô đó giữ cả 28 khoá. Tìm thấy một khoá tốn trung bình (28 + 1) / 2 = 14,5 phép so sánh, tìm hụt tốn cả 28 phép. Bảng băm một ô chính là một danh sách liên kết, và số đo nói đúng như vậy. Với bảng một ô thì cả bốn hàm băm cho kết quả giống hệt nhau, vì mọi số chia 1 đều dư 0.
Số khoá bằng đúng số ô. Đây là chỗ trực giác sai lần nữa. Người ta hay tưởng 28 khoá vào 28 ô thì gần như mỗi ô một khoá. Đo ra: 14 va chạm, tức đúng một nửa số khoá phải xếp hàng, 14 ô bỏ trống, tức đúng nửa bảng, và ô đông nhất giữ 4 khoá. Độ lệch 1,56 và tìm một khoá tốn 1,75 phép. Nhân tiện, m = 28 cũng chẳng có gì đặc biệt: bảng 27 ô cho 11 va chạm, tức tốt hơn hẳn cả 26 ô lẫn 28 ô.
Băm để tra cứu không phải băm để bảo mật
Phải nói thẳng chỗ này trước khi bạn mang bốn hàm trên đi đâu đó. Không hàm nào trong sim này là hàm băm mật mã, và không hàm nào an toàn.
Với hàm cộng, muốn dựng một khoá va chạm với khoá cho trước thì chỉ cần đảo thứ tự ký tự. Với hàm nhân dồn, cặp Ea và FB đã cho thấy dựng va chạm bằng tay cũng được. Người tấn công biết bạn dùng hàm nào và bảng bao nhiêu ô thì họ gửi hàng nghìn khoá cùng một ô, mọi thao tác tra cứu tụt từ một phép so sánh xuống hàng nghìn phép, và dịch vụ của bạn chết đứng dù không ai phá được mật khẩu nào. Đó là một kiểu tấn công có thật.
Hai bài toán khác nhau ở yêu cầu, chứ không phải ở chất lượng:
- Băm để tra cứu cần chia tương đối đều và tính thật nhanh. Va chạm ngẫu nhiên là chấp nhận được, đã có cách xử lý.
- Băm để bảo mật cần điều ngược lại về mặt chi phí: phải khó tìm được hai đầu vào cùng mã kể cả khi có người dồn sức đi tìm, và với mật khẩu thì còn cần chậm có chủ ý. Một hàm băm nhanh là điểm cộng ở cột trái và là điểm trừ nặng ở cột phải.
Bài an toàn và liêm chính thông tin nói về cột phải. Bài này chỉ ở cột trái. Lẫn hai cột là một trong những lỗi tốn kém nhất mà người mới hay mắc.
Còn vài chuyện nữa sim không làm được, nói luôn cho đủ. Nó đếm va chạm và phép so sánh chứ không đo thời gian chạy: một hàm ít va chạm hơn vẫn có thể chậm hơn vì bản thân nó tính lâu hơn. Cách xử lý va chạm ở đây là nối chuỗi, tức các khoá cùng ô nằm chung một danh sách và duyệt tuyến tính; dò tuyến tính hay băm kép cho những con số khác. Và cột độ lệch là thống kê mô tả chứ không phải một phép kiểm định: bộ khoá ở đây cố định chứ không phải mẫu ngẫu nhiên, nên đừng đọc nó như một giá trị p.
Bảng băm nhanh khi khoá rơi đều, và "đều" là thứ đo được chứ không phải hy vọng. Ba con số đáng nhìn là số ô trống, số khoá trong ô đông nhất, và số phép so sánh trung bình để tìm một khoá. Hàm băm tốt hay xấu quyết định bởi số mã phân biệt nó sinh ra: hàm chỉ lấy ký tự đầu cho 16 mã trên 28 tên, nên 12 va chạm là sàn và nới bảng từ 31 lên 64 ô không hạ được một va chạm nào. Cỡ bảng thì không độc lập với hàm băm: trên khoá bình thường, số nguyên tố 31 và luỹ thừa của 2 là 32 cho đúng 9 va chạm như nhau, nhưng trên khoá có bước đều thì 31 cho 0 còn 32 cho 18. Số nguyên tố là bảo hiểm cho cấu trúc bạn chưa biết mình có. Cuối cùng, đừng coi va chạm là sự cố hiếm: bảng 365 ô chỉ cần 23 khoá là va chạm đã nhiều khả năng hơn không, và đó là với hàm băm hoàn hảo, thứ bạn không có.
- 1Bạn băm 28 cái tên bằng hàm chỉ lấy ký tự đầu, và bộ tên đó có 16 chữ cái đầu khác nhau. Nới bảng từ 31 ô lên 64 ô thì số va chạm đổi thế nào?
- 2Trên 28 tên tiếng Việt với hàm cộng mã ký tự, bảng 31 ô và bảng 32 ô cùng cho 9 va chạm. Trên 26 khoá có tổng mã đi đúng bước 4, bảng 31 ô cho 0 va chạm còn bảng 32 ô cho 18. Kết luận đúng là gì?
- 3Một bảng băm có 365 ô. Bạn đưa vào 23 khoá và hàm băm của bạn là hàm băm hoàn hảo, tức mỗi khoá rơi vào ô bất kỳ với cùng xác suất. Khả năng có ít nhất một va chạm là bao nhiêu, và điều đó nói lên gì?