Bít hóa
Đã giới thiệu| English | Ý nghĩa |
|---|---|
| hash function/hæʃ ˈfʌŋkʃn/ | hàm băm |
| key/kiː/ | khóa |
| address/əˈdres/ | địa chỉ |
| deterministic/dɪˌtɜːmɪˈnɪstɪk/ | Xác định được |
| collision/kəˈlɪʒn/ | xung đột |
| linear probing/ˈlɪnɪə ˈprəʊbɪŋ/ | 探测 tuyến tính |
| chaining/ˈtʃeɪnɪŋ/ | liên kết |
| load factor/ləʊd ˈfæktə/ | hệ số tải |
Tìm một dòng trong năm mươi triệu mà không cần dò xét
- Quét thanh hóa đơn siêu thị và giá xuất hiện trước khi tay bạn rời khỏi sản phẩm. Tệp sản phẩm chứa năm mươi triệu dòng.
- Không có cái nào được tìm kiếm. Số mã vạch đi qua một phép tính ngắn gọn tạo ra một vị trí, và máy tính đọc vị trí đó: một lần đọc, không so sánh, mất cùng thời gian dù tập tin có năm mươi dòng hay năm mươi triệu dòng.
- Phép tính đó là hàm băm, và toàn bộ ý tưởng dựa vào nó: đừng lưu dữ liệu vào nơi nó vừa vặn, hãy lưu vào nơi chính khóa riêng của nó bảo nó thuộc về.
- Bài học này về thuật toán băm, những gì xảy ra khi hai khóa muốn chiếm cùng một ô, và cách tìm kiếm và chèn.
Hàm băm
- Một hàm băm, hay thuật toán băm, nhận khóa của một bản ghi và tạo ra địa chỉ nơi bản ghi được lưu trữ.
- Một hàm băm tốt thì nhanh, xác định (cùng một khóa luôn tạo ra cùng một địa chỉ), và phân bổ khóa đều trên các ô khả dụng.
- Đối với $N$ ô chứa, chương trình học yêu cầu ba phương pháp: modulo,
address ← key MOD N; gấp fold, chia khóa thành các phần, cộng chúng lại, sau đó MOD $N$; hash chuỗi string, cộng mã ký tự, sau đó MOD $N$.
Một hàm bít hóa:
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Hàm bít hóa ánh xạ khóa thành địa chỉ, cho phép tra cứu trực tiếp gần như tức thì.
Điều gì làm cho hàm bít hóa là một hàm tốt? Chọn tất cả các áp dụng.
Difficulty 2/5 · 140 coins + a small bonus on first completion today
Nhanh, xác định và phân bố đều. Không có hàm hash thực tế nào tránh được va chạm hoàn toàn, đó là lý do mọi thiết kế đều bao gồm chiến lược giải quyết.
Ví dụ có hướng dẫn: áp dụng từng thuật toán
- Một tập tin có 10 ô chứa, đánh số từ 0 đến 9. Khóa 4517 sẽ được đặt vào đâu?
- Modulo: $4517 \bmod 10 = 7$, nên vào ô 7.
- Gấp theo cặp: $45 + 17 = 62$, rồi $62 \bmod 10 = 2$, nên vào ô 2.
- Và khóa "CAB" bằng hash chuỗi? $67 + 65 + 66 = 198$, rồi $198 \bmod 10 = 8$, nên vào ô 8.
- Hiển thị phép tính. Điểm số dành cho phép tính, không chỉ riêng số ô chứa.
Sử dụng hàm hash chia dư address ← key MOD N với key = 27 và N = 10, địa chỉ nào sẽ được tạo ra?
Difficulty 2/5 · 140 coins + a small bonus on first completion today
27 MOD 10 = 7 (phần dư khi chia 27 cho 10).
Một bảng có 10 ô chứa. Sử dụng phương pháp gập đôi trên key 4517 (cộng 45 và 17, sau đó MOD 10), nó sẽ vào ô nào?
Difficulty 2/5 · 140 coins + a small bonus on first completion today
45 + 17 = 62, và 62 MOD 10 = 2. Cùng một khóa dưới hàm hash modulo sẽ đi vào ô chứa 7 thay vì thế.
Va chạm
- Va chạm xảy ra khi hai khóa khác nhau tạo ra cùng một địa chỉ. Với bất kỳ hàm hash và tập tin thực tế nào, va chạm là điều chắc chắn, vì vậy chiến lược xử lý phải là một phần của thiết kế, chứ không phải suy nghĩ thêm sau này.
- Quét tuyến tính linear probing đặt bản ghi vào ô trống tiếp theo, vòng ngược về đầu bảng khi kết thúc bảng. Đơn giản, nhưng các bản ghi bám cụm cluster: một vùng đầy sẽ mở rộng và mỗi khóa rơi vào đó sẽ mất nhiều thời gian hơn để truy xuất.
- Nối chaining khiến mỗi ô trở thành đầu của một danh sách liên kết linked list chứa tất cả các bản ghi đã hash vào đó. Không có hiện tượng bám cụm, nhưng tốn bộ nhớ phụ cho con trỏ và cần duyệt qua danh sách ngắn.
- Hash lại rehashing áp dụng hàm hash thứ hai để tìm ô khác, phân bổ khóa tốt hơn với chi phí là nhiều phép tính hơn.
Va chạm xảy ra khi:
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Hai key ánh xạ đến cùng một ô chứa là va chạm; nó phải được giải quyết bằng cách dò tìm, liên kết hoặc làm lại hàm hash.
Gắn mỗi ý tưởng xử lý va chạm với những gì nó làm.
Difficulty 2/5 · 140 coins + a small bonus on first completion today
Va chạm được giải quyết bằng liên kết hoặc dò tìm; giữ hệ số tải thấp giúp tìm kiếm gần O(1).
Tìm kiếm và chèn
- Để chèn: hash khóa. Nếu ô trống, ghi bản ghi vào đó. Nếu không, tuân theo chiến lược giải quyết,即到 ô trống tiếp theo cho quét tuyến tính, hoặc đầu danh sách của ô đó cho nối chaining.
- Để tìm kiếm: hash khóa và đọc ô đó. Nếu khóa lưu trữ khớp, bản ghi được tìm thấy. Nếu không, làm theo chiến lược tương tự, cho đến khi khóa khớp hoặc một ô trống chứng minh bản ghi không có trong tập tin.
- Cả hai thao tác đều sử dụng cùng một chiến lược. Một phép tìm kiếm dừng lại ở sự không khớp đầu tiên sẽ bỏ sót mọi bản ghi từng bị dịch chuyển do va chạm.
Ví dụ có hướng dẫn: truy vết va chạm
- Một bảng có 10 ô chứa sử dụng
key MOD 10với quét tuyến tính. Chèn 23, 33, 43 theo thứ tự đó, sau đó tìm 43. - 23 hash về 3; ô 3 trống, nên vào đó. 33 hash về 3; ô 3 đã bị 23 chiếm, nên quét tuyến tính đưa nó vào ô 4. 43 hash về 3; ô 3 và 4 đã bị chiếm, nên vào ô 5.
- Tìm 43: hash về 3, đọc ô 3, khóa là 23, không khớp, nên quét tiếp; ô 4 chứa 33, không khớp; ô 5 chứa 43, tìm thấy, sau ba lần đọc.
- Chuỗi ba ô liên tiếp đang tăng dần chính là hiện tượng bám cụm mà quét tuyến tính gây ra.
Bít hóa mỗi khóa thẳng vào thùng chứa
Hàm bít hóa chuyển khóa thành số thùng chứa, vì bạn nhảy thẳng vào bản ghi thay vì tìm kiếm. Khi hai khóa rơi vào cùng một thùng chứa thì đó là va chạm — chúng liên kết trong thùng chứa đó.
Khi tìm kiếm trong bảng hash, bản ghi không có trong tệp ngay khi ô chứa đầu tiên đọc được chứa một key khác.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Bản ghi có thể đã bị dịch chuyển do va chạm. Việc tìm kiếm tuân theo cùng chiến lược giải quyết cho đến khi khớp hoặc gặp ô trống.
Hệ số tải
- Hệ số tải load factor là số lượng bản ghi chia cho số lượng ô chứa. Đây là con số duy nhất dự đoán hiệu năng của bảng.
- Dưới khoảng 70%, thời gian tìm kiếm trung bình gần như một lần đọc. Trên mức đó, chuỗi quét dài ra đáng kể và hiệu năng suy giảm tiến tới tìm kiếm tuyến tính.
- Giải pháp là mở rộng bảng và hash lại mọi bản ghi vào đó, đó là lý do bảng hash được kích thước dựa trên dữ liệu nó sẽ chứa, chứ không phải dữ liệu nó đang chứa hôm nay.
Một bảng 10 ô sử dụng key MOD 10 với dò tìm tuyến tính. Sau khi chèn 23, 33 và 43 theo thứ tự đó, ô nào chứa 43?
Difficulty 2/5 · 140 coins + a small bonus on first completion today
Cả ba đều hash về ô 3. 23 chiếm ô 3, 33 dò tìm sang ô 4, và 43 sang ô 5. Ba key liên tiếp chính là hiện tượng cụm mà dò tìm tuyến tính gây ra.
Điểm số dễ mất
- Va chạm là hai khóa, một địa chỉ. Nó không phải lỗi và cũng không phải bản ghi bị mất; nó là trường hợp bình thường mà chiến lược xử lý.
- Phép tìm kiếm phải làm theo cùng chiến lược giải quyết như phép chèn, và chỉ dừng lại khi khớp hoặc gặp ô trống.
- Quét tuyến tính bám cụm; nối chaining tốn bộ nhớ. Hãy nêu sự đánh đổi trade-off, không chỉ cơ chế hoạt động.
- Hệ số tải là số bản ghi chia cho số ô chứa, và ngưỡng là khoảng 70%, không phải 100%.
Để giữ cho việc tìm kiếm bảng hash nhanh, hệ số tải (số bản ghi ÷ số ô chứa) nên được giữ:
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Hệ số tải thấp hơn có nghĩa là ít va chạm hơn, nên việc tìm kiếm vẫn duy trì gần O(1).
Bạn đã nắm vững
- một hàm hash biến một khóa thành một địa chỉ: nhanh, xác định, phân bố đều; modulo, gấp và hash chuỗi là ba phương pháp cần biết
- một va chạm là hai khóa hash về một địa chỉ, được giải quyết bằng quét tuyến tính (ô trống tiếp theo, bám cụm), nối chaining (mỗi ô một danh sách liên kết, tốn bộ nhớ) hoặc hash lại
- chèn và tìm kiếm đều làm theo cùng chiến lược; phép tìm kiếm kết thúc khi khớp hoặc gặp ô trống
- giữ hệ số tải, số bản ghi chia cho số ô chứa, dưới khoảng 70% để tra cứu chỉ mất một lần đọc