【算法学习】字符串哈希（Hash）

您所在的位置：网站首页 › java的哈希值是什么 › 【算法学习】字符串哈希（Hash）

【算法学习】字符串哈希（Hash）

2024-07-16 02:40| 来源: 网络整理| 查看: 265

什么是字符串Hash

构造字符串Hash

1）自然溢出方法

2）单Hash方法

3）双Hash方法

4）三种不同的构造方法的对比

获取子串的Hash O(1)

1）例子

2）公式

具体的题目例子

1）题目链接

2）题意

3）解题分析

4）AC代码（自然溢出 C++）

5）AC代码（单Hash C++）

6）AC代码（双Hash C++）

什么是字符串Hash

hash，其实就是将一个东西映射成另一个东西，类似Map，key对应value。

那么字符串Hash，其实就是：构造一个数字使之唯一代表一个字符串。但是为了将映射关系进行一一对应，也就是，一个字符串对应一个数字，那么一个数字也对应一个字符串。

用字符串Hash的目的是，我们如果要比较一个字符串，我们不直接比较字符串，而是比较它对应映射的数字，这样子就知道两个“子串”是否相等。从而达到，子串的Hash值的时间为 O(1)，进而可以利用“空间换时间”来节省时间复杂的。

我们希望这个映射是一个单射，所以问题就是如何构造这个Hash函数，使得他们成为一个单射。不用担心，接下来的内容正要讲解。

构造字符串Hash

假如给你一个数字1166，形式上你只知道它只是1和6的组合，但你知道它代表的实际大1*10^3+1*10^2+6*10^1+6*10^0。

同理，给你一个字符串，要把它转换为数字，就可以先把每一个字符都先对应一个数字，然后把它们按照顺序乘以进制（Base）的幂进行相加，然后这个数可能很大，所以一般会取余数（MOD）。

根据上面的理解，其实将字符串映射成数字，和我们平时的将一个某Base进制数，变为一个十进制数，相类似。

我们先定义以下：

给定一个字符串 $S = s_1s_2s_3...s_n$ ，对于每一个 $s_i$ 就是一个字母，那么我们规定 $idx(s_i) = s_i - 'a' + 1$ 。（当然也可以直接用其ASCII值）

构造字符串Hash总共有三种方法。每一种方法，主要都是用使用 Base 和 MOD（都要求是素数），一般都是 Base < MOD，同时将Base和MOD尽量取大即可，这种情况下，冲突（即不同字符串却有着相同的hash值）的概率是很低的。

1）自然溢出方法

对于自然溢出方法，我们定义 Base ，而MOD对于自然溢出方法，就是 unsigned long long 整数的自然溢出（相当于MOD 是 $2^{64} - 1$ ）

#define ull unsigned long long ull Base; ull hash[MAXN], p[MAXN]; hash[0] = 0; p[0] = 1;

定义了上面的两个数组，首先 $hash[i]$ 表示 $[0, i]$ 字串的hash 值。而 $p[i]$ 表示 $Base ^ i$ ，也就是底的 $i$ 次方。

那么对应的 Hash 公式为：

$hash[i] = hash[i-1] * Base + idx(s[i])$

(类似十进制的表示，14，一开始是 0，然后 0 * 10 + 1 = 1，接着 1*10 + 4 = 14)。

2）单Hash方法

同样的，定义了 Base 和 MOD，有了对应的要求余 MOD。所以一般用 long long 就可以了。

#define ll long long ll Base; ll hash[MAXN], p[MAXN]; hash[0] = 0; p[0] = 1;

定义了上面的两个数组，首先 $hash[i]$ 表示前 i 个字符的字串的hash 值。而 $p[i]$ 表示 $Base ^ i$ ，也就是底的 $i$ 次方。

那么对应的 Hash 公式为：

$hash[i] = (hash[i-1] * Base + idx(s[i])) \% MOD$

对于此种Hash方法，将Base和MOD尽量取大即可，这种情况下，冲突的概率是很低的。

举例

如取Base = 13，MOD=101，对字符串abc进行Hash hash[0] = 0 (相当于 0 字串) hash[1] = (hash[0] * 13 + 1) % 101 = 1 hash[2] = (hash[1] * 13 + 2) % 101 = 15 hash[3] = (hash[2] * 13 + 3) % 101 = 97

这样，我们就认为字符串abc当做97，即97就是abc 的hash值。

3）双Hash方法

用字符串Hash，最怕的就是，出现冲突的情况，即不同字符串却有着相同的hash值，这是我们不想看到的。所以为了降低冲突的概率，可以用双Hash方法。

将一个字符串用不同的Base和MOD，hash两次，将这两个结果用一个二元组表示，作为一个总的Hash结果。

相当于我们用不同的Base和MOD，进行两次单Hash方法操作，然后将得到的结果，变成一个二元组结果，这样子，我们要看一个字符串，就要同时对比两个 Hash 值，这样子出现冲突的概率就很低了。

那么对应的 Hash 公式为：

$hash1[i] = (hash1[i-1] * Base1 + idx(s[i])) \% MOD1$

$hash2[i] = (hash2[i-1] * Base2 + idx(s[i])) \% MOD2$

映射的Hash结果为： $hash1[i], hash2[i]$

这种Hash很安全。

4）三种不同的构造方法的对比其实，自然溢出方法，说到底就是单Hash方法，只是把MOD变成了自动溢出，也就是 $MOD = 2^{64} - 1$ 从速度上来看，应该是：自然溢出 > 单Hash > 双Hash。（也就是自然溢出时间更小）。从安全性上来看，应该：双Hash方法 > 单Hash方法。因为双Hash方法相当于是用两次单 Hash的结果来比较，这样子冲突的概率会变得更低。

获取子串的Hash O(1)

上面我们得到的 Hash值都是前 i 个字符的字串，那么如果我们想获取 $[l,r]$ 范围中的字串的Hash值，应该如何做。（利用Hash值，我们可以O(1) 时间来获取某个字串。）

我们先以一个具体的例子来理解。

1）例子

假设有一个 $S = s_1s_2s_3s_4s_5$ 的字符串，根据定义，获取其 Hash值如下（我们先忽略MOD，方便理解）：

$hash[0] = 0$

$hash[1] = s_1$

$hash[2] = s_1 * Base + s2$

$hash[3] = s_1 * Base^2 + s2 * Base + s_3$

$hash[4] = s_1 * Base^3 + s2 * Base^2 + s_3 * Base + s_4$

$hash[5] = s_1 * Base^4 + s2 * Base^3 + s_3 * Base^2 + s_4 * Base + s_5$

现在我们想求字串 $s_3s_4$ 的hash值，不难得出为 $s_3 * Base + s4$ ，并且从上面观察，如果看 $hash[4] - hash[2]$ 并将结果种带有s1,s2系数的项全部消掉，就是所求。但是由于Base的阶数，不能直接消掉，所以问题就转化成，将 $hash[2]$ 乘一个关于Base的系数，在做差的时候将多余项消除，从而得到结果。