哈希

在介绍 Hash 算法之前，首先你需要了解关于 字符串匹配 的事情。

Hash 的思想

Hash 的核心思想在于，暴力算法中，单次比较的时间太长了，应当如何才能缩短一些呢？

如果要求每次只能比较 O(1) 个字符，应该怎样操作呢？

是比较第一个？最后一个？随便选一个？求所有字符的和？

我们定义一个把 string 映射成 int 的函数 f ，这个 f 称为是 Hash 函数。

我们希望这个函数 f 可以方便地帮我们判断两个字符串是否相等。

具体来说，我们希望在 Hash 函数值不一样的时候，两个字符串一定不一样。

另外，反过来不需要成立。我们把这种条件称为是单侧错误。

我们需要关注的是什么？

时间复杂度和 Hash 的准确率。

通常我们采用的是多项式 Hash 的方法，即 \operatorname{f}(s) = \sum s[i] \times b^i \pmod M

这里面的 b 和 M 需要选取得足够合适才行，以使得 Hash 的冲突尽量均匀。

如果 b 和 M 互质，在输入随机的情况下，这个 Hash 函数在 [0,M) 上每个值概率相等

此时错误率为 \frac1M （单次比较）

在输入不是随机的情况下，效果也很好。

Hash 的实现

伪代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
match_pre(int n) {
    exp[0] = 1;
    for (i = 1; i < n; i++) {
        exp[i] = exp[i - 1] * b % M;
    }
}

match(char *a, char *b, int n, int m) {
    // match 函数返回：长度为 m 的串 b 在长度为 n 的串 a 中的匹配位置
    // hash(a, m) 函数用来获得某个字符串前 m 个字符的部分的 hash 值
    ans = new vector();
    int ha = hash(a, m);
    int hb = hash(b, m);
    for (i = 0; i < n - m + 1; i++) {
        if ((ha - hb * exp[i]) % M == 0) {
            ans.push_back(i);
        }
        ha = (ha - a[i] * exp[i] + a[i + m] * exp[i + m]) % M;
    }
    return ans;
}

通过上面这段代码，可以发现，每次直接计算 Hash 是 O(串长) 的

Hash 的分析与改进

改进时间复杂度或者错误率

在上述例子中，时间复杂度已经是 O(n+m)

我们来分析错误率

由于 n >> m ，要进行约 n 次比较，每次错误率 \frac1{M} ，那么总错误率是？

先补充一些随机数学的知识（非严格地）

现在考虑这 n 次比较，如果看成独立的，总错误率 1-(1-1/M)^n

当 M >> n 时，总错误率接近于 \frac{n}{M}

当 M = n 时，接近于 1-\frac{1}{e} (≈0.63)

如果不是独立的，最坏情况也就是全部加起来，等于 \frac{n}{M}

要改进错误率，可以增加 M

选取一个大的 M ，或者两个互质的小的 M

时间复杂度不变，单次错误率平方

Hash 的应用

不只是字符串中，在其他情况也可以用。

假设有个程序要对 10^{18} 大小的数组进行操作，保证只有 10^6 个元素被访问到

由于存不下，我们在每次操作时，对下标取 Hash 值（比如，直接 \bmod M ），然后在 M 大小的数组内操作

如果冲突了怎么办？

方案 1：尝试找下一个位置，下下个位置（优点：速度快；缺点：删除麻烦）

方案 2：在数组的每个位置直接挂一个链表

build本页面最近更新：，更新历史
edit发现错误？想一起完善？ 在 GitHub 上编辑此页！
people本页面贡献者：OI-wiki
copyright本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用

评论