哈希表（散列表）

因为Hash理解起来比较简单，所以直接上代码，就不过多废话了。

参考知乎文章：图文并茂详解数据结构之哈希表 - 知乎 (zhihu.com)

1. 数据结构特点

快速插入和快速查找，时间复杂度为O(1)
哈希表被填满后，涉及到扩容操作，效率低下
哈希值有碰撞（冲突）概率，解决碰撞的两种方式——开放寻址法与拉链法

2. 开放寻址法（以线性探测为例）

三种方式：
1. 线性探测
2. 二次探测
3. 再哈希法

2.1 解释说明

线性探测就是原始值经过一系列Hash函数后映射到Hash表中，若当前值已经被某一个数据所占有，则在当前位置的后一位置存储，若后一位置也已经被某一个数据所占有，则依次往后直到找到一个空位置

在算法竞赛中，我们常常需要用到设置一个常量用来代表“无穷大”。

比如对于int类型的数，有的人会采用INT_MAX，即0x7fffffff作为无穷大。但是以INT_MAX为无穷大常常面临一个问题，即加一个其他的数会溢出。而这种情况在动态规划，或者其他一些递推的算法中常常出现，很有可能导致算法出问题。

所以在算法竞赛中，我们常采用0x3f3f3f3f来作为无穷大。0x3f3f3f3f主要有如下好处：0x3f3f3f3f的十进制为1061109567，和INT_MAX一个数量级，即10^9数量级，而一般场合下的数据都是小于10^9的。0x3f3f3f3f * 2 = 2122219134，无穷大相加依然不会溢出。

可以使用memset(array, 0x3f, sizeof(array))来为数组设初值为0x3f3f3f3f，因为这个数的每个字节都是0x3f。

来源：https://www.acwing.com/file_system/file/content/whole/index/content/4799/

2.2 代码实现

int h[N];

memset(h, 0x3f, sizeof h);//h[N]使用需要初始化为每一项均为0x3f3f3f3f

// 如果x在哈希表中，返回x的下标；如果x不在哈希表中，返回x应该插入的位置
int find(int x) {
    int t = (x % N + N) % N;//(x % N + N) % N作用：保证t是正值
    while (h[t] != null && h[t] != x) {
        t ++ ;
        if (t == N) t = 0;
    }
    return t;
}

3. 拉链法

3.1 图解

3.2 代码实现

int h[N], e[N], ne[N], idx;
/*
e[idx]存储的是索引为idx的原始值x
ne[idx]存储的是（原始值为x，Hash值为k）拉链中索引为idx的拉链块儿所连接的下一个拉链块儿（数组模拟链表）
h[k]存储的是（原始值为x，Hash值为k）块儿中最新插入的数据对应的索引
idx存储的是索引，每插入一个数，idx++
*/
// 向哈希表中插入一个数
void insert(int x) {
    int k = (x % N + N) % N;
    e[idx] = x;
    ne[idx] = h[k];//ne[idx]指向原h[k]指向的第一个拉链块儿对应的idx
    h[k] = idx ++ ;//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;
}

4. 字符串哈希

字符串哈希学习文章推荐：【算法学习】字符串哈希（Hash）_字符串hash-CSDN博客

自然溢出Hash

所以计算字符串前k个字母的哈希值的公示为：

求子字符串的公示为：

例如，对于求**子字符串$s_3s_4$**的值，公示如下：

Hash在算法里面运用的比较简单，所以不过多解释，直接上$yxc$的代码模板

/*
核心思想：将字符串看成P进制数，P的经验值是131或13331，取这两个值的冲突概率低
小技巧：取模的数用2^64，这样直接用unsigned long long存储，溢出的结果就是取模的结果
*/

typedef unsigned long long ULL;
ULL h[N], p[N]; // h[k]存储字符串前k个字母的哈希值, p[k]存储 P^k(P的K次方) mod 2^64

// 初始化
p[0] = 1;
for (int i = 1; i <= n; i ++ ) {
    h[i] = h[i - 1] * P + str[i];
    p[i] = p[i - 1] * P;
}

// 计算子串 str[l ~ r] 的哈希值
ULL get(int l, int r) {
    return h[r] - h[l - 1] * p[r - l + 1];
}