Bảng băm

Wiki › Cấu trúc dữ liệu

huunguyen · Last updated 28, Tháng 3, 2026, 22:44

Bảng băm lưu trữ cặp key-value và cho phép tìm kiếm, thêm, xóa trong $O (1)$ trung bình nhờ hàm băm (hash function).

Độ phức tạp

Thao tác	Trung bình	Xấu nhất
Tìm kiếm	$O (1)$	$O (N)$
Thêm	$O (1)$	$O (N)$
Xóa	$O (1)$	$O (N)$

Hash Map (key-value)

C++ — `unordered_map`

#include <unordered_map>
unordered_map<string, int> mp;

mp["alice"] = 10;
mp["bob"] = 20;

cout << mp["alice"];  // 10

if (mp.count("alice")) { ... }  // kiểm tra tồn tại

for (auto& [key, val] : mp)
    cout << key << ": " << val << "\n";

mp.erase("alice");

Python — `dict`

mp = {}
mp["alice"] = 10
mp["bob"] = 20

print(mp["alice"])
print("alice" in mp)       # True
mp.get("charlie", 0)       # 0 nếu không tồn tại

for key, val in mp.items():
    print(key, val)

del mp["alice"]

# Counter — đếm tần suất
from collections import Counter
cnt = Counter([1, 2, 2, 3, 3, 3])
print(cnt[3])  # 3

Hash Set (chỉ key)

C++ — `unordered_set`

#include <unordered_set>
unordered_set<int> st;
st.insert(1); st.insert(2); st.insert(1);
cout << st.size();    // 2
cout << st.count(1);  // 1
st.erase(1);

Python — `set`

st = set()
st.add(1); st.add(2); st.add(1)
print(len(st))  # 2
print(1 in st)  # True
st.remove(1)

Ứng dụng thường gặp

Đếm tần suất

unordered_map<int, int> freq;
for (int x : a) freq[x]++;

Two Sum

unordered_map<int, int> idx;
for (int i = 0; i < n; i++) {
    int need = target - a[i];
    if (idx.count(need))
        cout << idx[need] << " " << i;
    idx[a[i]] = i;
}

Lưu ý quan trọng

unordered_map / unordered_set nhanh hơn map / set ( $O (1)$ vs $O (\log N)$ ) nhưng không có thứ tự.
Nếu cần duyệt theo thứ tự key, dùng map / set.
Trong C++, unordered_map có thể bị hack bằng hash collision — dùng map nếu lo ngại.

Bình luận

Không có bình luận tại thời điểm này.