【筆記】Hash

Posted on: | By:
  • 【用途】加密、判斷字串相同、樹同構、陣列內容相等。
  • 【做法】
    • 資料經過運算 (hash function) 對應到某個整數
    • 一樣的資料經過相同的hash運算，會對應到相同的整數
    • 無法輕易從hash值回推出原始資料
    • 要避免 hash 碰撞 (collision)
  • 【實作】Rolling Hash
    • 定義兩個質數，一小一大
    • mul：小質數，例如 37
    • mod：大質數，例如 1e9 + 7
    • Hash = 0; Hash *= mul; Hash += i; Hash %= mod;

【例1】對陣列內容進行hash

  • a[ ] = {1, 2, 3, 4, 5} –> {1, 39, 1446, 53506, 1979727}
  • 1 = ( 1 ) % 10000007
  • 39 = ( 1 * 37 + 2 ) % 10000007
  • 1446 = ( 1 * 37^2 + 2 * 37 + 3 ) % 10000007
//【例1】對陣列內容進行hash
#include <iostream>
using namespace std;
const int mul = 37, mod = 1e9 + 7;

int main() {
    int a[] = {1, 2, 3, 4, 5};
    long long Hash = 0;
    for (auto i: a){
        Hash *= mul;
        Hash += i;
        Hash %= mod;
        cout << Hash << ' ';
    }
    return 0;
}

【例2】對字串進行hash

  • s = “abcde” –> {97, 3687, 136518, 5051266, 186896943}
//【例2】對字串進行hash
#include <iostream>
using namespace std;
const int mul = 37, mod = 1e9 + 7;

int main() {
    string s = "abcde";
    long long Hash = 0;
    for (auto i: s){
        Hash *= mul;
        Hash += (int) i; //轉成 ASCII code
        Hash %= mod;
        cout << Hash << ' ';
    }
    return 0;
}

【例3】對樹進行hash (搭配 DFS)

  • 下圖例的兩棵樹的 hash 都是 2813。 亦即兩棵樹同構。
  • (Line-16) 要先排序
//【例3】對樹進行hash (搭配 DFS)
#include <iostream>
#include <vector>
using namespace std;
const int mul = 37, mod = 1e9 + 7;
const int maxn = 10;
vector <int> g[maxn];

int dfs(int now, int pre){
    vector <int> v;
    for (auto i: g[now]){
        if(i != pre){
            v.push_back(dfs(i, now));
        }
    }
    sort(v.rbegin(), v.rend()); //由大排到小，避免碰撞
    long long ret = 1; //如果是葉節點，會回傳 1
    for (auto i: v){
        ret *= mul;
        ret += i;
        ret %= mod;
    }
    return ret;
}

int main() {
    int n, a, b;
    cin >> n;
    for (int i=0; i<n-1; i++){
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    cout << dfs(0, -1) << endl;
    for (int i=0; i<n; i++){
        g[i].clear();
    }
    for (int i=0; i<n-1; i++){
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    cout << dfs(5, -1) << endl;
    return 0;
}

【例4】子字串 hash

  • 對一個字串，多次查詢子字串的 hash 值
  • 先計算每個 prefix hash 的結果，在進行 rolling hash 時順便紀錄。接著利用這些 prefix 的結果，湊出需要的 substring。
  • 時間複雜度：
    • 建表 (預處理)：O(n)
    • 查詢：O(1)
  • 【EX】s = “abcdefg”
  • pre[ ]：prefix hash 的結果
    • pre[0] = 0
    • pre[1] = (pre[0] + ‘a’) % mod
    • pre[2] = (pre[1]* mul + ‘b’) % mod
    • pre[3] = (pre[2]* mul + ‘c’) % mod
    • pre[4] = (pre[3]* mul + ‘d’) % mod
    • pre[5] = (pre[4]* mul + ‘e’) % mod
  • substring [l, r] hash值：
    • pre[r] – pre[l – 1] * (mul^(r – l + 1))
  • Example: “cd” (3~4) hash值
    • l = 3, r = 4
    • pre[4] = a * mul^3 + b * mul^2 + c * mul + d
    • pre[3-1] = pre[2] = a * mul + b
    • pre[2] * mul^2 = a * mul^3 + b * mul^2
    • pre[4] – pre[2] * mul^2 = c * mul + d
//【例4】子字串 hash
#include <iostream>
#include <vector>
using namespace std;
const int mul = 37, mod = 1e9 + 7;
int pre[10];

int query(int l, int r){
    long long ret = pre[l-1];
    for (int i=0; i<r-l+1; i++){
        ret *= mul;
        ret %= mod;
    }
    return pre[r] - ret;
}

int main() {
    string s = "abcdefg";
    pre[0] = 0;
    long long Hash = pre[0];
    for (int i=1; i<=s.size(); i++){
        Hash *= mul;
        Hash += s[i-1] - 'a' + 1;
        Hash %= mod;
        pre[i] = Hash;
    }
    for (int i=0; i<=s.size(); i++){
        cout << i << " : " << pre[i] << endl;
    }
    cout << query(3, 3) << endl;
    cout << query(4, 4) << endl;
    cout << query(5, 5) << endl;
    cout << query(3, 4) << endl;
    cout << query(3, 5) << endl;
    return 0;
}

Post Views (since April 2021) : 1,180
分享本文 Share with friends