Hệ số tải, và hai cách xử lý va chạm
Hệ số tải, và hai cách xử lý va chạm
Va chạm là chuyện không tránh được. Câu hỏi thật là: khi hai khoá cùng rơi vào một ô thì bạn làm gì, và cái đó tốn bao nhiêu khi bảng đầy dần?
Bài va chạm đã cho thấy va chạm không phải tai nạn hiếm: với một hàm băm tử tế và một bảng còn rất rộng, hai khoá vẫn rơi trúng nhau sớm hơn trực giác nhiều. Nên câu hỏi không phải là làm sao tránh va chạm, mà là va chạm rồi thì làm gì.
Có hai câu trả lời kinh điển, và chúng khác nhau tận gốc.
- Nối chuỗi: mỗi ô của bảng không giữ một khoá mà giữ một danh sách. Hai khoá trùng ô thì cùng nằm trong danh sách đó.
- Dò tuyến tính: mỗi ô giữ đúng một khoá. Ô nhà đã có người thì khoá mới đi sang ô kế tiếp, rồi ô kế tiếp nữa, cho tới khi gặp một ô trống.
Đọc mô tả thì hai cách nghe ngang nhau, và ở một bảng còn rộng thì đúng là chúng gần ngang nhau thật. Chuyện chỉ vỡ ra khi bảng đầy dần. Đại lượng quyết định gọi là hệ số tải, viết là α, bằng số khoá chia số ô. Sim dưới đây thả cùng một bộ khoá vào cả hai kiểu bảng rồi đếm từng lần dò, và mọi tham số đều sửa được.
1 · Bảng và bộ khoá ✎ sửa được
khoá mod số ô, đơn giản nhất có thể, để bạn kiểm được bằng máy tính bỏ túi. Khoá là 48 số nguyên phân biệt rút từ một bộ sinh có hạt giống, nên cùng một hạt giống luôn cho đúng một bộ khoá. Hệ số tải α = số khoá / số ô = 48 / 64 = 0,750.2 · Ba con số, đo trên cùng bộ khoá
| số lần dò trung bình | nối chuỗi | dò tuyến tính | đọc thế nào |
|---|---|---|---|
| khi tìm thấy | 1,35 | 2,15 | trung bình trên 48 khoá đang có trong bảng: 65 và 103 lần dò chia cho 48 |
| khi KHÔNG tìm thấy | 0,75 | 5,28 | trung bình trên 64 ô nhà có thể rơi vào. Nối chuỗi quét hết chuỗi nên ô rỗng tốn 0; dò tuyến tính đi tới khi gặp ô trống và tính cả ô trống ấy, nên ô rỗng tốn 1. |
| tệ nhất | 4 | 9 | khoá đắt nhất trong bảng: chuỗi dài nhất có 4 khoá, còn khoá xa nhà nhất của dò tuyến tính phải đi 9 ô |
Con số tìm không thấy của nối chuỗi luôn đúng bằng hệ số tải, không phụ thuộc hạt giống: tổng độ dài mọi chuỗi bằng đúng số khoá, và bạn chia nó cho số ô. Ở đây là 48 chia 64 bằng 0,750. Còn dò tuyến tính thì không có đẳng thức nào như vậy: nó phụ thuộc vào các khoá dính lại thành cụm dài cỡ nào, và đó là chuyện của mục kế tiếp.
3 · Vẽ ra bảng, và tô cụm
Đây là chỗ giải thích tất cả. Một cụm dài L ô làm hỏng L ô nhà cùng lúc: rơi vào ô đầu cụm thì phải dò L + 1 lần mới tới được ô trống, rơi vào ô thứ hai thì L lần, và cứ thế. Mỗi ô nhà đằng nào cũng trả 1 lần dò cho chính nó, nên phần riêng của cụm là L(L + 1)/2, tức bậc hai theo chiều dài cụm. Cụm dài nhất đang có 18 ô nên nó cộng thêm 171 lần dò, trong tổng 274 lần vượt mức nền của cả bảng. Và cụm càng dài thì càng dễ dài thêm, vì nó chiếm nhiều ô nhà hơn nên khoá mới càng dễ rơi vào nó. Đó là gom cụm sơ cấp.
4 · Kéo hệ số tải từ 0,10 tới 0,95 trên bảng 64 ô
| hệ số tải | số khoá | nối chuỗi: thấy | nối chuỗi: KHÔNG thấy | dò tuyến: thấy | dò tuyến: KHÔNG thấy | dò tuyến: tệ nhất | hai cột “không thấy” |
|---|---|---|---|---|---|---|---|
| 0,10 | 6 | 1,03 | 0,09 | 1,03 | 1,10 | 1,08 | |
| 0,20 | 13 | 1,08 | 0,20 | 1,12 | 1,26 | 1,92 | |
| 0,30 | 19 | 1,13 | 0,30 | 1,19 | 1,48 | 2,50 | |
| 0,40 | 26 | 1,19 | 0,41 | 1,35 | 1,80 | 4,08 | |
| 0,50 | 32 | 1,24 | 0,50 | 1,48 | 2,25 | 5,50 | |
| 0,60 | 38 | 1,29 | 0,59 | 1,64 | 3,10 | 7,00 | |
| 0,70 | 45 | 1,34 | 0,70 | 2,01 | 4,83 | 9,92 | |
| 0,75 | 48 | 1,37 | 0,75 | 2,19 | 6,49 | 11,17 | |
| 0,80 | 51 | 1,39 | 0,80 | 2,48 | 8,98 | 15,25 | |
| 0,85 | 54 | 1,42 | 0,84 | 2,85 | 12,03 | 19,58 | |
| 0,90 | 58 | 1,46 | 0,91 | 3,65 | 16,09 | 27,58 | |
| 0,95 | 61 | 1,47 | 0,95 | 4,18 | 25,83 | 32,83 |
Đọc hàng 0,90: nối chuỗi tốn 0,91 lần dò cho một phép tìm không thấy, dò tuyến tính tốn 16,09, tức gấp 17,8 lần. Trường hợp tệ nhất của dò tuyến tính ở hàng đó là 27,58 ô, so với 3,67 của nối chuỗi. Từ 0,80 trở đi hai cột không còn cùng một câu chuyện nữa.
(1 + 1/(1-α)²)/2 và (1 + 1/(1-α))/2 là kết quả cho một mô hình lý tưởng hoá: băm đều tuyệt đối và bảng lớn vô hạn. Bảng ở đây hữu hạn nên số đo được thấp hơn công thức, và khoảng cách đó thu hẹp lại khi bạn kéo số ô lên: ở hệ số tải 0,90 thì bảng 64 ô đo được khoảng 16 lần dò, bảng 512 ô đo được khoảng 43, còn công thức nói 50,50. Sim không sửa số cho khớp công thức, và bạn cũng đừng.5 · Băm lại: giữ hệ số tải ở dưới ngưỡng ✎ sửa được
| lần | xảy ra ở khoá thứ | số ô cũ | số ô mới | hệ số tải vừa chạm | hệ số tải ngay sau | băm lại mấy khoá | tổng đã băm lại |
|---|---|---|---|---|---|---|---|
| 1 | 7 | 8 | 16 | 0,875 | 0,438 | 7 | 7 |
| 2 | 13 | 16 | 32 | 0,813 | 0,406 | 13 | 20 |
| 3 | 25 | 32 | 64 | 0,781 | 0,391 | 25 | 45 |
Phép so sánh là lớn hơn hẳn, không phải lớn hơn hoặc bằng: đứng đúng trên ngưỡng thì chưa băm lại, thêm một khoá nữa mới băm. Cụ thể với cấu hình đang chạy: 48 khoá trong 64 ô cho hệ số tải 0,750, và bảng đã băm lại 3 lần. Phép so sánh chạy trên số nguyên, số khoá × 100 > 75 × số ô, nên ngưỡng 75% là chính xác chứ không phụ thuộc vào việc 0,75 tròn ra sao trong hệ nhị phân.
- Nó đếm số ô đã nhìn vào, nó không đo giây. Đây là chỗ con số ở đây dễ bị đọc quá lời nhất. Trong máy thật, ở hệ số tải thấp thì dò tuyến tính thường nhanh hơn nối chuỗi dù đếm ra số lần dò tương đương, vì nó đọc các ô nằm liền nhau trong một mảng nên cả dòng nhớ được nạp một lượt, còn nối chuỗi phải nhảy theo con trỏ tới những chỗ rải rác. Không con số nào ở trang này thấy được chuyện đó.
- Nó dùng một hàm băm duy nhất,
khoá mod số ô, trên các khoá rút ngẫu nhiên. Hàm băm tồi trên dữ liệu thật là một nguyên nhân va chạm hoàn toàn khác, và đó là chuyện của bài va chạm. - Nó không xoá khoá. Xoá trong dò tuyến tính là chỗ khó thật sự: xoá thẳng một ô sẽ cắt đứt cụm và làm các khoá phía sau biến mất khỏi phép tìm, nên người ta phải đánh dấu mộ hoặc dồn lại. Sim chỉ chèn.
- Bảng ở mục 3 là một hạt giống. Một lần chạy không phải một quy luật: đổi hạt giống thì cụm dài nhất nhảy khá mạnh. Bảng ở mục 4 trung bình 12 hạt giống chính vì lý do đó, và ngay cả thế thì nó vẫn là một cỡ bảng cụ thể chứ không phải một định lý.
Đếm cái gì, nói trước cho rõ
Một lần dò là một ô hoặc một nút danh sách bạn nhìn vào. Ba con số dưới đây đo cùng một cách cho cả hai kiểu bảng, vì có cùng thước thì mới so được:
- Tìm thấy: trung bình trên các khoá đang có trong bảng, mỗi khoá tốn bao nhiêu lần dò để tìm lại.
- Không tìm thấy: trung bình trên tất cả các ô nhà mà một khoá vắng mặt có thể rơi vào, tốn bao nhiêu lần dò để kết luận là nó không có. Nối chuỗi phải quét hết chuỗi, nên ô rỗng tốn 0 lần dò. Dò tuyến tính đi tới khi gặp ô trống và tính cả ô trống ấy, nên ô rỗng tốn 1 lần dò.
- Tệ nhất: khoá đắt nhất trong bảng phải dò bao nhiêu lần.
Cách quy ước ô rỗng ở dòng giữa là một lựa chọn, không phải chân lý, và nó làm nối chuỗi trông đẹp hơn một chút ở hệ số tải rất thấp. Nói ra để bạn biết mà trừ đi, chứ không phải để giấu.
Ba con số này khác nhau rất rõ, và đó chính là điểm dạy học. Ở trạng thái mở bài, bảng có 64 ô và 48 khoá, tức α = 0,750. Nối chuỗi tốn 1,35 lần dò khi tìm thấy, 0,75 khi không tìm thấy, và tệ nhất là 4. Dò tuyến tính tốn 2,15 khi tìm thấy, 5,28 khi không tìm thấy, và tệ nhất là 9. Ba cặp số, ba khoảng cách khác nhau: khi tìm thấy thì chênh chưa tới gấp đôi, khi không tìm thấy thì chênh 7,04 lần.
Một đẳng thức, và một chỗ không có đẳng thức nào
Con số 0,75 ở trên không phải trùng hợp. Với nối chuỗi, tổng độ dài mọi chuỗi bằng đúng số khoá, và bạn chia nó cho số ô, nên số lần dò trung bình khi không tìm thấy luôn đúng bằng hệ số tải. Không phụ thuộc hàm băm, không phụ thuộc hạt giống, không phụ thuộc may rủi. Đổi hạt giống thì các chuỗi xếp lại hoàn toàn khác, cột “tìm thấy” nhảy, mà cột “không tìm thấy” đứng im. Đó là một bất biến, và cổng kiểm số của bài này khẳng định nó với sai số bằng 0 trên hàng trăm cấu hình.
Dò tuyến tính không có đẳng thức nào như vậy. Số lần dò của nó phụ thuộc vào chuyện các khoá dính lại thành cụm dài cỡ nào, mà chuyện đó thì hàm băm không quyết định được. Đây là chỗ hai cách xử lý va chạm chia tay nhau.
Gom cụm sơ cấp: nhìn thấy nó trên hình
Nhìn bảng bên phải ở mục 3. Các ô có khoá dính vào nhau thành từng cụm liền mạch, cụm nào cũng bị chặn hai đầu bởi ô trống. Ở trạng thái mở bài có 10 cụm, cụm dài nhất 18 ô bắt đầu từ ô 26, và trung bình 4,80 ô mỗi cụm.
Vì sao cụm giết chết phép tìm? Một cụm dài L ô làm hỏng L ô nhà cùng lúc. Khoá vắng mặt rơi trúng ô đầu cụm thì phải đi hết cụm mới gặp ô trống, tức L + 1 lần dò. Rơi vào ô thứ hai thì L lần. Rơi vào ô cuối cụm thì 2 lần. Cộng lại là (L + 1) + L + ... + 2, tức L(L + 1)/2 + L.
Tách con số đó ra thì thấy ngay chỗ đau. Mỗi ô nhà trên cả bảng, kể cả ô trống, đằng nào cũng phải trả 1 lần dò để nhìn vào chính nó, và phần đó tuyến tính, không tránh được. Phần vượt lên trên mức nền ấy mới là phần cụm sinh ra, và nó bằng L(L + 1)/2, tức bậc hai theo chiều dài cụm. Công thức đóng cho cả bảng gọn đúng như vậy: tổng bằng số ô cộng L(L+1)/2 lấy tổng trên mọi cụm.
Ở trạng thái mở bài, tổng chi phí tìm không thấy của cả bảng 64 ô là 338 lần dò, gồm 64 lần nền cộng 274 lần do cụm sinh ra. Riêng cụm 18 ô kia đóng góp 18 × 19 / 2 = 171 trong 274 đó, tức gần hai phần ba, dù nó chỉ chiếm hơn một phần tư số ô. Chín cụm còn lại cộng lại mới được 103.
Và đây là chỗ vòng xoáy khép lại: cụm càng dài thì càng chiếm nhiều ô nhà, nên khoá mới càng dễ rơi vào nó, mà rơi vào nó thì nó lại dài thêm. Hai cụm nằm cạnh nhau, chỉ cách một ô trống, sẽ dính thành một ngay khi có khoá lấp cái ô đó, và cụm mới dài bằng tổng hai cụm cũ cộng một. Hiện tượng này tên là gom cụm sơ cấp, và nó là toàn bộ lý do dò tuyến tính sụp.
Nối chuỗi không có chuyện này. Một chuỗi dài không làm chuỗi bên cạnh dài thêm, vì chúng không đụng gì tới nhau.
Kéo hệ số tải lên, và hai đường tách nhau
Bảng ở mục 4 đo lại cả hai cách ở từng mốc hệ số tải, từ 0,10 tới 0,95, trên cùng cỡ bảng 64 ô. Mỗi ô trong bảng là trung bình của 12 hạt giống liên tiếp chứ không phải một lần chạy, vì một hạt giống trên bảng vài chục ô nhiễu đủ mạnh để giấu mất hình dạng đường cong.
Cột “không tìm thấy”, hai bên đặt cạnh nhau:
α | 0,10 | 0,50 | 0,75 | 0,90 | 0,95 |
|---|---|---|---|---|---|
| nối chuỗi | 0,09 | 0,50 | 0,75 | 0,91 | 0,95 |
| dò tuyến tính | 1,10 | 2,25 | 6,49 | 16,09 | 25,83 |
Cột nối chuỗi là một đường thẳng, vì nó chính là hệ số tải. Cột dò tuyến tính thì đi từ 1,10 lên 25,83, và chỗ dốc nằm hẳn về cuối: mỗi bước sau mốc 0,80 đều dài hơn mọi bước trước đó, và riêng bước cuối từ 0,90 lên 0,95 đã cộng thêm 9,73 lần dò, nhiều hơn cả quãng đường từ 0,10 tới 0,75 gộp lại.
Câu hỏi cụ thể: ở hệ số tải 0,9 thì dò tuyến tính tốn khoảng bao nhiêu lần dò? Đo trên bảng 64 ô, hàng 0,90 dùng 58 khoá nên hệ số tải thật là 0,90625, và kết quả là 16,09 lần dò cho một phép tìm không thấy, so với 0,91 của nối chuỗi. Trường hợp tệ nhất còn cách xa hơn nữa: 27,58 ô so với 3,67.
Có một chi tiết đáng nói vì nó dễ bị kể sai. Tỉ số giữa hai cột gần như đứng yên: 11,75 lần ở α = 0,10 và 17,76 lần ở α = 0,90, tức chỉ tăng khoảng một nửa. Cái thật sự nổ tung là khoảng cách: từ 1,01 lần dò lên 15,19 lần dò, tức gấp 15,07 lần. Lý do là ở hệ số tải thấp thì chính con số của nối chuỗi cũng bé tí, nên chia ra thì tỉ số đã lớn sẵn. Bản nháp đầu của bài này viết là tỉ số tăng mười lần, và chỉ khi đo mới thấy câu đó sai.
Bấm preset hệ số tải 0,90 để thấy đúng 0,9000 trên bảng 80 ô: dò tuyến tính lên 18,55 lần dò, cụm dài nhất nuốt 51 trong 80 ô, và khoá đắt nhất phải đi 44 ô. Sang preset gần đầy 0,95 thì cả bảng chỉ còn 3 cụm, cụm dài nhất 59 ô, và con số lên 24,21.
Số đo thấp hơn công thức trong sách, và đó là chuyện đúng
Sách giáo trình thường cho hai công thức cho dò tuyến tính với giả thiết băm đều: (1 + 1/(1-α))/2 cho phép tìm thấy và (1 + 1/(1-α)²)/2 cho phép tìm không thấy. Ở hàng mang nhãn 0,90 của bảng quét, tức α thật là 0,90625 như đã nêu ở trên, công thức thứ hai cho 50,50, trong khi sim đo được 16,09. Chênh lệch này lớn, và bài này không bẻ số cho khớp.
Lý do là công thức mô tả một mô hình lý tưởng hoá: bảng lớn vô hạn, các dãy dò độc lập nhau. Bảng 64 ô không lớn vô hạn. Kéo núm số ô lên thì con số đo được bò dần về phía công thức: bảng 512 ô ở cùng α = 0,90 đo được 43,47. Hộp “so với công thức” trong sim in cả hai cạnh nhau chính vì lý do đó. Công thức cho bạn dáng của đường cong, còn con số cụ thể thì phụ thuộc cỡ bảng, và trộn hai thứ đó vào nhau là cách nhanh nhất để nói sai.
Băm lại: vì sao không ai để α chạm tới 1
Nếu hệ số tải cao là tai hoạ thì cách chữa hiển nhiên là đừng để nó cao. Bảng băm thật giữ một ngưỡng, và khi hệ số tải vượt ngưỡng thì nó xin một bảng lớn hơn rồi băm lại toàn bộ khoá cũ sang bảng mới. Không thể chỉ chép sang, vì ô nhà là khoá mod số ô, mà số ô vừa đổi.
Mục 5 của sim đếm chuyện đó. Với ngưỡng 75%, bắt đầu từ 8 ô và thêm 48 khoá: 3 lần băm lại, tổng 45 khoá bị băm lại, bảng cuối cùng 64 ô với hệ số tải đúng 0,750. Ba lần đó rơi vào khoá thứ 7, 13 và 25, mỗi lần băm lại đúng chừng ấy khoá, và 7 + 13 + 25 = 45.
Tổng công việc là 48 lần chèn cộng 45 lần băm lại, tức 93 phép cho 48 khoá, 1,94 phép cho mỗi khoá. Đây đúng là lập luận khấu hao của bài mảng động, y hệt một chữ: những lần đắt thì hiếm, và vì sức chứa lớn lên theo kiểu nhân, tổng chi phí của cả lịch sử vẫn nhỏ hơn số khoá nhân một hằng số. Bảng băm chỉ khác mảng động ở một chỗ: mảng động phải chép, còn bảng băm phải tính lại hàm băm cho từng khoá, tức đắt hơn một chút cho mỗi phần tử, nhưng dáng tăng trưởng thì giống hệt.
Mốc biên: đúng trên ngưỡng thì chưa băm lại
Đây là chỗ lệch một đơn vị hay sống sót nhất. Phép so sánh là lớn hơn hẳn, không phải lớn hơn hoặc bằng:
- 48 khoá trong 64 ô cho
α = 0,750, đúng bằng ngưỡng 75%. Không băm lại. Bảng dừng ở 3 lần. - 49 khoá trong 64 ô thì
49/64 = 0,7656, vượt ngưỡng. Băm lại lần thứ tư, và lần này phải băm lại cả 49 khoá, bảng nhảy lên 128 ô.
Một khoá chênh lệch làm bảng rộng gấp đôi. Đổi phép so sánh thành lớn hơn hoặc bằng thì cả cấu hình mở bài này ra kết quả khác, nên cổng kiểm số khẳng định cả hai phía của mốc, và còn khẳng định luôn rằng biến thể sai đưa ra con số khác, để chắc chắn phép kiểm đó phân biệt được thật chứ không chỉ nằm cho có.
Phép so sánh trong sim chạy trên số nguyên, số khoá × 100 > ngưỡng × số ô, nên ngưỡng 75% là chính xác chứ không phụ thuộc vào việc 0,75 tròn ra sao trong hệ nhị phân.
Hạ ngưỡng xuống 50% bằng preset băm lại sớm thì cùng 48 khoá đó tốn 4 lần băm lại, 64 khoá bị băm lại, bảng cuối 128 ô, và 2,33 phép cho mỗi khoá. Đắt hơn về công và tốn gấp đôi bộ nhớ, đổi lại mọi phép tìm đều chạy ở hệ số tải thấp. Đó là một cuộc đánh đổi sòng phẳng, và sim viết nó ra bằng số chứ không khuyên bạn chọn bên nào.
Bảng đầy hoàn toàn: ca hỏng, và sim chặn tường minh
Bấm preset bảng đầy hoàn toàn: 32 khoá trong 32 ô, α = 1,00. Có ba chuyện xảy ra, và chúng khác nhau.
- Chèn: vẫn xong. Khoá cuối cùng tìm được đúng cái ô trống cuối cùng.
- Tìm một khoá có trong bảng: vẫn xong, chỉ là đắt.
- Tìm một khoá vắng mặt: không bao giờ xong. Phép tìm đi tới khi gặp ô trống, mà không còn ô trống nào, nên nó đi vòng quanh bảng mãi mãi.
Sim chặn phép đo thứ ba và nói ra lý do, thay vì treo trình duyệt của bạn hoặc in ra một con số bịa. Ô tương ứng trong bảng ghi “chặn” kèm chữ chứ không chỉ đổi màu. Cổng kiểm số có khẳng định riêng cho ca này: ở α một khoá dưới 1 thì con số phải đo được, ở đúng α = 1 thì phải bị chặn kèm lý do nhưng phần “tìm thấy” vẫn phải tính ra, và ở một khoá trên mức đầy thì cả lượt chạy bị từ chối chứ không âm thầm bỏ bớt khoá.
Nối chuỗi ở đúng hệ số tải 1 thì vẫn chạy bình thường, tốn trung bình 1,00 lần dò cho một phép tìm không thấy, và nó còn chạy tiếp được ở α = 3 hay α = 10. Bảng nối chuỗi không có sức chứa tối đa, nó chỉ chậm dần. Đó là khác biệt sâu nhất giữa hai cách, sâu hơn mấy con số ở trên nhiều.
Cũng vì lý do đó, sim kẹp số khoá không vượt quá số ô và báo cho bạn biết khi nó kẹp: hai cách xử lý va chạm phải chạy trên cùng một bộ khoá thì mới so được, mà dò tuyến tính thì không xếp nổi nhiều khoá hơn số ô.
Sim này đếm lần dò, nó không đo giây
Chỗ này phải nói thẳng, vì đây là cách dễ nhất để đọc quá lời mấy con số ở trên.
Trong máy thật, ở hệ số tải thấp, dò tuyến tính thường nhanh hơn nối chuỗi dù đếm ra số lần dò tương đương hoặc còn nhiều hơn. Lý do nằm ngoài mọi phép đếm ở đây: dò tuyến tính đọc các ô nằm liền nhau trong một mảng, nên cả một dòng nhớ được nạp một lượt và mấy ô kế tiếp gần như miễn phí. Nối chuỗi thì mỗi nút danh sách là một lần nhảy theo con trỏ tới một chỗ khác trong bộ nhớ, mỗi lần nhảy là một lần có thể trượt cache, và một lần trượt cache đắt hơn hàng chục phép so sánh. Nối chuỗi còn tốn thêm bộ nhớ cho con trỏ và cho từng nút.
Sim này không đo được chuyện đó, và cũng không giả vờ đo được. Nó chỉ nói: nếu bạn đếm số ô nhìn vào thì nó ra bấy nhiêu. Muốn biết cái nào nhanh hơn trên máy của bạn với dữ liệu của bạn thì phải đo thật, và bài hiệu năng tập hợp trong Java nói về việc đo đó.
Vài điểm nhỏ nữa, cũng để bạn khỏi đọc sim quá lời:
- Sim không xoá khoá. Xoá trong dò tuyến tính là chỗ khó thật sự: xoá thẳng một ô sẽ cắt cụm làm đôi, và mọi khoá phía sau vết cắt biến mất khỏi phép tìm dù chúng vẫn nằm trong bảng. Người ta phải đánh dấu mộ hoặc dồn lại, và cả hai đều có cái giá riêng. Nối chuỗi thì xoá là gỡ một nút, hết chuyện.
- Hàm băm ở đây là
khoá mod số ôtrên các khoá rút ngẫu nhiên, và khoảng rút được chọn chia hết cho các cỡ bảng hay dùng, nên hàm băm đều tuyệt đối. Nghĩa là mọi cụm bạn nhìn thấy đều do cách xử lý va chạm sinh ra chứ không do hàm băm lệch. Hàm băm tồi trên dữ liệu thật là một nguyên nhân khác hẳn, và đó là chuyện của bài va chạm. - Bảng vẽ ở mục 3 là một hạt giống. Một lần chạy không phải một quy luật: đổi hạt giống thì cụm dài nhất nhảy khá mạnh. Bảng ở mục 4 trung bình 12 hạt giống chính vì lý do đó, và ngay cả thế thì nó vẫn là một cỡ bảng cụ thể chứ không phải một định lý.
- Dò tuyến tính không phải kiểu địa chỉ mở duy nhất. Dò bậc hai và băm kép sinh ra dãy dò khác nên tránh được gom cụm sơ cấp, với cái giá là mất tính liền mạch trong bộ nhớ. Sim này chỉ có kiểu tuyến tính.
Cùng một bộ khoá, hai cách xử lý va chạm, và chúng chỉ giống nhau khi bảng còn rộng. Số lần dò trung bình khi không tìm thấy của nối chuỗi đúng bằng hệ số tải, luôn luôn, nên nó xuống theo đường thẳng. Dò tuyến tính thì đi theo chiều dài cụm, mà một cụm L ô cộng thêm L(L + 1)/2 lần dò lên trên mức nền và cụm càng dài càng dễ dài thêm, nên nó sụp: ở α = 0,90 trên bảng 64 ô, 16,09 lần dò so với 0,91. Ở α = 1 thì dò tuyến tính hỏng hẳn phép tìm-không-thấy, còn nối chuỗi vẫn chạy. Cách chữa là băm lại khi vượt ngưỡng, và cái giá của nó là một lập luận khấu hao y hệt mảng động: 1,94 phép cho mỗi khoá ở cấu hình mở bài. Nhưng đếm lần dò không phải đo thời gian: ngoài đời dò tuyến tính thường thắng ở hệ số tải thấp nhờ đọc bộ nhớ liền mạch, và không con số nào ở trang này thấy được điều đó.
- 1Một bảng băm nối chuỗi có 100 ô và đang giữ 250 khoá. Số lần dò trung bình để kết luận một khoá KHÔNG có trong bảng là bao nhiêu, và bạn cần biết thêm gì để trả lời?
- 2Ở trạng thái mở bài, tổng chi phí tìm-không-thấy của bảng dò tuyến tính là 338 lần dò, gồm 64 lần nền cộng 274 lần do cụm sinh ra. Cụm dài nhất chiếm 18 trong 64 ô, tức hơn một phần tư. Nó đóng góp bao nhiêu trong 274 đó?
- 3Sim đo được ở hệ số tải 0,75 thì dò tuyến tính tốn 5,28 lần dò cho một phép tìm thất bại còn nối chuỗi tốn 0,75. Kết luận nào rút ra được từ con số đó?