📖Mosquito's Note📖

哈希表

首先什么是 哈希表，哈希表（英文名字为 Hash table，国内也有一些算法书籍翻译为散列表，大家看到这两个名称知道都是指 hash table 就可以了）。

哈希表是根据关键码的值而直接进行访问的数据结构。

这么这官方的解释可能有点懵，其实直白来讲其实数组就是一张哈希表。

哈希表中关键码就是数组的索引下标，然后通过下标直接访问数组中的元素，如下图所示：

image

那么哈希表能解决什么问题呢，一般哈希表都是用来快速判断一个元素是否出现集合里。

例如要查询一个名字是否在这所学校里。

要枚举的话时间复杂度是 O(n)，但如果使用哈希表的话， 只需要 O(1)就可以做到。

我们只需要初始化把这所学校里学生的名字都存在哈希表里，在查询的时候通过索引直接就可以知道这位同学在不在这所学校里了。

将学生姓名映射到哈希表上就涉及到了 hash function ，也就是哈希函数

哈希函数

哈希函数，把学生的姓名直接映射为哈希表上的索引，然后就可以通过查询索引下标快速知道这位同学是否在这所学校里了。

哈希函数如下图所示，通过 hashCode 把名字转化为数值，一般 hashcode 是通过特定编码方式，可以将其他数据格式转化为不同的数值，这样就把学生名字映射为哈希表上的索引数字了。

image

如果 hashCode 得到的数值大于 哈希表的大小了，也就是大于 tableSize 了，怎么办呢？

此时为了保证映射出来的索引数值都落在哈希表上，我们会在再次对数值做一个取模的操作，就要我们就保证了学生姓名一定可以映射到哈希表上了。

此时问题又来了，哈希表我们刚刚说过，就是一个数组。

如果学生的数量大于哈希表的大小怎么办，此时就算哈希函数计算的再均匀，也避免不了会有几位学生的名字同时映射到哈希表 同一个索引下标的位置。

接下来哈希碰登场

哈希碰撞

如图所示，小李和小王都映射到了索引下标 1 的位置，这一现象叫做哈希碰。

image

一般哈希碰撞有两种解决方法， 拉链法和线性探测法。

拉链法

刚刚小李和小王在索引 1 的位置发生了冲突，发生冲突的元素都被存储在链表中。 这样我们就可以通过索引找到小李和小王了

img

（数据规模是 dataSize， 哈希表的大小为 tableSize）

其实拉链法就是要选择适当的哈希表的大小，这样既不会因为数组空值而浪费大量内存，也不会因为链表太长而在查找上浪费太多时间。

线性探测法

使用线性探测法，一定要保证 tableSize 大于 dataSize。 我们需要依靠哈希表中的空位来解决碰撞问题。

例如冲突的位置，放了小李，那么就向下找一个空位放置小王的信息。所以要求 tableSize 一定要大于 dataSize ，要不然哈希表上就没有空置的位置来存放 冲突的数据了。如图所示：

image

整数哈希

哈希函数可以简单的设计为: hash(x)=(xmodk+k)modkhash(x) = ( x mod k + k ) mod k

这样的写法是为了在 cpp 里不会出现负数的哈希值

数学上，哈希数组的长度，也就是 k 的值，最好取质数，这样碰撞的概率最小


// 线性
#include <iostream>
#include <cstring>

using namespace std;

const int N = 2e5 + 3, null = 0x3f3f3f3f;
int h[N];

void insert(int x) {
    int k = (x % N + N) % N;
    while (h[k] != null) {
        k ++;
        if (k == N) k = 0;
    }
    h[k] = x;
}

int find(int x) {
    int k = (x % N + N) % N;
    while (h[k] != null && h[k] != x) {
        k ++;
        if (k == N) k = 0;
    }
    return h[k];
}


int main() {
    int n;
    cin >> n;
    memset(h, 0x3f, sizeof h);
    while (n --) {
        string op;
        int x;
        cin >> op >> x;
        if (op == "I") insert(x);
        else {
            if (find(x) != null) puts("Yes");
            else puts("No");
        }
    }

    return 0;
}

// 拉链
#include <iostream>
#include <cstring>

using namespace std;

const int N = 1e5 + 3;
int h[N], e[N], ne[N], idx;

void insert(int x) {
    int k = (x % N + N) % N;
    e[idx] = x;
    ne[idx] = h[k];
    h[k] = idx ++;
}

bool find(int x) {
    int k = (x % N + N) % N;
    for (int i = h[k]; i != -1; i = ne[i])
        if (e[i] == x) return true;

    return false;
}


int main() {
    int n;
    cin >> n;
    memset(h, -1, sizeof h);
    while (n --) {
        string op;
        int x;
        cin >> op >> x;
        if (op == "I") insert(x);
        else {
            if (find(x)) puts("Yes");
            else puts("No");
        }
    }

    return 0;
}

字符串哈希（哈希函数）

如果我们把一个字母看成一个数字，那么一串字符就可以看成是一个p进制的数字

即: ABC=A∗p2+B∗p1+C∗p0ABC = A * p^2 + B * p^1 + C * p^0，如果字符串太长了，不方便存储，因此可以模上一个数，这就是 字符串的哈希函数

hash(ABC)=(A∗p2+B∗p1+C∗p0)mod264hash(ABC) = ( A * p^2 + B * p^1 + C * p^0 ) mod 2^{64}

一般上，习惯把这个模上的数定为2642^{ 64 }，p 定为1331 或131

又因为 unsigned long long 表示的范围为 0 ~ 2^64 - 1, 我们可以用这个类型存储哈希值，计算机会自动帮我们取模

如果我们有了一个字符串的所有前缀 hash 值，那么我们能在O(1)O(1)内求出任意一段子字符串的 hash 值

公式为： hash(l,r)=hash(lenght,r)−hash(lenght,l−1)∗pr−l+1hash(l, r) = hash(lenght, r) - hash(lenght, l - 1) * p^{r - l + 1}

乘上 pr−l+1p^{r - l + 1} 表示把两个前缀字符串的最高位对齐，即把[lenght, r] 向左移动到 与 [lenght, l] 对齐，才能相减

// 判断两段子字符串是否完全相同
#include <iostream>

using namespace std;
const int N = 100005, P = 131;
typedef unsigned long long ULL;

ULL p[N];
ULL h[N];
char str[N];

ULL get(int l, int r) {
    return h[r] - h[l - 1] * p[r - l + 1];
}

int main(){
    int n, m;
    cin >> n >> m;
    cin >> str + 1;

    p[0] = 1;
    for (int i = 1; i <= n; i ++)
        p[i] = p[i-1] * P,
        h[i] = h[i-1] * P + str[i];

    while (m --) {
        int l1, r1, l2, r2;
        cin >> l1 >> r1 >> l2 >> r2;
        if (get(l1, r1) == get(l2, r2)) puts("Yes");
        else puts("No");
    }

    return 0;
}

滚动哈希