Bảng băm (Hash Table)
1. Khái quát
A. Định nghĩa
Bảng băm (Hash Table) là cấu trúc dữ liệu chuyển một khóa (key) thành chỉ số mảng thông qua hàm băm (hash function), thực hiện chèn, tìm kiếm và xóa trong thời gian hằng số O(1) ở mức trung bình; nó giải quyết xung đột (collision) — khi các khóa khác nhau ánh xạ tới cùng một chỉ số — bằng chaining hoặc open addressing, và bảo đảm hiệu năng thời gian hằng số bằng cách giữ hệ số tải (load factor) dưới một ngưỡng nhất định.
Ý tưởng của bảng băm nằm ở chỗ "đừng tìm bằng cách so sánh từng khóa, hãy tính toán để xác định ngay vị trí lưu trữ từ chính khóa đó." Khi tra một cái tên trong danh bạ, con người không lật từng trang từ đầu mà ước lượng vị trí theo chữ cái — "bắt đầu bằng G nên ở phía trước." Bảng băm đẩy trực giác này đến cực hạn, dùng một hàm biến khóa thành con số để chỉ ngay ô mảng chính xác. Khác với cây tìm kiếm vốn phụ thuộc vào thứ tự (so sánh) giữa các khóa để đạt O(log n), bảng băm phụ thuộc vào nội dung (tính toán) của khóa, kéo số lần so sánh xuống một hằng số không phụ thuộc kích thước đầu vào. Chính sự chuyển dịch từ "so sánh sang tính toán" này là lý do căn bản khiến bảng băm trở thành container liên kết mặc định (hash map, dictionary, set) trong hầu hết mọi ngôn ngữ.
Tuy nhiên thời gian hằng số này không miễn phí mà có điều kiện. Nếu hàm băm không phân tán khóa đều hoặc hệ số tải tăng quá cao, xung đột bùng nổ và hiệu năng trong trường hợp xấu nhất sụp xuống O(n); thêm đầu vào ác ý, điều này leo thang thành một vấn đề an ninh gọi là tấn công xung đột băm (HashDoS). Do đó năng lực cốt lõi của Kỹ sư chuyên nghiệp khi xử lý bảng băm nằm ở phán đoán kỹ thuật để "thiết kế hàm băm tốt cùng chính sách giải quyết xung đột và tái băm phù hợp nhằm đạt O(1) trung bình một cách thực sự, đồng thời phòng thủ trước trường hợp xấu nhất và các mối đe dọa an ninh."
B. Bối cảnh ra đời và sự cần thiết
Phép toán từ điển (dictionary) tìm dữ liệu theo khóa là một trong những tác vụ thường gặp nhất trong điện toán. Lưu vào mảng không sắp xếp hoặc danh sách liên kết khiến tìm kiếm chậm ở O(n), còn tìm kiếm nhị phân trên mảng đã sắp xếp là O(log n) nhưng chèn và xóa tốn O(n) do dịch chuyển phần tử. Cây tìm kiếm nhị phân cân bằng ([[btree-bplus-index]], cây đỏ-đen, v.v.) bảo đảm chèn, tìm kiếm và xóa đều ở O(log n), nhưng chậm dần tỷ lệ với log n khi n lớn lên và hiệu suất cache thấp do truy đuổi con trỏ. Nhu cầu "làm cho phép tra theo khóa nhanh bất kể kích thước đầu vào" đã khai sinh bảng băm, vốn chuyển khóa trực tiếp thành địa chỉ.
Điểm then chốt ở đây là bảng băm là một đánh đổi điển hình hoán đổi không gian lấy thời gian. Một bảng địa chỉ trực tiếp (direct-address table), giữ một ô cho mọi giá trị khóa khả dĩ, đạt O(1) hoàn hảo không xung đột, nhưng dành trước bốn tỷ ô cho một khóa số nguyên 32-bit là phi thực tế. Bảng băm giải quyết sự lãng phí không gian này bằng cách chỉ giữ "một mảng nhỏ (kích thước m) tỷ lệ với số phần tử thực sự lưu trữ (n)" và ánh xạ nén một không gian khóa khổng lồ vào một không gian chỉ số nhỏ. Cái giá phải trả là xung đột — các khóa khác nhau trỏ tới cùng một ô — trở nên không thể tránh khỏi, và xử lý xung đột tốt tới đâu trở thành bản chất của thiết kế bảng băm.
Hơn nữa, việc phần lớn các điểm nghẽn hiệu năng của hệ thống hiện đại tập trung ở tra cứu khóa-giá trị cũng làm tăng sự cần thiết của bảng băm. Chỉ mục băm và kết nối băm của cơ sở dữ liệu ([[join-algorithm]]), quản lý bảng trang và bộ mô tả tệp của OS, bảng ký hiệu của trình biên dịch, bảng luồng của bộ định tuyến mạng, các cache trong bộ nhớ như Redis và Memcached ([[caching-strategy]]), cùng việc khử trùng lặp ([[data-deduplication]]) và tổng hợp của gần như mọi ứng dụng đều chạy trên bảng băm. Trong những môi trường phải xử lý hàng triệu lượt tra mỗi giây như thế, chênh lệch giữa O(log n) và O(1) trở nên quyết định khi tích lũy — và chính vì vậy bảng băm giữ vị thế "cấu trúc dữ liệu được dùng nhiều nhất."
2. Thành phần cấu tạo và nguyên lý hoạt động của bảng băm
Bảng băm hoạt động theo luồng không gian khóa → hàm băm → chỉ số (bucket) → không gian lưu trữ. Sơ đồ cấu trúc dưới đây cho thấy toàn bộ cấu trúc trong đó các khóa kích thước tùy ý được ánh xạ qua hàm băm vào một mảng bucket kích thước cố định và được buộc lại bằng chaining khi xung đột.
flowchart LR
K1["khóa 'apple'"] --> HF["hàm băm h(key)"]
K2["khóa 'grape'"] --> HF
K3["khóa 'melon'"] --> HF
HF --> IDX["chỉ số = h(key) mod m"]
IDX --> B0["bucket0"]
IDX --> B1["bucket1 → (apple) → (melon)"]
IDX --> B2["bucket2 → (grape)"]
IDX --> B3["bucket3"]
B1 -. "cùng bucket = xung đột" .-> B1
Thành phần cốt lõi thứ nhất của bảng băm là hàm băm. Một hàm băm tốt phải thỏa mãn ba điều. Thứ nhất, tính xác định — cùng một khóa phải luôn cho cùng một giá trị thì mới tra cứu được. Thứ hai, phân bố đều (uniformity) — phải rải khóa đều nhất có thể ra các bucket để tối thiểu hóa xung đột. Thứ ba, tính hiệu quả — bản thân việc tính hàm phải nhanh thì O(1) mới có ý nghĩa. Khó nhất trong số này là phân bố đều: cần tính chất rải kết quả không thiên lệch theo mẫu khóa đầu vào (số nguyên liên tiếp, chuỗi có chung tiền tố, v.v.), tức một sự phân tán gần với hiệu ứng tuyết lở (avalanche effect).
Về các kỹ thuật băm tiêu biểu, phương pháp chia (division method) h(k) = k mod m đơn giản để cài đặt nhưng nhạy với việc chọn m. Nếu m là lũy thừa của hai thì chỉ các bit thấp được phản ánh và phân bố xấu đi, nên thường chọn một số nguyên tố (prime) cách xa lũy thừa của hai làm m. Phương pháp nhân (multiplication method) h(k) = ⌊m·(k·A mod 1)⌋ (A là số vô tỷ giữa 0 và 1, thường dựa trên tỷ lệ vàng) ít nhạy với việc chọn m. Với khóa chuỗi, người ta dùng rộng rãi băm cuộn đa thức tích lũy từng ký tự theo đa thức (ví dụ h = h·31 + c; String.hashCode của Java nổi tiếng dùng 31) hoặc các hàm băm phi mật mã như FNV, MurmurHash và xxHash. Ngược lại, để bảo đảm phân bố về mặt toán học, người ta dùng băm phổ quát (universal hashing) — chọn ngẫu nhiên một hàm từ một họ — sao cho ngay cả với bất kỳ đầu vào cụ thể nào thì xác suất xung đột trung bình cũng không quá 1/m; đây cũng là nền tảng lý thuyết cho việc phòng thủ HashDoS bàn ở phần sau.
Vì sao chất lượng phân bố của hàm băm có tính quyết định thì biểu lộ rõ qua con số. Chẳng hạn nếu mọi khóa số nguyên đều là bội của 10 mà dùng phương pháp chia với m=10, mọi khóa dồn vào bucket 0 và tra cứu lập tức sụp xuống O(n). Ngược lại đổi m thành một số nguyên tố như 97 thì phá vỡ tính quy luật "bội của 10," rải khóa đều ra 97 bucket. Vì "hàm băm có hấp thụ được tính quy luật ẩn của đầu vào hay không" chi phối hiệu năng trung bình, nhà thiết kế phải xác nhận bằng đo đạc chứ không giả định phân bố khóa thực tế. Trong các trường hợp đặc biệt khi biết trước toàn bộ không gian khóa và tập phần tử, băm hoàn hảo (perfect hashing) thậm chí có thể đưa xung đột về không: một băm hai tầng (chia bucket bằng băm tầng trên và xử lý mỗi bucket bằng băm cấp hai không xung đột) bảo đảm tra cứu O(1) ngay cả trong trường hợp xấu nhất. Băm hoàn hảo thực sự được dùng trong các tình huống "khóa cố định" như bảng từ khóa dành riêng của trình biên dịch hoặc một tập khóa không đổi (từ điển tĩnh).
Thành phần cốt lõi thứ hai là nén chỉ số. Số nguyên lớn do hàm băm tạo ra được rút về số hiệu bucket thực tế qua phần dư của phép chia cho kích thước mảng m (hoặc mặt nạ bit). Thành phần thứ ba là bucket và chiến lược lưu trữ: mỗi bucket chứa phần tử và xử lý xung đột ra sao là chủ đề của Mục 3. Lý tưởng là nếu n phần tử được đặt đều vào m bucket thì số phần tử trung bình mỗi bucket trở thành hệ số tải α = n/m, và tra cứu là "tính băm + trung bình α lần so sánh trong một bucket," nên O(1) trung bình thành lập chừng nào α còn được giữ hằng số. Rốt cuộc hiệu năng bảng băm được quyết định đồng thời bởi hai trục "chất lượng phân bố của hàm băm" và "quản lý hệ số tải."
Điều phải phân biệt ở đây là độ phức tạp trung bình với độ phức tạp xấu nhất. O(1) của bảng băm chỉ là giá trị kỳ vọng dưới giả định xác suất rằng "các khóa được phân bố đều," và trong trường hợp xấu nhất khi mọi khóa dồn vào một bucket thì tra cứu trở thành O(n). Ở điểm này nó khác về bản chất so với cây cân bằng vốn luôn luôn bảo đảm O(log n) cho mọi phép toán. Vì vậy khi đánh giá bảng băm, phải xét không chỉ hiệu năng trung bình mà còn "trường hợp xấu nhất tệ đến đâu, và trường hợp xấu đó có thể bị khơi gợi một cách ác ý hay không" — câu hỏi trở thành động cơ thiết kế cho việc chuyển sang cây (treeify), băm hoàn hảo và phòng thủ HashDoS bàn ở phần sau.
3. Kỹ thuật giải quyết xung đột và quản lý hệ số tải
Dù hàm băm có tốt đến đâu, nếu không gian khóa lớn hơn số bucket thì xung đột là không thể tránh khỏi về nguyên lý. Như nghịch lý ngày sinh (birthday paradox) cho thấy, chỉ cần đưa vào m bucket khoảng √m phần tử là xung đột xảy ra với xác suất 50%, nên phải thiết kế xung đột như một "đối tượng xử lý thường trực" chứ không phải một "ngoại lệ." Giải quyết xung đột chia lớn thành chaining phân tách và open addressing.
flowchart TB
COL["xung đột: h(k1)=h(k2)"] --> M{"phương thức giải quyết"}
M -->|"lưu ngoài bucket"| CH["chaining phân tách(Chaining)"]
M -->|"lưu trong mảng bucket"| OA["open addressing(Open Addressing)"]
CH --> CHD["buộc bằng danh sách liên kết / cây"]
OA --> LP["dò tuyến tính"]
OA --> QP["dò bậc hai"]
OA --> DH["băm kép"]
CHD --> LF{"vượt hệ số tải α?"}
LP --> LF
QP --> LF
DH --> LF
LF -->|"có"| RH["tái băm: nhân đôi mảng rồi tái bố trí"]
LF -->|"không"| OK["giữ thời gian hằng số"]
A. Chaining phân tách (Chaining)
Chaining phân tách (separate chaining) dùng mỗi bucket làm đầu của một danh sách liên kết (hoặc mảng động/cây), treo mọi phần tử ánh xạ tới cùng bucket lên danh sách đó. Chèn thêm vào đầu danh sách ở O(1), còn tra cứu và xóa duyệt tuyến tính danh sách của bucket đó nên trung bình là O(α). Nếu giữ hệ số tải α hằng số thì O(1) trung bình được bảo đảm, và tính bền vững rằng hoạt động không gãy mà chỉ chậm từ từ ngay cả khi α vượt 1 (nhiều phần tử hơn số bucket) là ưu điểm lớn của chaining.
Thế mạnh của chaining là xóa đơn giản (gỡ một nút khỏi danh sách), chấp nhận được hệ số tải trên 1, và không chịu "phân cụm (clustering)" như open addressing. Mặt khác, mỗi phần tử mang một con trỏ nên chi phí bộ nhớ lớn, và các nút danh sách rải rác khắp bộ nhớ cho tính cục bộ cache (cache locality) kém, nên hiệu năng thực có thể thua con số lý thuyết. Một trường hợp thực tiễn tiêu biểu là HashMap của Java: từ Java 8, khi xung đột trong một bucket vượt 8, danh sách liên kết được chuyển thành cây đỏ-đen (treeify), hạ trường hợp xấu nhất từ O(n) xuống O(log n). Đây là biện pháp phòng thủ tấn công HashDoS vốn dồn xung đột vào một bucket cụ thể bằng đầu vào ác ý — một ví dụ tốt về chiến lược lai "chaining ở mức trung bình, cây ở trường hợp xấu nhất."
Về con số thực tế, đặt n=750 phần tử vào m=1.000 bucket bằng chaining cho α=0,75, trung bình 0,75 phần tử mỗi bucket — tức tra cứu kết thúc trong chưa tới một lần so sánh trung bình. Nhưng nếu hàm băm kém và mọi khóa dồn vào một bucket thì độ dài danh sách của bucket đó thành 750 và tra cứu sụp xuống O(n); việc chuyển sang cây cứu vãn đúng trường hợp này. Như vậy chaining là một giá trị mặc định an toàn vốn "nhanh ở mức trung bình và không sụp đổ ngay cả ở trường hợp xấu nhất," nên nhiều thư viện chuẩn áp dụng nó.
B. Open addressing (Open Addressing)
Open addressing lưu phần tử trong mảng bucket bằng cách tìm một ô trống, không cần danh sách riêng. Khi xung đột, nó lần lượt xem xét các ô kế tiếp theo một quy tắc cố định (trình tự dò, probe sequence) và đặt phần tử vào một ô trống. Dò tuyến tính (linear probing) di chuyển từng ô một theo h(k), h(k)+1, h(k)+2, …; đơn giản để cài đặt và có tính cục bộ cache xuất sắc, nhưng các ô liên tiếp dính lại thành phân cụm sơ cấp (primary clustering), tạo ra chuỗi dò dài. Dò bậc hai (quadratic probing) nới khoảng cách theo h(k)+1², h(k)+2², … để giảm nhẹ phân cụm sơ cấp, nhưng phân cụm thứ cấp — các khóa có cùng vị trí ban đầu đi theo cùng một đường — vẫn còn. Băm kép (double hashing) xác định chính khoảng cách dò bằng một hàm băm thứ hai h₂(k), di chuyển theo h(k)+i·h₂(k), giảm phân cụm hiệu quả nhất nên phân bố tiến gần tới băm phổ quát.
Để lần theo hành vi cụ thể với dò tuyến tính, giả sử m=8 và h("cat")=3, h("dog")=3, h("ant")=4. "cat" vào ô trống 3; "dog" thấy 3 đã chiếm, xem ô 4 vốn trống nên được lưu ở 4. Rồi "ant" thấy h=4 đã bị "dog" chiếm nên bị đẩy sang 5. Cách các khóa có giá trị băm ban đầu khác nhau (3 và 4) dính thành một cụm (3-4-5) chính là phân cụm sơ cấp, và cụm này càng dài thì chuỗi dò của các lần chèn và tra cứu sau đó cũng càng dài theo. Đó chính là lý do dò bậc hai hay băm kép nới khoảng cách dò để làm tan sự dính cụm này.
Open addressing không có con trỏ nên bộ nhớ đặc và hiệu suất cache cao, thường nhanh hơn chaining trên các CPU hiện đại. Đổi lại việc xóa trở nên khó — xóa thẳng một phần tử sẽ cắt đứt chuỗi dò đi qua ô đó khiến không tìm được các phần tử phía sau, nên phải để lại dấu "đã xóa (tombstone)" ở chỗ xóa hoặc kéo một phần tử phía sau về. Ngoài ra hệ số tải không thể vượt 1, và khi α vượt 0,7–0,8 thì chuỗi dò dài ra đột ngột và hiệu năng sụp dốc đứng. dict của Python dùng một trình tự dò thêm nhiễu loạn (perturbation) vào open addressing, còn SwissTable của Rust và Google (Abseil) nổi tiếng với thiết kế hiện đại xem xét siêu dữ liệu của nhiều ô cùng lúc bằng SIMD trên nền open addressing để hạ chi phí dò.
C. Hệ số tải và tái băm (Rehashing)
Cơ chế chung chống đỡ hiệu năng của cả hai phương pháp là quản lý hệ số tải và tái băm. Khi hệ số tải α = n/m vượt một ngưỡng (thường 0,75 với chaining, 0,5–0,7 với open addressing), một mảng lớn hơn (thường gấp đôi) được tạo mới và mọi phần tử được băm lại và tái bố trí. Một lần tái băm trông đắt ở O(n), nhưng tăng mảng gấp đôi giữ tổng chi phí tái băm qua n lần chèn ở O(n), nên phân bổ (amortized) thì duy trì O(1) mỗi lần chèn. Phép phân tích phân bổ này theo cùng nguyên lý với việc mở rộng một mảng động (ArrayList, vector) và là bí quyết để bảng băm giữ "O(1) trung bình" đến cùng.
Tuy nhiên tái băm khiến một lần chèn cụ thể vọt lên (latency spike) O(n), làm xấu đi độ trễ đuôi (tail latency) trong các hệ thống thời gian thực, độ trễ thấp. Để tránh điều này Redis dùng tái băm tăng dần (incremental rehashing), chuyển bucket sang bảng mới từng chút một ở mỗi lần tra cứu hoặc cập nhật thay vì chuyển tất cả một lần, làm phẳng độ trễ. Ngoài ra, chọn kích thước bảng là số nguyên tố hay lũy thừa của hai tại thời điểm tái băm, và có cho phép thu nhỏ (shrink) hay không, cũng là các biến thiết kế chi phối cân bằng giữa bộ nhớ và độ trễ. Như vậy ngưỡng hệ số tải và chiến lược tái băm là các điểm tinh chỉnh cốt lõi quyết định đồng thời hiệu năng trung bình, độ trễ xấu nhất và mức dùng bộ nhớ của bảng băm.
Điều thường bị bỏ sót trong thực tiễn là hiệu quả của định kích thước trước (pre-sizing). Nếu có thể biết đại khái số phần tử sẽ chứa, có thể lấy bảng đủ lớn ngay từ đầu để tránh hẳn tái băm. Chẳng hạn nếu rõ ràng sẽ chèn một triệu mục mà lại khởi đầu với kích thước mặc định (16 chẳng hạn), khoảng 20 lần tái băm xảy ra trong quá trình tăng trưởng và việc sao chép thừa tích lũy lại; chỉ định dung lượng khi tạo (Java new HashMap<>(expectedSize), Go make(map[K]V, n)) loại bỏ chi phí này một lần. Nhưng lấy quá lớn thì lãng phí bộ nhớ và hạ hiệu suất cache, nên khuyến nghị cân bằng bằng cách lấy "số phần tử dự kiến ÷ hệ số tải mục tiêu" làm dung lượng ban đầu.
4. So sánh: Phương thức giải quyết xung đột và cấu trúc dữ liệu thay thế
Việc chọn giữa hai phương thức giải quyết xung đột bên trong bảng băm, và giữa bảng băm với cây tìm kiếm, phân nhánh theo "tối ưu hóa cái gì." Bảng dưới đây sắp xếp các khác biệt đó, nhưng lý do căn bản sinh ra khác biệt nằm ở đặt dữ liệu ở đâu và như thế nào.
| Phân loại | Chaining phân tách | Open addressing |
|---|---|---|
| Vị trí lưu trữ | Danh sách/cây ngoài bucket | Trong mảng bucket |
| Giới hạn hệ số tải | Cho phép α>1 (giảm từ từ) | Bắt buộc α<1, khuyến nghị 0,7 |
| Tính cục bộ cache | Thấp (con trỏ phân tán) | Cao (bộ nhớ liên tục) |
| Xóa | Đơn giản (gỡ nút) | Phức tạp (cần tombstone) |
| Chi phí bộ nhớ | Thêm con trỏ | Dư ô trống |
| Hiện tượng phân cụm | Không | Xảy ra ở dò tuyến tính/bậc hai |
Sự đảo ngược hiệu năng giữa chaining và open addressing bắt nguồn từ phân tầng bộ nhớ. Về lý thuyết cả hai đều O(1) trung bình, nhưng trên CPU hiện đại một lần trượt cache tốn hàng trăm nhịp xung, nên open addressing — vốn dò tuyến tính một mảng liên tục — thường nhanh hơn trong đo đạc so với chaining vốn truy đuổi một danh sách rải rác dọc con trỏ. Ngược lại nếu phần tử lớn hoặc xóa thường xuyên và muốn dùng hệ số tải cao thì chaining có lợi. Do đó không được đồng nhất hai bên chỉ vì "độ phức tạp lý thuyết như nhau"; phải chọn bằng cách cân nhắc đồng thời hành vi cache, kích thước phần tử, tần suất xóa và hệ số tải mục tiêu.
Việc chọn giữa hai phương thức phân nhánh thế nào trong thực tiễn biểu lộ rõ ràng ở thư viện chuẩn của các ngôn ngữ. HashMap của Java và std::unordered_map của C++ mặc định chaining, được thiết kế để bền vững với xóa và hệ số tải cao, trong khi dict của Python, HashMap của Rust và flat_hash_map Abseil của Google chọn open addressing để tối đa hóa hiệu suất cache và tốc độ tra cứu. Lý do chiến lược nội bộ khác nhau dù cùng mang tên "hash map" là vì mỗi ngôn ngữ giả định các khối lượng công việc điển hình khác nhau (tần suất xóa, kích thước phần tử, mức độ phơi nhiễm với đầu vào bên ngoài) và giả định phần cứng khác nhau. Do đó không được phán đoán trước hiệu năng dựa trên giả định "các hash map đều như nhau"; xác nhận chiến lược nội bộ và chính sách hệ số tải của bản cài đặt đang dùng là điểm khởi đầu của việc tinh chỉnh hiệu năng.
So sánh giữa bảng băm và cây tìm kiếm cân bằng ([[btree-bplus-index]], cây đỏ-đen) thì căn bản hơn. Bảng băm nhanh hơn ở O(1) trung bình so với O(log n) của cây, nhưng có ràng buộc quyết định là không bảo toàn thứ tự. Nếu cần truy vấn khoảng (range query, "mọi khóa giữa 100 và 200"), duyệt theo thứ tự, tra cứu min/max hay tìm khóa lân cận thì bảng băm trở thành quét toàn bộ O(n) trong mọi trường hợp và cây vượt trội áp đảo. Nên một chỉ mục cơ sở dữ liệu chọn chỉ mục băm nếu chỉ tra cứu bằng (equality) và chọn chỉ mục cây B+ khi có lẫn truy vấn khoảng. Ngoài ra, vì bảng băm có O(n) xấu nhất và độ trễ tái băm, trong các hệ thống thời gian thực nơi độ trễ xấu nhất quan trọng, một cây luôn luôn bảo đảm O(log n) thì dễ dự đoán hơn. Tóm lại "hash nếu ưu tiên tra cứu bằng và tốc độ trung bình; cây nếu ưu tiên thứ tự, khoảng và bảo đảm xấu nhất" là tiêu chí phán đoán trong bài làm của Kỹ sư chuyên nghiệp.
5. Chuyên sâu: Bảng băm hiện đại và an ninh
Từ những năm 2000, bảng băm cổ điển đã tiến hóa mạnh để đáp ứng các yêu cầu về bảo đảm trường hợp xấu nhất và đa nhân cùng an ninh. Dòng chảy thứ nhất là open addressing nâng cao kéo hiệu năng xấu nhất xuống hằng số. Băm cuckoo (cuckoo hashing) đặt hai hoặc nhiều hàm băm và bảng sao cho mỗi khóa chỉ nằm ở "một trong hai vị trí," và khi vị trí đầy thì đuổi phần tử hiện có sang bảng khác (như chim cu cu cướp tổ) rồi tái bố trí, qua đó đạt tra cứu xấu nhất O(1) (một số lần kiểm tra hằng số). Băm Robin Hood (Robin Hood hashing) tái bố trí để "nhường chỗ cho phần tử có khoảng cách dò dài (nghèo)," giảm phương sai của khoảng cách dò và cải thiện độ trễ đuôi, còn băm hopscotch (hopscotch hashing) gom các phần tử vào trong vùng lân cận (neighborhood) gần bucket gốc, nhắm đồng thời tới hiệu suất cache và bảo đảm xấu nhất. Chúng là sản phẩm của ý thức vấn đề hiện đại "mức trung bình đã nhanh rồi, hãy xử lý trường hợp xấu nhất và phương sai độ trễ."
Dòng chảy thứ hai là bảng băm đồng thời (concurrent hash table). Trên đa nhân, bảo vệ toàn bảng bằng một khóa khổng lồ sẽ làm mất tính song song, nên ConcurrentHashMap của Java chia nhỏ khóa theo từng bucket (hoặc segment) (xem [[process-synchronization]]) và trộn thêm các phép toán không khóa (lock-free) như CAS để tối thiểu hóa tranh chấp dù hàng chục luồng truy cập đồng thời. Đặc biệt, qua các kỹ thuật như để nhiều luồng chia nhau thực hiện tái băm hay xử lý việc đọc không cần khóa (chỉ bằng tính khả kiến volatile), nó đạt khả năng mở rộng gần như tuyến tính trên khối lượng công việc nghiêng về đọc. Điều này cho thấy bảng băm đã mở rộng vượt khỏi một cấu trúc dữ liệu đơn luồng để thành nền tảng của các hệ thống song song hiệu năng cao.
Dòng chảy thứ ba là an ninh. Khi kẻ tấn công gửi một khối lượng lớn khóa đều ánh xạ tới cùng một bucket, bảng băm thoái hóa thành O(n) và vắt kiệt CPU — một tấn công HashDoS (hash-flooding) đã trở thành hiện thực ở nhiều framework web vào năm 2011. Khi đó hầu hết các stack web — PHP, Java, Python, Ruby, ASP.NET, v.v. — đặt các tham số HTTP POST vào một bảng băm (mảng liên kết), và kẻ tấn công chỉ gửi một yêu cầu chứa hàng vạn khóa xung đột cũng có thể khiến máy chủ tiêu tốn hàng chục giây CPU để phân tích riêng yêu cầu đó, làm tê liệt dịch vụ chỉ với một nhúm yêu cầu (CVE-2011-4815, v.v.). Sự kiện này khắc sâu rằng nguyên tắc an ninh "không tin đầu vào" phải áp dụng cả tới giả định phân bố của một cấu trúc dữ liệu. Làm biện pháp phòng thủ, SipHash, một băm có khóa (keyed hash) trộn băm với một khóa bí mật theo từng tiến trình, đã trở thành chuẩn, ngăn kẻ tấn công dự đoán hay khơi gợi xung đột. Việc Python, Rust, Ruby và nhiều ngôn ngữ khác áp dụng SipHash hoặc biến thể của nó làm băm mặc định là tiêu biểu, và việc chuyển sang cây của Java HashMap cũng là một biện pháp giảm nhẹ cùng mạch. Việc "giả định phân bố của một cấu trúc dữ liệu hiệu năng" có thể tự nó trở thành bề mặt an ninh là một chủ đề chuyên sâu quan trọng cho thấy thiết kế bảng băm giáp ranh với lĩnh vực kỹ thuật an ninh vượt khỏi thuật toán.
Cuối cùng, ứng dụng của bảng băm vượt khỏi phạm vi cấu trúc dữ liệu. Kết nối băm của cơ sở dữ liệu xây một bảng băm từ bảng nhỏ rồi kết nối bằng cách quét bảng lớn một lần; bộ lọc Bloom ([[bloom-filter]]), Count-Min sketch ([[count-min-sketch]]) và HyperLogLog ([[hyperloglog]]) mở rộng băm thành các cấu trúc dữ liệu xác suất để giảm bộ nhớ một cách ngoạn mục; và băm nhất quán ([[consistent-hashing]]) tối thiểu hóa việc tái bố trí khi biến động nút trong cache phân tán và sharding. Ở gốc rễ mọi kỹ thuật này là ý tưởng cốt lõi của bảng băm "ánh xạ một khóa tới một vị trí bằng tính toán." Nghĩa là bảng băm không chỉ tự thân là cấu trúc dữ liệu được dùng rộng rãi nhất mà còn là nền tảng chung của vô số kỹ thuật nâng cao vươn tới các cấu trúc dữ liệu xác suất, hệ thống phân tán và động cơ cơ sở dữ liệu — nên phải hiểu nó như một nguyên lý thiết kế vượt xa phạm vi của một cấu trúc dữ liệu đơn lẻ.
6. Cân nhắc và hàm ý
Khi đưa các nguyên lý, kỹ thuật và sự tiến hóa đã xem xét đến nay vào thiết kế hệ thống thực, Kỹ sư chuyên nghiệp phải phán đoán tổng hợp hàm băm, giải quyết xung đột, hệ số tải, an ninh và tính đồng thời để đạt thực sự hiệu năng sách giáo khoa "O(1) trung bình." Sau đây là các cân nhắc cốt lõi.
Kiểm chứng chất lượng phân bố của hàm băm theo đặc tính dữ liệu. Vì O(1) trung bình đứng trên giả định "các khóa được phân bố đều," phải đo xem hàm băm có cho phân bố đều với các mẫu khóa thực tế (ID liên tiếp, tiền tố chung, phân bố lệch) hay không. Giám sát các chỉ số như mức chiếm dụng bucket, độ dài chuỗi tối đa và tỷ lệ xung đột, và nếu phân bố kém thì xem xét áp dụng một hàm băm (MurmurHash, xxHash, v.v.) hoặc băm phổ quát để loại trừ khuyết tật hiệu năng tiềm ẩn chỉ chậm với các đầu vào cụ thể.
Chọn phương thức giải quyết xung đột theo khối lượng công việc và phần cứng. Nếu xóa thường xuyên, dùng hệ số tải cao và phần tử lớn thì chaining có lợi; nếu nghiêng về tra cứu và hiệu suất cache cùng độ trễ thấp quan trọng thì open addressing (đặc biệt dò tuyến tính, SwissTable) có lợi. Dù độ phức tạp lý thuyết như nhau, hành vi cache quyết định hiệu năng đo được, nên hãy quyết định bằng cách xác nhận CPU mục tiêu, kích thước phần tử và tần suất xóa qua benchmark.
Quản lý độ trễ bằng ngưỡng hệ số tải và chiến lược tái băm. Lấy hệ số tải thấp thì nhanh nhưng lãng phí bộ nhớ; lấy cao thì đặc nhưng tăng xung đột (khoảng 0,7 là điểm uốn với open addressing). Trong các hệ thống độ trễ thấp nơi cú vọt độ trễ O(n) của tái băm là vấn đề, hãy làm phẳng độ trễ đuôi bằng tái băm tăng dần kiểu Redis hoặc định kích thước trước (pre-sizing), và thiết kế để bảo đảm O(1) trung bình qua phân tích phân bổ.
Phòng thủ mối đe dọa an ninh (HashDoS) theo mặc định. Mọi bảng băm nhận đầu vào bên ngoài làm khóa (tham số HTTP, JSON, phân tích header, v.v.) có thể bị kẻ tấn công khơi gợi xung đột để làm thoái hóa về O(n), nên hãy dùng một băm có khóa như SipHash theo mặc định và đặt trần cho số phần tử mỗi bucket (chuyển sang cây, tái băm) để giới hạn trường hợp xấu nhất về hằng số hoặc logarit. Phản ánh ngay từ đầu thiết kế quan điểm rằng giả định phân bố của một cấu trúc dữ liệu hiệu năng tự nó là một bề mặt tấn công.
Khi có yêu cầu thứ tự/khoảng thì chạy song song cấu trúc dữ liệu thay thế. Bảng băm tối ưu cho tra cứu bằng nhưng không hỗ trợ truy vấn khoảng, duyệt theo thứ tự hay tra cứu giá trị nhỏ nhất. Khi các yêu cầu đó lẫn vào, hãy dùng kèm cây B+ hay skip list ([[skip-list]]), hoặc trong cơ sở dữ liệu thì chọn giữa chỉ mục băm và chỉ mục cây B+ theo loại truy vấn, kết hợp các cấu trúc dữ liệu để xử lý mỗi phép toán ở độ phức tạp phù hợp.
Trong môi trường đồng thời, áp dụng chia khóa và thiết kế không khóa. Trên đa nhân, bảo vệ bảng bằng một khóa toàn cục làm mất tính song song, nên hãy giảm tranh chấp bằng chia khóa theo bucket/segment hoặc các phép toán không khóa dựa trên CAS (ConcurrentHashMap, v.v.), và chọn một thiết kế bảo đảm tính nhất quán (khả kiến, nguyên tử) của truy cập đồng thời trong lúc tái băm, bảo đảm khả năng mở rộng cho khối lượng công việc nghiêng về đọc.
Loại bỏ chi phí ban đầu bằng định kích thước trước phản ánh quy mô dự kiến. Nếu có thể ước lượng số phần tử sẽ chứa, hãy chỉ định dung lượng khi tạo là "số phần tử dự kiến ÷ hệ số tải mục tiêu" để loại bỏ tái băm lặp lại trong quá trình tăng trưởng; ngược lại nếu quy mô không chắc chắn thì khởi đầu thận trọng để tránh lãng phí bộ nhớ. Trên các đường batch/khởi tạo nơi dự kiến nạp hàng loạt, gợi ý dung lượng một dòng này chi phối lớn tới thông lượng tổng thể, nên hãy coi nó là một hạng mục kiểm tra cơ bản của thiết kế hiệu năng.
Tổng hợp lại, bảng băm là cấu trúc dữ liệu được dùng rộng rãi nhất trong điện toán, cung cấp các phép toán từ điển O(1) trung bình bằng ý tưởng đơn giản "ánh xạ một khóa tới một vị trí bằng tính toán." Nhưng thời gian hằng số đó chỉ được hiện thực hóa khi hội đủ các điều kiện kỹ thuật là hàm băm tốt, giải quyết xung đột phù hợp và quản lý hệ số tải, và dễ dàng sụp đổ nếu không xử lý các biến số thực tế là trường hợp xấu nhất, độ trễ tái băm, HashDoS và tính đồng thời. Kỹ sư chuyên nghiệp phải chẩn đoán đặc tính dữ liệu và khối lượng công việc để thiết kế hàm băm cùng chính sách giải quyết xung đột và tái băm, kết hợp với cây khi có yêu cầu thứ tự, và với năng lực thiết kế tổng hợp bao quát cả an ninh và tính đồng thời, biến "thời gian hằng số có điều kiện" thành "thời gian hằng số thực sự."
Tài liệu tham khảo
- T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, "Introduction to Algorithms" (4th ed.), Chapter 11: Hash Tables, MIT Press. https://mitpress.mit.edu/9780262046305/introduction-to-algorithms/
- R. Pagh, F. F. Rodler, "Cuckoo Hashing", Journal of Algorithms, 2004. https://www.sciencedirect.com/science/article/pii/S0196677403001925
- J. Aumasson, D. J. Bernstein, "SipHash: a fast short-input PRF", 2012. https://www.aumasson.jp/siphash/siphash.pdf
- Google Abseil, "Swiss Tables Design Notes". https://abseil.io/about/design/swisstables
Tóm tắt một câu: Bảng băm ánh xạ một khóa tới chỉ số mảng qua một hàm băm để thực hiện chèn, tìm kiếm và xóa ở O(1) trung bình; nó giải quyết xung đột bằng chaining hoặc open addressing, giữ hệ số tải dưới một ngưỡng và bảo toàn O(1) phân bổ qua tái băm — nhưng chỉ khi xử lý về mặt kỹ thuật các điều kiện chất lượng phân bố của hàm băm, trường hợp xấu nhất, độ trễ tái băm, HashDoS và tính đồng thời thì "thời gian hằng số có điều kiện" mới trở thành "thời gian hằng số thực sự."