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

什么是字符串Hash构造字符串Hash1）自然溢出方法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...

文章共5,509字 · 阅读需要大约19分钟

一键AI生成摘要，助你高效阅读

问答

Mikchy

30028人浏览 · 2020-01-15 21:11:25

Mikchy · 2020-01-15 21:11:25 发布

什么是字符串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的系数，在做差的时候将多余项消除，从而得到结果。

不难发现，对应项系数只差一个 $Base^2$ ，而4 - 2 = 2(待求hash子串下标相减即可)，这样就不难推导出来此例题的求解式子。

$hash[4] - hash[2] * Base^2$
至此，通过对上例的归纳，可以得出如下的公式。

2）公式

若已知一个 $S = s_1s_2...s_n$ 的字符串的hash值， $hash[i], 0 \leq i \leq n$ ，其子串 $s_l...s_r$ ,对应的hash值为：

$res = hash[r] - hash[l-1] * Base^{r - l + 1}$

同时，Hash值是要进行取 MOD 的：

$res = (hash[r] - hash[l-1] * Base^{r - l + 1}) \% MOD$

看起来这个式子人畜无害，但是对于取模运算要谨慎再谨慎，注意到括号里面是减法，即有可能是负数，故做如下的修正：

$res = ((hash[r] - hash[l-1] * Base^{r - l + 1}) \% MOD + MOD) \% MOD$

至此得到求子串hash值公式。

值得一提的是，如果需要反复对子串求解hash值，预处理Base的n次方效果更佳。所以才有上面用 $p[i] = (Base^i) \% MOD$ ，也是有取余数的。

具体的题目例子

1）题目链接

https://leetcode-cn.com/problems/distinct-echo-substrings/

2）题意

给你一个字符串 text ，请你返回满足下述条件的不同非空子字符串的数目：

可以写成某个字符串与其自身相连接的形式。

例如，abcabc 就是 abc 和它自身连接形成的。

示例 1：
输入：text = "abcabcabc"
输出：3
解释：3 个子字符串分别为 "abcabc" ， "bcabca" 和 "cabcab" 。
示例 2：
输入：text = "leetcodeleetcode"
输出：2
解释：2 个子字符串为 "ee" 和 "leetcodeleetcode" 。
提示：

1 <= text.length <= 2000
text 只包含小写英文字母。

3）解题分析

这道题，首先要理解题意。题目的意思是，在给定的字符串 text 中，找到满足条件的不同字串的个数。这个条件就是：字串要求前后一半的两部分是一样的。比如 abcabc，前一半是 abc，后一半是 abc，所以这个是满足条件的字串。

那么一开始的想法就是，遍历所以出现的字串情况，然后判断这个字串的前一半和后一半是不是相等。那么复杂的是：先遍历所有的字串，O(n^2)；接着每一个字串，要得到前一半字符串和后一般字符串，那就是 O(n/2 + n/2) = O(n)。所以复杂的是 O(n^3)，那么就会超时。

此时如果我们有办法，得到前一半字符串和后一般字符串，然后比较的时候，这里的查找时间如果能为 O(1)就可以了。

这个就用到了，字符串Hash。相当于用Hash，将字符串单映射为一个数字，那么我们比较某个字串是否相等，就是比较对应的Hash值是否相等。那么计算一个字串对应的Hash值，我们利用空间换时间，将查找时间变为O(1)。

当我们比较，如果某个字串的前后两部分的Hash值相等，那就说明这个字串满足条件。同时由于我们可能会会有重复出现的，因此要去重，想到用 set 来存储符合条件的字串Hash值（因为字符串和Hash值是单映射，所以存储hash值的个数就是不同字串的个数），最后输出 set 的大小即可。

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

#define ull unsigned long long   // 自然溢出用 unsigned long long
const int MAXN = 2e4 + 50;
class Solution {
public:
    unordered_set<ull> H;
    ull base = 29;
    ull hash[MAXN], p[MAXN];

    int distinctEchoSubstrings(string text) {
        int n = text.size();
        hash[0] = 0, p[0] = 1;
        for(int i = 0;i < n;i++)
            hash[i+1] = hash[i]*base + (text[i] - 'a' + 1);
        
        for(int i = 1;i < n;i++)
            p[i] = p[i-1]*base;

        for(int len = 2; len <= n; len += 2)
        {
            for(int i = 0;i + len -1 < n;i++)
            {
                int x1 = i, y1 = i + len/2 - 1;
                int x2 = i + len/2, y2 = i + len - 1;
                ull left = hash[y1 + 1] - hash[x1] * p[y1 + 1 - x1];
                ull right = hash[y2 + 1] - hash[x2] * p[y2 + 1 - x2];

                if(left == right) H.insert(left);
            }
        }
        return H.size();
    }
};

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

#define ll long long   // 单Hash，有一个取余数MOD，所以long long就得了
ll Base = 29;
ll MOD = 1e9 + 7;
const int MAXN = 2e4 + 50;

class Solution {
public:
    unordered_set<ll> H;
    ll hash[MAXN], p[MAXN];

    int distinctEchoSubstrings(string text) {
        int n = text.size();
        hash[0] = 0, p[0] = 1;
        for(int i = 0;i < n;i++)
            hash[i+1] = (hash[i]*Base + (text[i] - 'a' + 1)) % MOD;
        
        for(int i = 1;i < n;i++)
            p[i] = (p[i-1]*Base) % MOD;

        for(int len = 2; len <= n; len += 2)
        {
            for(int i = 0;i + len -1 < n;i++)
            {
                int x1 = i, y1 = i + len/2 - 1;
                int x2 = i + len/2, y2 = i + len - 1;
                ll left = ((hash[y1 + 1] - hash[x1] * p[y1 + 1 - x1]) % MOD + MOD) % MOD;
                ll right = ((hash[y2 + 1] - hash[x2] * p[y2 + 1 - x2]) % MOD + MOD) % MOD;

                if(left == right) H.insert(left);
            }
        }
        return H.size();
    }
};

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

#define ll long long   // 双Hash方法，不同的Base和MOD，相当于两次 单Hash
ll Base1 = 29;
ll Base2 = 131;
ll MOD1 = 1e9 + 7;
ll MOD2 = 1e9 + 9;
const int MAXN = 2e4 + 50;

class Solution {
public:
    set< pair <ll, ll> > H;  // 因为是一个二元组，所以可以用 pair 容器。
    ll h1[MAXN], h2[MAXN], p1[MAXN], p2[MAXN];

    int distinctEchoSubstrings(string text) {
        int n = text.size();
        h1[0] = 0, h2[0] = 0, p1[0] = 1, p2[0] = 1;
        for(int i = 0;i < n;i++)
        {
            h1[i+1] = (h1[i]*Base1 + (text[i] - 'a' + 1)) % MOD1;
            h2[i+1] = (h2[i]*Base2 + (text[i] - 'a' + 1)) % MOD2;
        }
            
        
        for(int i = 1;i < n;i++)
        {
            p1[i] = (p1[i-1]*Base1) % MOD1;
            p2[i] = (p2[i-1]*Base2) % MOD2;
        }
           

        for(int len = 2; len <= n; len += 2)
        {
            for(int i = 0;i + len -1 < n;i++)
            {
                int x1 = i, y1 = i + len/2 - 1;
                int x2 = i + len/2, y2 = i + len - 1;
                ll left1 = ((h1[y1 + 1] - h1[x1] * p1[y1 + 1 - x1]) % MOD1 + MOD1) % MOD1;
                ll right1 = ((h1[y2 + 1] - h1[x2] * p1[y2 + 1 - x2]) % MOD1 + MOD1) % MOD1;
                ll left2 = ((h2[y1 + 1] - h2[x1] * p2[y1 + 1 - x1]) % MOD2 + MOD2) % MOD2;
                ll right2 = ((h2[y2 + 1] - h2[x2] * p2[y2 + 1 - x2]) % MOD2 + MOD2) % MOD2;

                if(left1 == right1 && left2 == right2) H.insert(make_pair(left1, left2));
            }
        }
        return H.size();
    }
};

GitCode 开源社区

旨在为数千万中国开发者提供一个无缝且高效的云端环境，以支持学习、使用和贡献开源项目。

更多推荐

【目标检测】目标检测的一些常用神经网络模型及方法

我的阶段性总结????文章目录1.概述1.2 目标检测的任务1.3 目标检测的分类2.R-CNN系列2.1 [R-CNN（Region with CNN features）](https://arxiv.org/pdf/1311.2524.pdf)2.2 [Fast R-CNN](https://www.cv-foundation.org/openaccess/content_iccv_2015/