DeMen Blog #1: “Bàn về Hash: Khi Hash không chỉ là so sánh hai xâu.”

    Tác giả: Võ Khắc Triệu (DeMen100ns)

    Hash là một thuật toán để so sánh hai xâu trong O(1) với độ sai rất nhỏ. Không, Hash không phải như thế này.

    0. Vậy rốt cuộc Hash là gì?

    Wikipedia định nghĩa hàm băm (Hash function) như sau:

    A hash function is any function that can be used to map data of arbitrary size to fixed-size values.

    Tạm dịch: Hàm băm (Hash function) là một hàm ánh xạ, trong đó một giá trị sẽ được biểu diễn bằng một giá trị hash nằm trong một khoảng giá trị cố định.

    Ví dụ về hash function (Nguồn: Wikipedia)

    Mục đích của việc hash là để giảm chi phí hay độ phức tạp cho việc so sánh hai giá trị cụ thể nào đó. Tuy nhiên, có thể sẽ có một số cặp giá trị khác nhau có cùng giá trị hash giống nhau và chúng ta chấp nhận việc này như một lỗi, đồng thời cố gắng tạo ra hàm hash để giảm xác suất xảy ra lỗi.

    Tính chất:

    • Nếu hai biến có giá trị giống nhau thì sẽ có giá trị hash giống nhau.
    • Nếu hai biến có giá trị hash giống nhau thì khả năng cao sẽ có giá trị giống nhau (Phụ thuộc vào hàm hash).

    Với thuật toán dùng để so sánh 2 xâu giống nhau, tên đầy đủ của thuật toán là Rolling Hash với việc lấy số dư của các hàm đa thức cho một số MM lớn (thường là nguyên tố) để tính ra giá trị hash.

    Tuy nhiên, đây không phải là hàm hash duy nhất. Trên thực tế, có rất nhiều hàm hash khác nhau, mỗi hàm đều có một hoặc một vài ứng dụng khác nhau.

    Trong bài viết này, chúng ta sẽ bàn về một số các hàm hash khác và các ứng dụng của nó.

    1. XOR Hashing

    Ý tưởng

    Trước khi đọc tiếp, các bạn có thể tìm hiểu về phép toán tử bitwise XOR tại đây

    Ta tạo một hàm hash H()H(), với mỗi giá trị xx thì H(x)H(x) tương ứng với một số k−bitk-\text{bit} ngẫu nhiên (thường là 64−bit64-\text{bit} hoặc 128−bit128-\text{bit}).

    Xét một tập AA gồm chứa kk phần tử. Ta gọi giá trị Hash XOR của tập AA hay HXOR(A)H_{XOR}(A) là tổng XOR của giá trị hash của các phần tử trong tập, hay: HXOR(A)=H(A1)⊕H(A2)⊕⋯⊕H(Ak)H_{XOR}(A) = H(A_1) \oplus H(A_2) \oplus \dots \oplus H(A_k)

    Thao tác XOR các giá trị hash của các phần tử trong một tập được gọi là XOR Hashing.

    Ta sẽ xét một bài toán đơn giản để hiểu về cách XOR Hashing hoạt động.

    Bài toán

    Xét mảng aa gồm nn phần tử, trả lời qq truy vấn sau:

    • l rl\ r: Cho biết tất cả các giá trị từ 11 đến r−l+1r - l + 1 có xuất hiện trong đoạn [l..r][l .. r] của mảng aa không?

    Giới hạn: 1≤n,q,ai≤1061 \le n, q, a_i \le 10^6

    Ta thấy, trong bài toán này, thứ tự của các vị trí không quan trọng, chỉ có tập các giá trị của đoạn mới quan trọng. Như vậy, với mỗi truy vấn l rl\ r ta sẽ kiểm tra xem tập {al,al+1,…,ar}\{a_l, a_{l + 1}, \dots, a_r\} có giống với tập {1,2,…,r−l+1}\{1, 2, \dots, r - l + 1\} hay không.

    Lời giải

    Giả sử {al,al+1,…,ar}\{a_l, a_{l + 1}, \dots, a_r\} và {1,2,…,r−l+1}\{1, 2, \dots, r - l + 1\} là hai tập giống nhau. Khi này ta có:

    HXOR({al,al+1,…,ar})=HXOR({1,2,…,r−l+1})H_{XOR}(\{a_l, a_{l + 1}, \dots, a_r\}) = H_{XOR}(\{1, 2, \dots, r - l + 1\})

    ⇔H(al)⊕H(al+1)⊕⋯⊕H(ar)=H(1)⊕H(2)⊕⋯⊕H(r−l+1)(∗)\Leftrightarrow H(a_l) \oplus H(a_{l + 1}) \oplus \dots \oplus H(a_r) = H(1) \oplus H(2) \oplus \dots \oplus H(r - l + 1) (*)

    Với ⊕\oplus là phép bitwise XOR.

    Khi này, ta chỉ cần kiểm tra điều kiện (∗)(*) có thỏa hay không là được.

    Ngạc nhiên thay, điều kiện nhìn tưởng chừng dễ sai này lại đúng một cách khó tin. Hãy cùng thử chứng minh lời giải này nhé.

    Tính chất

    Xét hai tập AA và BB độ dài nn. Vì XOR là một phép toán có tính chất giao hoán nên nếu AA và BB có cùng tập các phần tử thì:

    H(A1)⊕H(A2)⊕⋯⊕H(An)=H(B1)⊕H(B2)⊕⋯⊕H(Bn)H(A_1) \oplus H(A_2) \oplus \dots \oplus H(A_n) = H(B_1) \oplus H(B_2) \oplus \dots \oplus H(B_n)

    ⇔HXOR(A)=HXOR(B)\Leftrightarrow H_{XOR}(A) = H_{XOR}(B)

    Với tính chất trên, ta thấy được nếu hai tập AA và BB có cùng tập giá trị thì giá trị Hash XOR của hai tập sẽ bằng nhau.

    Xác suất sai

    Khi hai tập AA và BB khác nhau, ta chứng minh được xác suất trùng hash của hai tập sẽ là 12k\frac{1}{2^k}, một xác suất rất bé khi kk đủ lớn. Thật vậy, ta chứng minh như sau:

    Với mỗi bit giá trị, có 50%50\% khả năng bit đó sẽ là 00 và 50%50\% bit đó sẽ là 11. Tổng XOR của một dãy bit như vậy cũng sẽ có 50%50\% khả năng bit đó sẽ là 00 và 50%50\% bit đó sẽ là 11.

    Trở lại bài toán, vì về phải của (∗)(*) là một số k−bitk-\text{bit} cố định và vế trái của (∗)(*) là một số k−bitk-\text{bit} ngẫu nhiên nên xác suất hai vế bằng nhau trong trường hợp tập AA và BB khác nhau sẽ là 50%k50\%^k hay 12k\frac{1}{2^k}.

    Cài đặt

    #include <bits/stdc++.h>
    

    using namespace std;
    

    const int N = 1e6 + 5;
    const int MAXA = 1e6;
    

    mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
    

    long long a[N], HXOR[N];
    long long pre[N], pre_a[N];
    

    signed main(){
        ios_base::sync_with_stdio(0);
        cin.tie(0);
    

        int n, q; cin >> n >> q;
        for(int i = 1; i <= n; ++i){
            cin >> a[i];
        }
    

        for(int i = 1; i <= MAXA; ++i){
            HXOR[i] = rng();
        }
    

        for(int i = 1; i <= n; ++i){
            pre[i] = pre[i - 1] ^ HXOR[i];
            pre_a[i] = pre_a[i - 1] ^ HXOR[a[i]];
        }
    

        while (q--){
            int l, r; cin >> l >> r;
            if (pre[r - l + 1] == (pre_a[l - 1] ^ pre_a[r])){
                cout << "YES" << '\n';
            } else {
                cout << "NO" << '\n';
            }
        }
    }

    Ứng dụng

    Ưu điểm lớn nhất XOR Hashing là có thể tạo ra một khoảng giá trị hash rất lớn (thường tới 2642^{64} hay 21282^{128}) và giá trị Hash XOR được rải đều nên khả năng sai là rất thấp và rất dễ cài đặt.

    XOR Hashing thường có hai ứng dụng chính:

    • Kiểm tra các giá trị trong hai tập khác nhau có cùng số lần lặp lại modulo 2modulo\ 2 hay không.
    • Các bài toán liên quan đến phép bitwise XOR.

    Mở rộng

    XOR Hashing thường sẽ gặp vấn đề khi giải các bài toán có các giá trị bị lặp lại do tính chất a⊕a=0a \oplus a = 0. Mở rộng ra một chút, ta có thể dùng k$$-$$nary XOR (phép XOR trên hệ cơ số kk) để xử lý các bài toán với các giá trị bị lặp lại không quá k−1k - 1 lần.

    2. Sum Hashing

    Ý tưởng

    Tương tự với XOR Hashing, ta tạo một hàm hash H()H(), với mỗi giá trị xx thì H(x)H(x) tương ứng với một số ngẫu nhiên.

    Xét tập AA gồm một số giá trị (có thể lặp lại). Ta gọi giá trị Hash Sum của tập AA hay HSUM(A)H_{SUM}(A) là tổng của giá trị hash của các phần tử trong tập, hay: HSUM(A)=∑i∈AH(i)H_{SUM}(A) = \sum_{i \in A} H(i)

    Thao tác cộng các giá trị hash của các phần tử trong một tập được gọi là Sum Hashing.

    Ta cũng sẽ xét một bài toán đơn giản để hiểu về cách Sum Hashing hoạt động.

    Bài toán

    Xét mảng aa gồm nn phần tử, thực hiện qq truy vấn có dạng sau:

    • l r k:l\ r\ k: Cho biết mỗi giá trị trong đoạn l..rl .. r của mảng aa có lặp lại số lần là bội số của kk hay không.

    Giới hạn: 1≤n,q,ai≤106,2≤k≤n1 \le n, q, a_i \le 10^6, 2 \le k \le n.

    Lời giải

    Với bài toán này thì XOR Hashing không phải một ý tưởng tốt vì tính lặp lại của giá trị và kk có thể rất lớn.

    Tuy nhiên, ta có thể tận dụng tính chất sau:

    Tính chất

    Nếu mỗi giá trị trong đoạn l..rl .. r của mảng aa có lặp lại số lần là bội số của kk thì HSUM({al,al+1,…,ar})≡0(modk) (∗∗)H_{SUM}(\{a_l, a_{l + 1}, \dots, a_r\}) \equiv 0 \pmod k\ (**)

    Như vậy, ta có thể sử dụng Sum Hashing để kiểm tra điều kiện (∗∗)(**) có thỏa hay không.

    Xác suất sai

    Dễ thấy xác suất sai đạt lớn nhất khi k=2k = 2.

    Giả sử tồn tại giá trị trong đoạn l..rl .. r của mảng aa lặp lại số lần không phải là bội số của kk thì xác suất để điều kiện (∗∗)(**) thỏa là 12\frac{1}{2}.

    Xác suất sai lúc này còn khá lớn, tuy nhiên ta có thể tạo ra tt hàm hash khác nhau và kiểm tra điều kiện cho tất cả chúng.

    Xác suất sai khi sử dụng tt hàm hash khác nhau sẽ là 12t\frac{1}{2^t}, với t≥50t \ge 50 sẽ đủ tốt.

    Cài đặt

    #include <bits/stdc++.h>
    

    using namespace std;
    

    const int N = 1e6 + 5;
    const int MAXA = 1e6;
    

    mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
    

    long long a[N], H[51][N];
    long long pre[51][N];
    

    signed main()
    {
        ios_base::sync_with_stdio(0);
        cin.tie(0);
    

        int n, q; cin >> n >> q;
        for(int i = 1; i <= n; ++i){
            cin >> a[i];
        }
    

        for(int t = 1; t <= 50; ++t){
            for(int i = 1; i <= MAXA; ++i){
                H[t][i] = rng() % (long long)(1e12);
            }
            for(int i = 1; i <= n; ++i){
                pre[t][i] = pre[t][i - 1] + H[t][a[i]];
            }
        }
    

        while (q--){
            int l, r, k; cin >> l >> r >> k;
    

            bool f = true;
            for(int t = 1; t <= 50; ++t){
                f &= ((pre[t][r] - pre[t][l - 1]) % k == 0);
            }
    

            if (f){
                cout << "YES" << '\n';
            } else{
                cout << "NO" << '\n';
            }
        }
    }

    Ứng dụng

    Hiển nhiên, với hai tập AA và BB giống nhau thì: HSUM(A)=HSUM(B)H_{SUM}(A) = H_{SUM}(B)

    Ta có thể sử dụng tính chất này để so sánh hai tập mà không bị ràng buộc điều kiện như XOR Hashing. Tuy vậy, ta vẫn có thể kết hợp thêm XOR Hashing như một điều kiện phụ để giảm xác suất sai của thuật toán.

    3. Modulo Hashing

    Ý tưởng

    Xét một giá trị AA rất lớn nào đó. Ta có thể biểu diễn AA bằng số dư của nó khi chia cho một giá trị MM nào đó mà vẫn đảm bảo được các tính của giá trị gốc, hay: H(A)≡A (mod M)H(A) \equiv A\ (mod\ M)

    Xét bài toán sau:

    Bài toán

    Hãy cho biết A=BA = B hay không, biết rằng A=p1×p2×⋯×pnA = p_1 \times p_2 \times \dots \times p_n và B=q1×q2×⋯×qmB = q_1 \times q_2 \times \dots \times q_m.

    Giới hạn: 1≤n,m≤105,2≤pi,qi≤1091 \le n, m \le 10^5, 2 \le p_i, q_i \le 10^9

    Lời giải

    Trong bài toán này, việc tính trực tiếp A,BA, B sẽ tốn chi phí rất lớn và cài đặt rất khó do việc phải dùng Bignum.

    Tuy nhiên, ta có thể sử dụng Modulo Hashing, trong đó, nếu A=BA = B thì:

    H(A)=H(B)H(A) = H(B)

    ⇔A≡B (mod M)\Leftrightarrow A \equiv B\ (mod\ M)

    Ta có thể tính H(A)H(A) và H(B)H(B) một cách dễ dàng.

    Xác suất sai

    Dễ thấy, nếu A≠BA \neq B thì khả năng H(A)=H(B)H(A) = H(B) sẽ là 1M\frac{1}{M}.

    Với MM đủ lớn (M>109)(M > 10^9) thì xác suất sai sẽ trở nên rất nhỏ.

    Cài đặt

    #include <bits/stdc++.h>
    

    using namespace std;
    

    const int MOD = 1e9 + 9;
    

    signed main()
    {
        ios_base::sync_with_stdio(0);
        cin.tie(0);
    

        int HA = 0, HB = 0;
        int n, m; cin >> n >> m;
    

        for(int i = 1; i <= n; ++i){
            int pi; cin >> pi;
            HA = (HA * 1LL * pi) % MOD;
        }
    

        for(int i = 1; i <= m; ++i){
            int qi; cin >> qi;
            HB = (HB * 1LL * qi) % MOD;
        }
    

        if (HA == HB){
            cout << "YES";
        } else {
            cout << "NO";
        }
    }

    Ứng dụng

    Ứng dụng chính của Modulo Hashing là việc so sánh bằng nhau giữa hai số rất lớn (có thể lên tới 1010610^{10^6} hoặc lớn hơn), với mỗi số được tính bằng một dãy các phép tính của các số nguyên nhỏ hơn (thường là 32−bit32-\text{bit} hoặc 64−bit64-\text{bit}). Ví dụ điển hình của ứng dụng này chính Rolling Hash.

    Chọn số mod phù hợp

    • Số mod nên là số nguyên tố.
    • Các bạn có thể kết hợp sử dụng nhiều số mod.

    Các bạn có thể xem thêm tại bài viết này của rng_58.

    4. Hash nhà làm

    Tóm lại, bản chất của hash chính là một hàm ánh xạ. Với từng bài toán, các bạn có thể tự tạo ra hàm hash phù hợp để giải quyết bài toán đó. Hàm hash cần phải đảm bảo tính chất ánh xạ và có xác suất sai đủ thấp (chứng minh hoặc thực nghiệm). Ngoài ra ta có thể kết hợp nhiều hàm hash với nhau để giảm xác suất sai xuống.

    Bài tập

    Tài liệu tham khảo

    Author: Võ Khắc Triệu (DeMen100ns) @ DeMen100ns's Blog

    Permalink: https://demen100ns.github.io/blog/2026-07-12-demen-blog-1-hash/

    Title: DeMen Blog #1: "Bàn về Hash: Khi Hash không chỉ là so sánh hai xâu."

    License: All articles on this blog are licensed under the BY-NC-SA license agreement unless otherwise stated. Please indicate the source when reprinting!

    backtop