Bảng băm

Bảng băm (hash table) là cấu trúc dữ liệu lưu các cặp khóa–giá trị (key–value) và cho phép thêm, tìm, xóa trong $O(1)$ trung bình. Thay vì duyệt cả mảng mất $O(N)$ để tìm một phần tử, bảng băm "nhảy thẳng" tới vị trí cần tìm nhờ một hàm băm biến khóa thành chỉ số. Nhờ đó nhiều bài toán tưởng như cần $O(N^2)$ (đếm tần suất, tìm cặp có tổng cho trước, đếm giá trị phân biệt...) giải được trong $O(N)$.

Trong C++ ta dùng unordered_map / unordered_set; trong Python là dict / set / collections.Counter.

Ý tưởng / Trực giác

Giả sử cần kiểm tra nhanh "giá trị $x$ đã xuất hiện chưa". Cách ngây thơ là duyệt toàn mảng mỗi lần hỏi: $O(N)$ một truy vấn. Bảng băm làm khác:

• Có một mảng (gọi là bucket) gồm $M$ ô.
• Một hàm băm $h(x)$ biến khóa $x$ thành một chỉ số trong $[0,M)$. Ví dụ đơn giản $h(x)=xmodM$.
• Khóa $x$ được lưu ở ô số $h(x)$. Muốn tìm $x$, ta chỉ tính $h(x)$ rồi nhìn đúng ô đó — không cần duyệt cả mảng.

Vì sao trung bình là $O(1)$? Nếu hàm băm phân tán khóa đều ra các ô, mỗi ô chỉ chứa rất ít khóa, nên tính $h(x)$ rồi đọc ô là gần như tức thì. Vấn đề duy nhất là va chạm (collision): hai khóa khác nhau có cùng $h(x)$. Khi đó cùng một ô chứa nhiều khóa, thường được giải quyết bằng danh sách móc nối (chaining) — mỗi ô giữ một danh sách các khóa rơi vào nó. Nếu tải (số khóa / số ô) được giữ nhỏ, mỗi danh sách rất ngắn nên thao tác vẫn $O(1)$ trung bình.

Điểm mấu chốt: bảng băm không giữ thứ tự các khóa (khác với cây tìm kiếm cân bằng). Đổi lại, nó nhanh hơn: $O(1)$ trung bình thay vì $O(\log N)$.

Hình ảnh trực quan: hàm băm và va chạm

Chèn các khóa $5,12,19,7$ vào bảng có $M=5$ ô, với $h(x)=xmod5$:

h(5)  = 5  % 5 = 0
h(12) = 12 % 5 = 2
h(19) = 19 % 5 = 4
h(7)  = 7  % 5 = 2   <-- va chạm với 12 (cùng ô 2)

Bucket sau khi chèn (chaining):

 ô 0 | -> [5]
 ô 1 | (rỗng)
 ô 2 | -> [12] -> [7]     <-- hai khóa cùng ô, nối thành danh sách
 ô 3 | (rỗng)
 ô 4 | -> [19]

Muốn tìm khóa $7$: tính $h(7)=2$, nhảy thẳng tới ô 2, duyệt danh sách ngắn [12] -> [7], thấy $7$. Ta không đụng tới ô 0, 1, 3, 4.

Trong thực tế thư viện chuẩn dùng hàm băm phức tạp hơn $xmod5$ rất nhiều và tự rehash (tăng $M$, băm lại) khi tải quá cao, nên ta chỉ cần dùng unordered_map / dict mà không phải tự cài.

Ví dụ chạy tay: đếm tần suất bằng hash map

Đếm số lần xuất hiện mỗi giá trị trong dãy a = [4, 2, 4, 4, 2, 7]. Dùng unordered_map<int,int> cnt. Duyệt trái sang phải, mỗi bước tăng cnt[a[i]]:

i=0  a[i]=4   cnt = {4:1}
i=1  a[i]=2   cnt = {4:1, 2:1}
i=2  a[i]=4   cnt = {4:2, 2:1}
i=3  a[i]=4   cnt = {4:3, 2:1}
i=4  a[i]=2   cnt = {4:3, 2:2}
i=5  a[i]=7   cnt = {4:3, 2:2, 7:1}
                     ^^^
                    giá trị 4 xuất hiện 3 lần

Mỗi lần cnt[a[i]]++ chỉ mất $O(1)$ trung bình, nên đếm xong toàn dãy chỉ $O(N)$ — so với cách ngây thơ "với mỗi giá trị, duyệt lại cả mảng" tốn $O(N^2)$.

Cài đặt

Hash map (từ điển khóa–giá trị) — C++

#include <unordered_map>
using namespace std;

unordered_map<string, int> mp;
mp["alice"] = 10;            // thêm / gán
mp["bob"]++;                 // nếu chưa có, tự tạo "bob" với giá trị 0 rồi tăng

cout << mp["alice"];         // 10
if (mp.count("alice")) {     // count() trả 0 hoặc 1: kiểm tra tồn tại
    // ... có khóa "alice"
}
// LƯU Ý: mp["x"] sẽ TẠO khóa "x" (giá trị 0) nếu chưa có.
// Muốn chỉ kiểm tra mà không tạo, dùng mp.count() hoặc mp.find().

for (auto& [key, val] : mp) cout << key << ": " << val << "\n";
mp.erase("alice");           // xóa khóa

Hash set (tập hợp) — C++

#include <unordered_set>
using namespace std;

unordered_set<int> st;
st.insert(1); st.insert(2); st.insert(1);  // 1 chỉ được lưu một lần
cout << st.size();    // 2  -> đếm giá trị phân biệt
cout << st.count(5);  // 0  -> kiểm tra 5 có trong tập không

Đếm tần suất & ứng dụng Two Sum — C++

// Đếm tần suất
unordered_map<int,int> cnt;
for (int i = 0; i < n; i++) cnt[a[i]]++;

// Two Sum: tìm i, j sao cho a[i] + a[j] = target, trong O(N)
// idx[v] = chỉ số (1-based) của giá trị v đã gặp.
unordered_map<int,int> idx;
for (int i = 0; i < n; i++) {
    int need = target - a[i];     // số cần để ghép với a[i]
    if (idx.count(need)) {        // đã gặp "need" trước đó?
        cout << idx[need] << " " << i + 1 << "\n";  // tìm thấy cặp
        return;
    }
    idx[a[i]] = i + 1;            // ghi nhận a[i] để các bước sau tra
}
cout << "IMPOSSIBLE\n";

Python

from collections import Counter

mp = {}
mp["alice"] = 10
print(mp.get("charlie", 0))   # 0 nếu không tồn tại (KHÔNG tạo khóa mới)

cnt = Counter([4, 2, 4, 4, 2, 7])
print(cnt[4])                 # 3
print(cnt.most_common(1))     # [(4, 3)]

st = set()
st.add(1); st.add(2); st.add(1)
print(len(st))                # 2  -> số giá trị phân biệt
print(1 in st)                # True

Độ phức tạp

So với cây cân bằng (map/set): unordered_map $O(1)$ trung bình nhanh hơn map $O(\log N)$, nhưng mất thứ tự và xấu nhất $O(N)$ mỗi thao tác nếu bị tấn công va chạm. Nếu cần duyệt khóa theo thứ tự tăng dần, hãy dùng map / set.

⚠️ Lỗi thường gặp

• operator[] âm thầm tạo khóa. Trong C++, if (mp[x] > 0) hay chỉ cần đọc mp[x] cũng tạo khóa x với giá trị 0 nếu chưa có, làm mp.size() phình ra và đếm sai. Muốn chỉ kiểm tra, dùng mp.count(x) hoặc mp.find(x) != mp.end(). Python dict[x] thì ngược lại: ném KeyError nếu thiếu — dùng mp.get(x, 0) hoặc defaultdict/Counter.

• Tràn số khi giá trị/tổng vượt int. Đếm cặp bằng $\sum \left(\genfrac{}{}{0ex}{}{c_v}{2}\right)$ hay tổng các tần suất nhân nhau dễ vượt $2^{31}$. Dùng long long cho biến tích lũy. Ví dụ với $N$ phần tử trùng nhau, số cặp là $\left(\genfrac{}{}{0ex}{}{N}{2}\right)\approx N^2/2$ — với $N={10}^5$ đã hơn $5\times {10}^9$, tràn int.

• Tin rằng unordered_map luôn $O(1)$. Trên Codeforces và nhiều judge, người ta cố tình tạo bộ test "anti-hash" khiến mọi khóa va chạm, biến unordered_map<int,...> thành $O(N)$ mỗi thao tác → TLE. Cách chống: trộn khóa bằng một hằng số ngẫu nhiên (custom hash), hoặc đơn giản dùng map / sắp xếp khi $N$ vừa phải.

• Băm trực tiếp pair/tuple trong C++ không biên dịch. unordered_map<pair<int,int>, int> báo lỗi vì không có hàm băm sẵn cho pair. Phải tự viết hàm băm, hoặc ghép hai số thành một khóa ((long long)x * BASE + y), hoặc dùng map<pair<int,int>, int>.

• So sánh số thực hay xâu dài làm khóa. Khóa double rất rủi ro vì sai số dấu phẩy động khiến hai giá trị "bằng nhau về toán học" lại khác bit. Với khóa là xâu dài, mỗi lần băm phải đọc cả xâu nên thao tác là $O(\text{độ dài})$, không còn $O(1)$ thuần.

• Quên reset bảng giữa các test. Trong bài nhiều test, để sót dữ liệu cũ trong unordered_map từ test trước làm sai kết quả. Hãy .clear() ở đầu mỗi test.

Biến thể / Mở rộng

• unordered_map với khóa tổ hợp: ghép nhiều trường thành một khóa duy nhất (xâu nối, hoặc số gộp bit) khi cần đếm theo nhiều thuộc tính.
• Hash của xâu (polynomial hashing): băm cả một xâu thành một số để so sánh xâu trong $O(1)$ — kỹ thuật riêng, mạnh trong bài xử lý xâu.
• Bảng đếm bằng mảng: khi khóa là số nguyên nhỏ trong $[0,K]$, một mảng int cnt[K+1] còn nhanh và chắc chắn hơn unordered_map (không lo va chạm, truy cập $O(1)$ thật sự).

Bài tập luyện

• Cặp Bằng Nhau (eqpairs) — (Học việc) Đếm số cặp $a_i=a_j$ — dùng map tần suất rồi cộng $\left(\genfrac{}{}{0ex}{}{c_v}{2}\right)$; nhớ dùng long long.
• Phép Đảo Chữ (spellanagram) — (Học việc) Kiểm tra anagram bằng cách so sánh bảng tần suất 26 chữ cái của hai xâu.
• Số Phân Biệt (distnum) — (Nghiệp dư) Đếm số giá trị phân biệt trong dãy — bài tập kinh điển cho unordered_set.
• Tổng Hai Giá Trị (sum2vals) — (Nghiệp dư) Two Sum: với mỗi $a_i$ tra target - a_i trong hash map đã thấy để tìm cặp trong $O(N)$.
• Băm Xáo Trộn (shufhash) — (Nghiệp dư) Kiểm tra hash hợp lệ: tìm cửa sổ con của $h$ có bảng tần suất chữ cái trùng với mật khẩu $p$ — kết hợp đếm tần suất và cửa sổ trượt.