哈希

值冲突解决方法一

（了解即可）

在插入发生冲突时，往后找第一个空着的位置，将值插入；

相应的在值查询时，不仅要查询哈希函数对应的位置，还要依次比较连续的非空的哈希表中的值

const int modnum = N;
int HashTable[modnum];
int Hash(int x) { return x % modnum; }
//插入新值
void Insert(int x) {
    int addr = Hash(x);
    while (HashTable[addr] != NULL)
        addr = (addr + 1) % modnum;
    HashTable[addr] = x;
}
//查找元素
bool IsExist(int x) {
    int addr = Hash(x);
    while (HashTable[addr] != NULL) {
        if (HashTable[addr] == x)
            return true;
        addr = (addr + 1) % modnum;
    }
    return false;
}
​

值冲突解决方法二：

在每一个存哈希值的地方都开一个vector

const int modnum = 11;
vector<int>HashTable[modnum];
int Hash(int x) { return x % modnum; }
//插入新值
void Insert(int x) {
    int addr = Hash(x);
    HashTable[addr].push_back(x);
}
//查找元素
bool IsExist(int x) {
    int addr = Hash(x);
    int l = HashTable[addr].size();//每次计算size都要遍历，所以预先求出，防止在循环中重复计算增加时间复杂度
    for (int i = 0; i < l; i++) {
        if (HashTable[addr][i] == x)
            return true;
    }
    return false;
}

一般在手写哈希函数的时候，会要求Hash(x)=x%pHash(x)=x\%p中的p为素数，如9999971,9999973

字符串哈希

对于s=s1s2s3…sn,siϵa…zs=s_{1}s_{2}s_{3}…s_{n}, s_{i} \epsilon{a…z}

它的哈希函数为：

对于Hash(s)=(∑i=1nci∗basen−i)modpHash(s)=(\sum_{i=1}^{n}c_{i}*base^{n-i})modp

base是一个由你指定的数，一般是一个大于等于字符集中字符数量（cic_{i}的最大值）的素数，比如这里可以取base=31;

int Hash(char s[], int n) {
    int res = 0;
    for (int i = 1; i <= n; i++)
        res = (res * base + (s[i] - 'a')) % p;
    return res;
}

实际操作时常考虑双哈希

还可以利用类似前缀和的思想，快速得到任意一段子串的哈希值

用数组a记录下我们计算Hash(c)的中间过程，a[1]=Hash(c1),a[2]=Hash(c1c2)……a[1]=Hash(c_{1}),a[2]=Hash(c_{1}c_{2})……

即有a[i]=Hash(s1s2…sn)a[i]=Hash(s_{1}s_{2}…s_{n})

那么字符串s的任意子串sl,r=slsl+1…srs_{l,r}=s_{l}s_{l+1}…s_{r}的哈希值为：

对于Hash(sl.r)=(a[r]−a[l−1]∗baser−l+1)modpHash(s_{l.r})=(a[r]-a[l-1]*base^{r-l+1})modp

int Hash(char s[], int n) {
    int res = 0;
    for (int i = 1; i <= n; i++) {
        res = (res * base + (s[i] - 'a')) % p;
        a[i] = res;
    }
    return res;
}
​
int CalSubstringHash(int l, int r) {
    int t = a[l - 1] * pow(base, r - l + 1) % p;
    return (a[r] - t + p) % p;
}

unordered_map

$$unordered_map<K,V>hash_table

例题：小蜗的疑问

现在给你两个字符串a和b，a和b都由小写字母构成。

小蜗想知道字符串b在a中出现了几次(出现位置可以重叠)。

单哈希：

const int p = 9999971, base = 101;
int n, m, ha[200011], hb[200011], c[200011];
char a[200011], b[200011];
void solve() {
    scanf("%d%d", &n, &m);
    scanf("%s%s", a + 1, b + 1);
    c[0] = 1;
    for (int i=1; i <= 200010; i++)
        c[i] = c[i - 1] * base % p;
    for (int i = 1; i <= n; i++)
        ha[i] = (ha[i - 1] * base + a[i] - 'a') % p;
    for (int i = 1; i <= n; i++)
        hb[i] = (hb[i - 1] * base + b[i] - 'a') % p;
    int ans = 0;
    for (int i = 1; i + m - 1 <= n; i++)
        if ((ha[i + m - 1] - 1LL * ha[i - 1] * c[m] % p + p) % p == hb[m])
            ++ans;
    printf("%d", ans);
}

双哈希：

const int p = 9999971, base = 101;
const int p2 = 9999973, base2 = 137;
int n, m, ha[200011], hb[200011], c[200011], ha2[200011], hb2[200011], c2[200011];
char a[200011], b[200011];
void solve() {
    scanf("%d%d", &n, &m);
    scanf("%s%s", a + 1, b + 1);
    c[0] = 1, c2[0] = 1;
    for (int i = 1; i <= 200010; i++) {
        c[i] = c[i - 1] * base % p;
        c2[i] = c2[i - 1] * base2 % p2;
    }
    for (int i = 1; i <= n; i++) {
        ha[i] = (ha[i - 1] * base + a[i] - 'a') % p;
        ha2[i] = (ha2[i - 1] * base2 + a[i] - 'a') % p2;
    }
    for (int i = 1; i <= n; i++) {
        hb[i] = (hb[i - 1] * base + b[i] - 'a') % p;
        hb2[i] = (hb2[i - 1] * base2 + b[i] - 'a') % p2;
    }
    int ans = 0;
    for (int i = 1; i + m - 1 <= n; i++)
        if (((ha[i + m - 1] - 1LL * ha[i - 1] * c[m] % p + p) % p == hb[m])&& ((ha2[i + m - 1] - 1LL * ha2[i - 1] * c2[m] % p2 + p2) % p2 == hb2[m]))
            ++ans;
    printf("%d", ans);
}
struct StringHash {
    int n;        // 字符串长度
    char str[N];  // 下标从1开始
    const ll Base1 = 29, MOD1 = 1e9 + 7;
    const ll Base2 = 131, MOD2 = 1e9 + 9;
    ll ha1[N], ha2[N];    // 正着的哈希值
    ll rha1[N], rha2[N];  // 反着的哈希值
    ll pow1[N], pow2[N];  // Base1和Base2的乘方
​
    void init() {  // 预处理pow1[]、pow2[]
        pow1[0] = pow2[0] = 1;
        for (int i = 1; i <= n; i++) {
            pow1[i] = pow1[i - 1] * Base1 % MOD1;
            pow2[i] = pow2[i - 1] * Base2 % MOD2;
        }
    }
​
    void pre() {  // 预处理ha1[]、ha2[]
        for (int i = 1; i <= n; i++) {
            ha1[i] = (ha1[i - 1] * Base1 + str[i]) % MOD1;
            ha2[i] = (ha2[i - 1] * Base2 + str[i]) % MOD2;
            rha1[i] = (rha1[i - 1] * Base1 + str[n - i + 1]) % MOD1;
            rha2[i] = (rha2[i - 1] * Base2 + str[n - i + 1]) % MOD2;
        }
    }
​
    pair<int, int> get_hash(int l, int r) {  // 求子串str[l...r]正着的哈希值
        ll res1 = ((ha1[r] - ha1[l - 1] * pow1[r - l + 1]) % MOD1 + MOD1) % MOD1;
        ll res2 = ((ha2[r] - ha2[l - 1] * pow2[r - l + 1]) % MOD2 + MOD2) % MOD2;
        return pair<int, int>(res1, res2);
    }
​
    pair<int, int> get_rhash(int l, int r) {  // 求子串str[l...r]反着的哈希值
        ll res1 = ((rha1[n - l + 1] - rha1[n - r] * pow1[r - l + 1]) % MOD1 + MOD1) % MOD1;
        ll res2 = ((rha2[n - l + 1] - rha2[n - r] * pow2[r - l + 1]) % MOD2 + MOD2) % MOD2;
        return pair<int, int>(res1, res2);
    }
​
    bool IsPalindrome(int l, int r) {  // 判断子串str[l...r]是否是回文串
        return get_hash(l, r) == get_rhash(l, r);
    }
​
    pair<int, int> add(pair<int, int> a, pair<int, int> b) {
        ll res1 = (a.first + b.first) % MOD1;
        ll res2 = (a.second + b.second) % MOD2;
        return pair<int, int>(res1, res2);
    }
​
    pair<int, int> mul(pair<int, int>& a, ll k) {  // a *= Base的k次方
        ll res1 = a.first * pow1[k] % MOD1;
        ll res2 = a.second * pow2[k] % MOD2;
        return pair<int, int>(res1, res2);
    }
} solver;
void solve() {
    cin >> solver.str + 1;
    solver.n = strlen(solver.str + 1);
    solver.init();
    solver.pre();
    /*……*/
}

Last updated