Bảng băm Hash Table: dict, unordered_map và đếm cặp tổng K

Từ tra cứu khóa đến bảng băm

Giả sử cần biết mỗi mã sản phẩm xuất hiện bao nhiêu lần. Nếu dùng mảng cặp và tìm mã bằng vòng lặp sau mỗi lượt nhập, dữ liệu lớn có thể phải xét rất nhiều cặp. Bảng băm biến một khóa thành thông tin giúp chọn vị trí lưu, từ đó chỉ xem một phần dữ liệu có liên quan thay vì duyệt hết.

Một hàm băm nhận khóa rồi tạo giá trị băm. Bộ chứa dùng giá trị này để tổ chức các ô hoặc vùng lưu. Hai khóa khác nhau vẫn có thể cho cùng giá trị băm hoặc rơi vào cùng vùng; hiện tượng đó gọi là va chạm. Bảng băm đúng không kết luận hai khóa bằng nhau chỉ vì cùng mã băm, mà còn kiểm tra quan hệ bằng nhau của khóa.

Trong C++, unordered_map<Key, Value> lưu khóa–giá trị, còn unordered_set<Key> chỉ cần biết khóa có tồn tại. Trong Python, các vai trò tương ứng là dict và set. Bài này dùng khóa số nguyên, chưa cần tự viết hàm băm hay tự quản lý các ô va chạm.

Khi nào dùng dict, khi nào dùng mảng tần suất?

Nếu khóa chỉ là các số từ 0 tới 25, mảng 26 ô thường đơn giản hơn bảng băm. Nếu khóa là số lớn, số âm hoặc xâu thay đổi, dict/map băm giúp bạn lưu những khóa thật sự xuất hiện. Mục tiêu là chọn cách lưu phù hợp miền khóa và các truy vấn cần trả lời.

Dict Python giữ thứ tự chèn, nhưng thứ tự đó không phải thứ tự sắp xếp khóa. unordered_map C++ cũng không cho một thứ tự duyệt tăng dần bảo đảm. Nếu đầu ra phải có thứ tự, sắp xếp riêng các khóa hoặc chọn cây tìm kiếm có thứ tự.

Đếm cặp có tổng bằng K

Cho dãy [1, 5, 3, 3, 5], đếm cặp chỉ số i < j có tổng bằng 6. Ba cặp là (0,1), (2,3), (0,4). Hai số 5 nằm ở hai vị trí khác nhau tạo hai cặp với số 1; vì vậy chỉ lưu “đã có số 1” là chưa đủ cho bài đếm, ta cần số lần xuất hiện.

Duyệt x từ trái qua phải. Các phần tử đứng trước đã được lưu trong freq. Mỗi lần gặp x, số cặp mới chính là freq[target - x]. Cộng số này vào đáp án, rồi tăng freq[x]. Thứ tự hai bước rất quan trọng: nếu tăng freq trước, khi target bằng hai lần x, bạn có thể ghép x với chính nó.

Với số 3 đầu tiên, phần bù 3 chưa xuất hiện nên không có cặp mới. Với số 3 thứ hai, freq[3] bằng 1, tạo đúng một cặp. Với [3,3,3], đáp án là 3, không phải 1 và cũng không phải 6. Cách duyệt chỉ ghép với các chỉ số trước giúp mỗi cặp xuất hiện đúng một lần.

Code chạy được và kết quả

#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;
// Giá trị đầu vào và target trong [-10^9, 10^9].
long long dem_cap(const vector<long long>& a,long long target) {
    unordered_map<long long,long long> freq;long long ans=0;
    freq.reserve(a.size());
    for(long long x:a) {
        auto it=freq.find(target-x);
        if(it!=freq.end())ans+=it->second;
        ++freq[x];
    }
    return ans;
}
int main(){
    int n;long long target=6;vector<long long>a={1,5,3,3,5};
    if(cin>>n>>target){a.resize(n);for(auto&x:a)cin>>x;}
    cout<<dem_cap(a,target)<<'\n';
}

def dem_cap(a,target):
    freq,ans={},0
    for x in a:
        ans+=freq.get(target-x,0)
        freq[x]=freq.get(x,0)+1
    return ans

if __name__=='__main__':
    import sys
    d=list(map(int,sys.stdin.read().split()))
    a,target=(d[2:2+d[0]],d[1]) if d else ([1,5,3,3,5],6)
    print(dem_cap(a,target))

Chạy không nhập gì, chương trình dùng ví dụ trên và in 3. Với dữ liệu riêng, nhập n và target, sau đó n số nguyên. Bản C++ dùng long long cho khóa và số cặp; ví dụ giả định các giá trị và target trong khoảng ±10⁹ để phép trừ phần bù an toàn. Số cặp có thể tăng theo n² dù thời gian xử lý kỳ vọng tuyến tính.

Code Python dùng freq.get(key, 0) để đọc tần suất mặc định mà không thêm khóa mới. Bản C++ dùng find khi tra phần bù. Ngược lại, freq[x] trong C++ sẽ tạo khóa x với giá trị ban đầu bằng 0 nếu chưa có, rồi mới tăng lên; ở bước cập nhật đó là điều ta muốn.

Thời gian trung bình và trường hợp xấu nhất

Với phân bố băm phù hợp, mỗi lượt tra và cập nhật có thời gian trung bình O(1), tổng thời gian kỳ vọng O(n), bộ nhớ O(u) với u là số khóa phân biệt. Với chuỗi, riêng việc băm hoặc so sánh khóa còn phụ thuộc độ dài chuỗi; không thể coi khóa dài tùy ý luôn tốn chi phí hằng số.

Trong trường hợp nhiều va chạm xấu, một thao tác có thể cần xét nhiều khóa, khiến tổng chi phí vượt xa O(n). reserve trong C++ giúp giảm số lần cấp phát và băm lại khi biết trước quy mô, nhưng không chứng minh loại bỏ được mọi trường hợp va chạm. Không dùng một mốc thời gian đo trên máy riêng để kết luận mọi dữ liệu đều chạy như nhau.

Với dữ liệu không đáng tin và cần cận thời gian bảo đảm, cây cân bằng có chi phí O(log n) cho các thao tác khóa thích hợp. Tuy nhiên bạn vẫn cần xét chi phí so sánh khóa. Không có cấu trúc nào nhanh nhất cho mọi loại truy vấn và mọi kiểu dữ liệu.

Những lỗi dễ gặp

Khi tự kiểm tra hàm băm vừa viết, bạn nên đối chiếu với hàm hai vòng lặp xét mọi cặp i < j trên dãy rỗng, mảng một phần tử, mảng có giá trị trùng, số âm và target âm. Trong Python, khóa của dict phải băm được; list thay đổi được không dùng trực tiếp làm khóa. Với khóa ghép, tuple của các thành phần băm được thường phù hợp hơn.

Luyện ngay trên Big-O Coding

Kiểm tra trùng lặp luyện set; bài hai chỉ số tổng target luyện lưu vị trí; gom nhóm từ đảo chữ luyện tạo khóa biểu diễn tần suất. Các yêu cầu khác nhau nên giá trị cần lưu trong bảng cũng khác.

Câu hỏi thường gặp

Nguồn tham khảo

• cppreference: std::unordered_map
• Python: Mapping Types — dict
• Open Data Structures: Hash Tables