哈希 Hash

概述

Hash （散列函数），其核心思想在于，将输入映射到一个值域较小、可以方便比较的范围。这种转换是一种压缩映射，也就是说，不同的输入可能会映射到相同的值，造成哈希碰撞。

在 OI 中我们常用哈希来比较两数据是否相同，如：字符串哈希（序列哈希），树哈希（树同构），集合哈希。还有一种以 「key-value」 形式存储数据的数据结构：哈希表。

我们通常会设计一个 Hash 函数 $F$ 将不方便比较的数据映射到整数。我们希望通过这个函数判断两个数据是否相等，具体来说，哈希函数最重要的性质可以概括为下面两条：

• 在 Hash 函数值不一样的时候，两个数据一定不一样；
• 在 Hash 函数值一样的时候，两个数据不一定一样（但有大概率一样，且我们当然希望它们总是一样的）。

字符串哈希（序列哈希）

顾名思义，就是用哈希来判断字符串（序列）是否相等。

实现

通常我们采用的是多项式 Hash 的方法，现有 一个长度为 $n$ 的字符串 $S$（下标以 $1$ 开始），我们定义哈希函数 （其中 $b,M$ 都是常数）

$$F(S)=\sum_{i=1}^{n} S[i]\times b^{n-i} \pmod{M}$$

这样设计哈希函数有一个好处：通过 $O(n)$ 的预处理，我们可以 $O(1)$ 获取 $S$ 某子串的哈希值。
具体的，我们可以预处理出 $S$ 每个前缀的哈希值，$f_i=\sum_{j=1}^i S[i]\times b^{i-j}\pmod{M}$，那么有 $f_i=f_{i-1}\times b+S[i] \pmod{M}$，还需要预处理 $b^i \pmod{M}$ 记为 $pow_i$。

对于一子串 $S[l:r]\,(1\le l\le r\le n)$ 其哈希值为

$$\begin{aligned} &\sum_{i=l}^r S[i]\times b^{r-i}\\ =&\sum_{i=1}^r S[i]\times b^{r-i} - \sum_{i=1}^{l-1}S[i]\times b^{r-i}\\ =&\sum_{i=1}^r S[i]\times b^{r-i} - b^{r-l+1}\sum_{i=1}^{l-1}S[i]\times b^{l-1-i}\\ =&f_r-pow_{r-l+1}\times f_{l-1} \end{aligned}$$

可以通过如下简短的代码实现。

const int MAX = 100000;
const int b = 2333;
const int M = 1e9+7;
typedef long long ll;
ll pw[MAX], f[MAX];
void inithash(char S[], int n) { // 预处理
    pw[0] = 1; f[0] = 0;
    for (int i = 1; i <= n; ++i) {
        f[i] = (f[i - 1] * b + S[i]) % M;
        pw[i] = pw[i - 1] * b % M;
    }
}
ll gethash(int l, int r) { // 获取 S[l : r] 的哈希值
    return (f[r] - f[l - 1] * pw[r - l + 1] % M + M) % M;
}

碰撞分析

下面讲一下如何选择 $M$ 和计算哈希碰撞的概率，以下内容摘自 OI-wiki。

这里 $M$ 需要选择一个素数（至少要比最大的字符要大），$b$ 可以任意选择。如果我们用未知数 $x$ 替代 $b$，那么 $f(s)$ 实际上是多项式环 $\mathbb{Z}_M[x]$ 上的一个多项式。考虑两个不同的字符串 $s,t$，有 $f(s)=f(t)$。我们记 $h(x)=f(s)-f(t)=\sum_{i=1}^l(s[i]-t[i])x^{l-i}\pmod M$，其中 $l=\max(|s|,|t|)$。可以发现 $h(x)$ 是一个 $l-1$ 阶的非零多项式。如果 $s$ 与 $t$ 在 $x=b$ 的情况下哈希碰撞，则 $b$ 是 $h(x)$ 的一个根。由于 $h(x)$ 在 $\mathbb{Z}_M$ 是一个域（等价于 $M$ 是一个素数，这也是为什么 $M$ 要选择素数的原因）的时候，最多有 $l-1$ 个根，如果我们保证 $b$ 是从 $[0,M)$ 之间均匀随机选取的，那么 $f(s)$ 与 $f(t)$ 碰撞的概率可以估计为 $\frac{l-1}{M}$。简单验算一下，可以发现如果两个字符串长度都是 $1$ 的时候，哈希碰撞的概率为 $\frac{1-1}{M}=0$，此时不可能发生碰撞。

若进行 $n$ 次比较，每次错误率 $\dfrac{1}{M}$，那么总错误率是 $1-\left(1-\dfrac 1 M\right)^n$。在随机数据下，若 $M=10^9+7$，$n=10^6$，错误率约为 $\dfrac 1{1000}$，并不是能够完全忽略不计的。

所以，我们使用若干大质数分别取模，这样哈希函数的值域可以扩大到这些质数的乘积。事实上在实际运用中，我们通常取两个 $10^9$ 左右的孪生质数就够了。如 $10^9+7,10^9+9$；$1019260817,1019260819$（社会主义好质数）

应用

字符串哈希主要是用来判断两字符串是否相同的工具，简单暴力，常用于骗分。下面举几个具体的例子，虽然字符串哈希可能并不是解决这些问题的最优方法，但起简单易懂，比较好实现。

字符串匹配

求出模式串哈希值，对于文本串每个长度为模式串长度的子串求哈希值，分别与模式串进行比较即可。

允许 $k$ 个位置失配的字符串匹配

问题描述：给定长度为 $n$ 的文本串 $T$，以及长度为 $m$ 的模式串 $P$，问文本串中有多少子串与 $P$ 匹配。这里匹配定义为最多 $k$ 个位置不相同。 （$1\le n,m\le 10^6,1\le k\le 5$）

该问题 KMP 算法无法解决，但可以 二分+哈希。枚举 $T$ 中每个可能匹配的子串，二分找到第一个失配的位置，忽略失配位置及之前位置，继续查找下一个位置，最多重复 $k$ 次，复杂度 $O(m+kn\log n)$

最长回文子串

一种 $O(n\log n)$ 的做法是枚举回文中心，再二分回文半径，需要分别预处理字符串正着和倒着的哈希值。

实际上，通过哈希也有 $O(n)$ 的做法，记 $r_{i}$ 表示以 $i$ 为结尾的最长回文串长度，注意到 $r_i\le r_{i-1}+2$，那么每次新枚举到一个 $i$，让 $r_i$ 由 $r_{i-1}+2$ 递减，找到第一个回文串。答案就是 $\max\{r_i\}$ 。复杂度证明：每次 $r_i$ 最多 $+2$，暴力判断一次变会 $-1$，，减小量小于等于增加量，故最多判断 $2n$ 次。

最长公共子字符串

问题描述：给定 $n$ 个总长度不超过 $m$ 的字符串，求所有字符串的最长公共子字符串，若有多个，输出任意一个。 $1\le n,m\le 10^6$。

显然若有一个长度为 $k$ 的公共子串，必然有长度为 $k-1$ 的公共子串。二分答案 $len$，考虑如何判断合法：我们只需要将每个长度为 $len$ 的串的哈希值放到哈希表里，再取交集即可。

复杂度 $O(m\log \frac{m}{n})$。

当然，你可以用 SAM/SA 在线性时间内暴切此题。（话说若字符集大小为 $10^6$ ，SAM 也要带 $\log$ ）

后缀排序

问题描述：给定一个长度为 $n$ 的字符串 $S$，将字符串的所有非空后缀按字典序排序，输出排名。

这是 SAM/SA 板题，显然有 $O(n\log n)$ ，$O(n)$ 的优秀做法。这里字符串哈希来凑个热闹，提供一个 $O(n\log ^2n)$ 的做法。

暴力排序即 string + sort ，sort 本身复杂度 $O(n\log n)$ ，string 一次比较 $O(n)$ ，所以有了 $O(n^2\log n)$ 的极高复杂度。考虑如何降低两后缀一次比较的复杂度，对于后缀 $S[i:n],S[j:n]$，二分最大的 $k$ 使 $S[i:i+k-1]=S[j:j+k-1]$ ，此时 $S[i+k]\ne S[j+k]$ ，即可通过这位比较两后缀的大小，以上判断子串相同字符串哈希足矣。

一次比较复杂度 $O(\log n)$，故总复杂度 $O(n\log^2 n)$。

线段树维护哈希值

顾名思义，就是说字符串会有修改，我们需要用线段树动态维护哈希值。

具体的，线段树每个节点维护其对应子串的哈希值，因为到时候要哈希值拼接，需要用到字符串长度，建议开结构体，重载运算符：

#define fi first
#define se second
typedef long long ll;
typedef pair<ll,ll> pll;
const int p1 = 1019260817; // 双模 hash 
const int p2 = 1019260819;
const int bs = 125641; // 基数
pll operator*(const pll &a, const ll &b) {return pll(a.fi * b % p1, a.se * b % p2);}
pll operator*(const pll &a, const pll &b) {return pll(a.fi * b.fi % p1, a.se * b.se % p2);}
pll operator+(const pll &a, const ll &b) {return pll((a.fi + b) % p1, (a.se + b) % p2);}
pll operator-(const pll &a, const pll &b) {return pll((a.fi - b.fi + p1) % p1, (a.se - b.se + p2) % p2);}
pll operator+(const pll &a, const pll &b) {return pll((a.fi + b.fi) % p1, (a.se + b.se) % p2);}
pll pw[N], pws[N]; // pw[i] = bs ^ i, pws[i] = \sum_{j=0}^i bs^j
void init(int n) {
    pw[0] = {1, 1};
    for (int i = 1; i <= n; ++i) pw[i] = pw[i - 1] * bs;
}
struct dat {
    pll f; // 哈希值
    int len; // 串长
    dat() { f = {0, 0}; len = 0; }
    dat(const pll &_f,const int &_len) { f = _f; len = _len; }
};
dat operator*(const dat &a, const dat &b) { // hash 值拼接
    return dat(a.f * pw[b.len] + b.f, a.len + b.len);
}

哈希表

哈希表是又称散列表，一种以 「key-value」 形式存储数据的数据结构。只需要输入查找的值 $key$，就可以快速地找到其对应的 value。$key$ 可以是很大的整数，浮点数，字符串甚至结构体。类似于 STL 中的 map ，不过 map 是用红黑树实现的，单次操作复杂度 $O(\log n)$ 的，而哈希表在平均情况下能在 $O(1)$ 时间内完成（但在在最坏情况下，时间复杂度为 $O(size)$ ）。

实现

在 OI 中，最常见的情况应该是 $key$ 为大整数的情况，此时不能将 $key$ 直接当作数组下标。一般把 $key$ 模一个较大的质数作为索引，也就是取 $f(x)=x \bmod M$ 作为哈希函数。若 $key$ 是字符串，一般先算出字符串的哈希值，再把其哈希值作为 $key$ 插入到哈希表里。

理想情况下，不同的 $key$ 产生不同的哈希值，假设我们用数组 $a$ 存放数据，对于一对键值 $(key,value)$，直接 $a[f(key)]=value$ 即可。但往往会有不同的 $key$ 会有相同的哈希值，此时需要处理哈希冲突。OI 中最常用的是拉链法。

拉链法

即在每个存数据的位置开一个链表，将多个 $f(key)$ 相同的 $key$ 放在对于位置的链表中，查询时将对于位置链表整个扫一遍，比较其 $key$ 与查询的 $key$ 是否一致。

闭散列法

闭散列方法把所有记录直接存储在散列表中，如果发生冲突则根据某种方式继续进行探查。
比如线性探查法：如果在 $d$ 处发生冲突，就依次检查 $d+1,d+2,\dots$；
二次探测再散列法：如果在 $d$ 处发生冲突，就依次检查 $d+1,d-1,d+4,d-4,d+9,d-9,\dots$。

代码实现

以下是拉链法的代码实现，这里的 $key,value$ 都是 long long 类型，异常操作返回 -1。

typedef long long ll;
const int M = 19260817;
const int MAX_SIZE = 2000000;
struct Hash {
    struct data {
        int nxt;
        ll key, value;
    } e[MAX_SIZE];
    int head[M], size;
    inline int f(ll key) { return key % M; } // 哈希函数
    void clear() { // 清空
        memset(head, -1, sizeof(head));
        size = 0;
    }
    ll query(ll key) { // 查询
        for (int i = head[f(key)]; i != -1; i = e[i].nxt)
            if (e[i].key == key) return e[i].value;
        return -1;
    }
    ll modify(ll key, ll value) { // 修改
        for (int i = head[f(key)]; i != -1; i = e[i].nxt)
            if (e[i].key == key) return e[i].value = value;
        return -1;
    }
    ll insert(ll key, ll value) { // 插入
        if (query(key) != -1) return -1;
        e[++size] = data{head[f(key)], key, value};
        head[f(key)] = size;
        return value;
    }
};

简单封装的模板，可以像 map 那样直接用中括号访问 「下标」。

typedef long long ll;
const int M = 19260817;
const int MAX_SIZE = 2000000;
struct Hash_map {
    struct data {
        int nxt;
        ll key, value; // (key,value) 
    } e[MAX_SIZE];
    int head[M], size;
    inline int f(ll key) { return key % M; } // 哈希函数
    ll &operator[](const ll &key) { // 重载[]
        int ky = f(key);
        for (int i = head[ky]; i != -1; i = e[i].nxt)
            if (e[i].key == key) return e[i].value;
        return e[++size] = data{head[ky], key, 0}, head[ky] = size, e[size].value;
    }
    void clear() { // 清空
        memset(head, -1, sizeof(head));
        size = 0;
    }
    Hash_map() { clear(); } // 初始化清空
};

STL 无序关联式容器

自 C++11 标准起（注意目前 CCF 的一系列赛事不支持 C++11），四种基于哈希实现的无序关联式容器正式纳入了 C++ 的标准模板库中，分别是：unordered_set，unordered_map，unordered_multiset，unordered_multimap。

常用的是前两个。 map 被卡常，又懒得手写哈希表，可以使用 unordered_map，用法与 map 差不多， 但 unordered_map 是不排序的。

自定义哈希函数

在哈希函数确定的情况下，可以构造出数据使得容器内产生大量哈希冲突，导致复杂度达到上界。标准库中的模数一般是 $126271,107897$ ，此时可以通过插入大量模数的倍数来造成大量冲突。自定义哈希函数可以有效避免构造数据产生的大量哈希冲突。

具体地，如下定义即可，需要注意 my_hash 中 x 的类型要和 unordered_map 中存储的类型对应：

struct my_hash {
    size_t operator()(int x) const { // 哈希函数，你可以修改该函数，但确保返回值是 size_t
        x += 0x2e6f39b17f9c1a51;
        x = (x ^ (x >> 30)) * 0xad5299bbe1aee5b9;
        x = (x ^ (x >> 27)) * 0x94d04f24133111eb;
        return x ^ (x >> 31);
    }
    // 提供一种 pair<int, int> 为 key 的哈希函数
    size_t operator()(pair<int, int> x) const {
        uint64_t u = (uint64_t)((x.first ^ 0xd121a3e8c6453277) << 32) | (x.second ^ 0x7c8312029eb1c5d2);
        u ^= (u >> 32);
        u ^= (u << 27);
        u ^= (u >> 31);
        return u;
    }
};
int main() {
    unordered_map<pair<int, int>, int, my_hash> mp;
    mp[make_pair(1, 2)] = 10;
    mp[make_pair(1, 3)] = 20;
    mp[make_pair(3, 4)] = 30;
    cout << "mp[(1, 3)] = " << mp[make_pair(1, 3)] << endl;
    mp.erase(make_pair(1, 3));
    cout << "size = " << mp.size() << endl;
    cout << "count (1, 3) = " << mp.count(make_pair(1, 3)) << endl;
    for (auto it = mp.begin(); it != mp.end(); ++it) {
        cout << "(" << it->first.first << ", " << it->first.second << ") = " << it->second << endl;
    }
    mp.clear();
    cout << "is_empty = " << mp.empty() << endl; 
    return 0;
}
/* 输出:
mp[(1, 3)] = 20
size = 2
count (1, 3) = 0
(3, 4) = 30
(1, 2) = 10
is_empty = 1
*/

常见的哈希

树哈希

有时我们要判断一些树是否同构，可以用恰当的哈希方式来将树映射成一个便于储存的哈希值。
若解决了有根树的树哈希，那无根树哈希也迎刃而解了：以重心为根，如果重心有两个，分别判断即可。

树哈希的方法有很多，这里只介绍两种靠谱的方法。

方法一

按照 dfs 序可以将树上结点对应到序列上，在序列上填上对应结点的深度，如上图得到序列为:

$$\begin{array}{c} 1&2&3&3&3&2&3&2 \end{array}$$

显然，根据序列可以还原出形态唯一的树，那么树哈希便转换成了序列上的哈希。具体的，需要递归处理，记 $hash(u)$ 为 $u$ 子树的哈希值，初始 $hash(u)=dep_u$ ，插入 $v$ 子树，就相当于两个序列接起来，$hash(u)'=hash(u)\times base^{siz_v}+hash(v)$ ，（ $base$ 为底数，$siz_v$ 为 $v$ 子树大小 ）。

• 如果交换子树的顺序算同构，把 $u$ 所有孩子的哈希值排序后再加入；
• 如果要判断两个不同深度的子树是否同构，把深度换成高度（到最深叶子结点的距离）。

该树哈希冲突的概率与字符串哈希是一样的。

方法二

按照以下公式：

$$f_{u}=c+\sum_{v\in son(u)} f_{v}\times prime(size_{v})$$

其中 $f_u$ 表以 $u$ 为根子树对应的哈希值，$size_v$ 表 $v$ 子树大小，$son(u)$ 为 $u$ 点孩子的集合，$prime(i)$ 为第 $i$ 个质数（也可以再 random_shuffle 一下效果更好）。$c$ 随便搞个常数。

集合哈希

集合中元素是无序的，将集合中元素排序后再序列哈希即可。若要动态维护，用平衡树维护每个元素的排名。

若全集是确定的，可以先将所有元素离散化，哈希函数定义为 $f(S)=\sum_{a\in S} b^{id(a)} \pmod{M}$ ，其中 $id(a)$ 表示 $a$ 离散化后的标号，$b$ 是个常数，$M$ 是模数。若是多重集哈希则可以 $f(S)=\sum_{a\in S} cnt(a)\times b^{id(a)} \pmod{M}$，其中 $cnt(a)$ 表 $a$ 出现次数。

例题

难度应该是递增的，直接在这里贴代码不方便，放个链接吧 例题 AC CODE

BZOJ1567

序列哈希板题.

将矩阵每行按照序列哈希预处理，一个方阵的哈希值将几行拼起来即可。枚举方阵边长，第一个矩阵的所有哈希值放入 set，另一个查找 set 中是否出现即可。

BZOJ4337

树哈希.

树的同构版题，按照 『树哈希』 中介绍的两种方法做即可。

SPOJ-LCS2 luogu

序列哈希+哈希表+二分.

即 最长公共子字符串

BZOJ3198

哈希+二项式反演.

题目让我们求『恰有』 K 个区对应相同，且容易算得『至少』K 个区对应相同，设前者为 $g_k$，后者为 $f_k$ ，显然 $f_k=\sum_{i=k}^{6} \binom{i}{k} g_i$，根据套路 $g_k=\sum_{i=k}^6 (-1)^{k-i}\binom{i}{k} f_i$。考虑如何算 $f_k$ ，枚举 $k$ 个位置，计算只考虑这 $k$ 个位置有多少对是相同的，这里需要哈希表。

HDU6647 vjudge

树哈希+换根dp+排列组合.

题目让我们求的是遍历一棵无根树产生的本质不同括号序列方案数。首先对于两个不同构的有根树，其产生的括号必然不同，考虑树哈希判同构。
先令根为 $1$，设 $f_u$ 表示遍历 $u$ 子树本质不同括号序列方案数，考虑转移，$son(u)$ 表 $u$ 孩子的集合：

$$f_u=\frac{|son(u)|!}{n_1!n_2!\dots n_k!}\prod_{v\in son(u)} f_v$$

右边所有 $f_v$ 的乘积显然，左边表示有 $|son(u)|!$ 种遍历顺序，但有的子树会同构，需要去重，$n_j$ 就表示某种子树有多少个 （$\sum_{i=1}^k n_i = |son(u)| $），相当于多重集的排列。
要求出每个点为根的本质不同括号序列方案数，换根 DP 就行了。（因为要换根所以方法一不方便，使用方法二被卡哈希的话可以看看 std）

51Nod1553 vjudge

线段树维护哈希+循环串.

首先 $S[l:r]$ 是周期为 $d$ 的循环串 $\iff$ $S[l+d:r]=S[l,r-d]$。证明显然，画个图就明白了。
题目要求区间赋值，显然线段树维护哈希，打懒标记没问题，考虑如何快速修改哈希值。显然一段长度为 $l$，都是 $a$ 的字符串哈希值为 $\sum_{i=0}^{n-1} a\times b^i= a\sum_{i=0}^{n-1} b^i$ ，预处理 $b^i$ 前缀即可。

51Nod1863 vjudge

主席树+哈希+最短路.

首先需要往最短路方向想这题。每个点的 $dis$ 可以表示成一个按排序表顺序的数量序列，第 $i$ 个元素表示优先级为 $i$ 的属性的出现次数。每经过一条边，就相当于单点加一，可以用主席树维护。
那么如何判定两个序列的大小？我们需要找到的是这两个序列的第一个不同元素。主席树上维护区间哈希值来判断区间是否相同，然后二分即可。
因为需要用主席树维护，后面的状态基于前面的，所以不能 spfa ，只能 dijkstra 。但是空间复杂度是 $O(mlogn)$ ，会 MLE 。
我们发现每一次修改的时候，由于一个点自身的属性不会变，所以每次修改这个点的时候，一定是从一个状态继承，并修改 其属性的 $rank$ 这个位置上的值，所以每次新建的节点都是一样的，所以直接覆盖到原先建出来的节点上即可，空间复杂度 $O(nlogn)$ 。堆优化 dijkstra ，时间复杂度 $O(n\log^2n)$ 。（比较大小需要一个 $\log$）

XJOI4588

备用链接1 备用链接2

字符串哈希+多重集哈希+哈希表+排列组合.

自然想到枚举 $d$（即矩阵的宽度），此时的划分方案只有 $n/d$ 种（短串只有 $n/d$ 个位置可以放 ），此时要先对这 $n/d$ 个划分去重。两个划分等价当且仅但这两划分的 $n/d$ 的字符串在排序后相同。
具体地，在一个种划分中可能会出现多个相同的串，需要哈希表统计每种串出现次数（其实就是个多重集）。对比两种划分是否等价多重集哈希可以解决。最后考虑一下一种划分的贡献，假设改划分 $s_1$ 出现了 $c_1$ 次， $s_2$ 出现了 $c_2$ 次…… $s_k$ 出现了 $c_k$ 次，其贡献为 $\dfrac{(\sum_{i=1}^k c_i)!}{c_1!c_2!\dots c_k!}$ （多重集排列数）。

UOJ522

毒瘤题.

官方题解：sol

References

• OI-wiki 哈希表
• OI-wiki 字符串哈希
• OI-wiki 无序关联式容器
• 树哈希方法二参考 树 hash
• cppreference container
• zhouzhendong’s blog