Hash

Dẫn nhập

Các bài toán về chủ đề xâu luôn là một vấn đề khó trong lập trình. Có rất nhiều các thuật toán, cấu trúc dữ liệu được tạo ra để giải quyết các bài toán về xâu. Trong số những thuật toán ấy, Hash là thuật toán được sử dụng rất phổ biến. Vậy thì Hash là gì? Hãy cùng nhau đi tìm hiểu trong bài học ngày hôm nay nhé.

---

Nội dung

Để có thể tiếp thu bài học này một cách tốt nhất, các bạn nên có những kiến thức cơ bản về:

• Các kiến thức cần thiết để theo dõi khoá học

Trong bài học ngày hôm nay, chúng ta sẽ cùng nhau tìm hiểu về:

• Một số tính chất của toán tử %
• Thuật toán Hash

---

Một số tính chất của toán tử %

Khái niệm

Trước hết, hãy nhắc lại một chút cho bạn nào đã quên về toán tử %.

Toán tử % là phép toán chia lấy phần dư. Ví dụ 5 chia 3 dư 2 thì ta có 5 % 3=2

---

Tính chất

Để có thể tiếp thu bài học, mình sẽ cần cung cấp cho các bạn một số các tính chất cơ bản của toán tử % như sau.

Với a, b,p là các số nguyên dương, ta có:

• 
• 

Ví dụ: Ta có 

Thì  và bằng với  .

Hay  và bằng với .

---

Thuật toán Hash

Bài toán đặt ra

Cho một xâu  chỉ bao gồm các chữ cái in thường, có chiều dài không vượt quá . Cho một xâu  khác có chiều dài nhỏ hơn xâu , hãy in ra các vị trí  trong xâu  sao cho xâu con đoạn (kí hiệu  là chiều dài xâu ) là xâu . Các vị trí được đánh số từ 1.

Ví dụ:

Input	Output
ababbab bab	2 5

Giải thích: Ta thấy xâu con đoạn và  của  là “bab” trùng với .

---

Ý tưởng

Ta sẽ không xử lí các xâu dưới dạng các kí tự mà ta sẽ sử dụng dạng số. Khi đó ký tự ‘a’ sẽ tương ứng với số 1, kí tự ‘b’ tương ứng với số 2, … Tức là biểu diễn các ký tự chữ bằng số thứ tự của chúng trong bảng chữ cái. Ví dụ xâu “abzc” sẽ được biểu diễn bởi dãy 4 số . Lúc này, một xâu sẽ tương ứng với một số được biểu diễn ở dạng cơ số base với .

Từ đây, ta rút ra được nhận xét: Hai xâu bằng nhau khi và chỉ khi biểu diễn số của hai xâu ở cơ số 10 là bằng nhau. Do đó, để so sánh hai xâu, ta sẽ chuyển biểu diễn của chúng từ hệ cơ số  về cơ số 10 rồi so sánh. Biểu diễn của chúng trong cơ số 10 chính là mã Hash.

Tuy nhiên, có một vấn đề ở đây. Do một xâu có tối đa  kí tự nên biểu diễn cơ số 10 của chúng là vô cùng lớn nên nếu dạng biểu diễn thập phân của xâu  là , dạng biểu diễn thập phân của xâu  là  thì ta sẽ coi  giống  “khi và chỉ khi”  với  là số nguyên tố đủ lớn.

Dễ thấy, kết luận trên là chưa chính xác do  là điều kiện cần chứ không phải điều kiện đủ để  giống . Tuy nhiên, ta chấp nhận việc này trong Hash. Trên thực tế, thuật toán Hash LUÔN LUÔN TỒN TẠI TỶ LỆ SAI. Tuy nhiên, tỉ lệ này rất thấp (cá nhân mình chưa bao giờ gặp Hash sai) và có cách giảm tỉ lệ này xuống gần như không thể.

---

Cách cài đặt

Vấn đề đầu tiên mà chúng ta cần giải quyết là biểu diễn một xâu dưới dạng cơ số 10. Nếu như các bạn đã từng làm các bài toán chuyển các số ở hệ cơ số 2, 3, 8, 16 sang hệ cơ số 10 thì vấn đề này khá đơn giản.

Giả sử ta có một xâu  có dạng biểu diễn dãy số là  với cơ số . Khi đó, mã Hash của  là:

Trong thực tế, ta sẽ không lấy giá trị đúng của phép tính trên mà ta lấy giá trị của nó sau khi chia lấy dư cho .

Vấn đề tiếp theo ta cần quan tâm là làm sao lấy ra được giá trị đoạn  trong  để tiến hành so sánh.

Giả sử ta có biểu diễn dưới dạng cơ số  của  là . Giờ để lấy mã Hash của đoạn  là  thì ta lấy mã Hash của  trừ đi mã Hash của .

Để dễ hình dung, hãy thử tưởng tượng trong hệ cơ số . Ta có một số là , giờ để thu được số , có phải ta sẽ lấy  trừ đi  hay chính là trừ đi  phải không?

Do vậy để thu được mã Hash đoạn  ta chỉ cần lấy mã Hash đoạn  trừ đi tích của mã Hash đoạn  với .

Từ đây, ta nghĩ đến việc tính trước tất cả các mã Hash của các xâu tiền tố của .

Vấn đề cuối cùng còn lại là chọn  và . Về cơ bản,  và  cần đáp ứng hai yêu cầu sau:

•  là số nguyên tố lớn hơn số lượng số ký tự cần mã hoá (mình thường chọn 257)
•  là số nguyên tố đủ lớn (mình thường chọn )

---

Code

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MOD = 1e9 + 7, BASE = 257, MaxN = 1 + 1e5;

ll hashS1[MaxN], power[MaxN];

ll getHash(int i, int j){
    return (hashS1[j] - hashS1[i - 1] * power[j - i + 1] + 1ll * MOD * MOD) % MOD;
}

int main(){
    string s1 = "ababbab", s2 = "bab";
    int n = s1.length(), m = s2.length();
    // Việc này biến chỉ số xâu từ [0, n - 1] và [0, m - 1] thành [1, n] và [1, m]
    s1 = " " + s1;
    s2 = " " + s2;
    ll hashS2 = 0;
    for(int i = 1 ; i <= m ; ++i) hashS2 = (hashS2 * BASE + (s2[i] - 'a' + 1)) % MOD;
    // power[i] là BASE^i
    power[0] = 1;
    for(int i = 1 ; i <= n ; ++i) power[i] = (power[i - 1] * BASE) % MOD;
    for(int i = 1 ; i <= n ; ++i) hashS1[i] = (hashS1[i - 1] * BASE + (s1[i] - 'a' + 1)) % MOD;
    for(int i = 1 ; i <= n - m + 1 ; ++i)
    if(getHash(i, i + m - 1) == hashS2) cout << i << " ";

    return 0;
}

---

Độ phức tạp

Ta thấy, các phép tính trong code trên đều diễn ra trong  nên độ phức tạp chương trình chính là .

---

Mở rộng

Như mình đã nói ở trên, Hash luôn có cơ hội sai dù tỉ lệ này là rất nhỏ. Nếu như test được sinh hoàn toàn ngẫu nhiên thì gần như không thể sai được. Tuy nhiên, nếu như người ra đề cố tính “giết Hash” thì họ sẽ nghĩ ra được các test sai. Do đó, để đảm bảo chắc chắn hơn, các bạn có thể tính mã Hash với 2 cơ số  và 2 số dư  khác nhau. Khi này, gần như là không thể có cách “giết Hash”.

---

Kết luận

• Qua bài này chúng ta đã nắm được về Hash.
• Bài sau chúng ta sẽ quay trở lại tìm hiểu về cấu trúc dữ liệu với bài Đồ thị và cây.
• Cảm ơn các bạn đã theo dõi bài viết. Hãy để lại bình luận hoặc góp ý của mình để phát triển bài viết tốt hơn. Đừng quên “Luyện tập – Thử thách – Không ngại khó”.

---

Thảo luận

Nếu bạn có bất kỳ khó khăn hay thắc mắc gì về khóa học, đừng ngần ngại đặt câu hỏi trong phần BÌNH LUẬN bên dưới hoặc trong mục HỎI & ĐÁP trên thư viện Howkteam.com để nhận được sự hỗ trợ từ cộng đồng.