跳转至

哈希

在介绍 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本页面贡献者：
copyright本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用

评论