Kỹ thuật Hashing (băm) là một trong những phương thức quan trọng và phổ biến nhất trong lập trình hiện đại, đặc biệt khi làm việc với dữ liệu có cấu trúc và có yêu cầu truy cập/truy vấn nhanh. Hashing là quá trình chuyển đổi dữ liệu gốc (thường là một khóa như số nguyên, chuỗi…) thành một giá trị khác gọi là hash value bằng một hàm băm (hash function). Hash value thường được dùng để truy cập/so sánh các dữ liệu nhanh hơn.
Ý tưởng cơ sở:
Khi bạn cần lưu trữ hoặc tìm kiếm dữ liệu (ví dụ như một số nguyên, chuỗi ký tự, hoặc một đối tượng bất kỳ), thay vì duyệt qua toàn bộ cấu trúc dữ liệu để so sánh từng phần tử, bạn có thể dùng hàm băm (hash function) để:
- Chuyển khóa (key) thành một giá trị băm (hash value) — thường là một số nguyên.
- Dùng hash value này để xác định trực tiếp vị trí lưu trữ hoặc vị trí tra cứu dữ liệu trong cấu trúc như bảng băm (hash table) hoặc unordered_map/unordered_set.
Nhờ vậy, việc tìm kiếm/chèn/xóa không cần phải tuần tự mà có thể “nhảy thẳng” đến vị trí tương ứng — giống như tra từ điển biết chính xác trang cần mở.
Ví dụ minh họa:
Giả sử bạn muốn lưu trữ thông tin về học sinh theo tên:
unordered_map<string, int> score; score["Alice"] = 95; score["Bob"] = 87;
Giải thích:
"Alice"là khóa (key)unordered_mapsẽ gọi một hàm băm nội bộ để chuyển"Alice"thành một số nguyên duy nhất (hash value)–> người dùng không cần quan tâm giá trị đó là gì.- Dựa vào số đó, nó xác định “vị trí” phù hợp trong bộ nhớ để lưu điểm số của Alice.
- Khi bạn gọi
score["Alice"], thư viện map thực hiện thao tác băm lại chuỗi “Alice” để được giá trị hash value tương ứng rồi sau đó tìm đến đúng vị trí trí đã lưu và truy xuất ngay lập tức điểm số của Alice.
Tất cả thao tác trên đều rất nhanh, trung bình O(1) cho thao tác truy vấn dữ liệu.
So sánh với cách truyền thống:
- Không dùng Hash: Nếu dùng vector hoặc mảng, bạn cần duyệt từng phần tử để so sánh → thời gian O(n).
- Dùng Hash: Dùng hash để tìm đúng chỗ → thời gian O(1) trung bình.
Vì vậy, hash value đóng vai trò như một “chỉ đường nhanh” [shortcut] đến dữ liệu cần xử lý — giúp lập trình hiệu quả hơn nhiều, đặc biệt khi làm việc với tập dữ liệu lớn hoặc cần xử lý nhanh trong lập trình thi đấu.
Ý nghĩa
- Tăng tốc độ truy xuất dữ liệu
Hashing cho phép tìm kiếm, chèn, và xóa dữ liệu trong thời gian trung bình O(1) — nhanh hơn rất nhiều so với các cấu trúc như mảng hay danh sách liên kết. - Giảm độ phức tạp trong giải thuật
Một số bài toán tưởng như phải xử lý theo cách “brute force” có thể tối ưu mạnh mẽ bằng cách dùng bảng băm (hash table) — giúp giảm từ O(n²) xuống O(n). - Xử lý dữ liệu không có thứ tự
Hashing hoạt động hiệu quả trên dữ liệu không sắp xếp, giúp tiết kiệm thời gian sắp xếp hoặc tìm kiếm theo cấu trúc truyền thống.
Ứng dụng trong lập trình thi đấu
Ví dụ 1: Tìm cặp số có tổng bằng K
Bài toán: Cho mảng a[] có n phần tử và số K. Hỏi có tồn tại hai phần tử a[i] + a[j] = K?
unordered_set<int> s;
bool found = false;
for (int i = 0; i < n; i++) {
if (s.count(K - a[i])) {
found = true;
break;
}
s.insert(a[i]);
}
👉 Thay vì duyệt 2 vòng for, ta dùng unordered_set để kiểm tra trong O(1), tổng thể là O(n). Cụ thể: tương ứng với mỗi a[i], ta chỉ cần kiểm tra xem “có phần tử với giá trị K – a[i] trong mảng hay không?” (s.count(K-a[i]) !=0)
Ví dụ 2: Đếm số lần xuất hiện phần tử
Khi cần đếm số lần xuất hiện của từng phần tử trong mảng (ví dụ để kiểm tra số phần tử xuất hiện nhiều hơn n/2):
unordered_map<int, int> freq; for (int x : a) freq[x]++;
👉 unordered_map giúp lưu tần suất xuất hiện chỉ trong một vòng lặp duy nhất.
Kết luận
Hashing là kỹ thuật nền tảng để xây dựng các phương thức truy vấn trên các cấu trúc dữ liệu. Trong lập trình thi đấu, nó giúp lập trình viên tối ưu thời gian, hạn chế các vòng lặp lồng nhau khi thực hiện các truy vấn, và giải quyết hiệu quả nhiều bài toán với dữ liệu lớn hoặc ràng buộc thời gian khắt khe. Việc nắm vững và vận dụng thành thạo hashing là một lợi thế lớn trong bất kỳ cuộc thi lập trình nào.