哈希

STL 中的哈希

STL 中的哈希表可以使用 unordered_map 和 unordered_set 。

哈希函数

1. 一般数值直接取模就可以(一般模一个质数，并且该质数离2的整次幂尽量远)；
2. 如果有冲突，则需要处理解决，因此有了哈希表的不同存储方式。

哈希存储结构

开放寻址法以及拉链法用于处理冲突。

开放寻址法

根据哈希函数值查找存储位置，若存储位置已被占用，则向后查询第一个可用位置并放入。

拉链法

哈希函数值相同的数将会存储在哈希值对应处的链表上。

//插入操作(写法类似邻接表)
void insert(int x)
{
    int k = (x % mod + mod) % mod;//避免负数
    e[idx] = x, ne[idx] = h[k], h[k] = idx++;
}

//查询操作
bool find(int x)
{
    int k = (x % mod + mod) % mod;//避免负数
    for(int i = h[k]; i != -1; i = ne[i])
        if(e[i] == x) return true;
    return false;
}

字符串哈希

字符串前缀哈希法。

$H[i]$ 表示字符串中前 $i$ 个字符的哈希值；约定 $H[0] = 0$ 。

int p = 131;//经验值
//预处理
for(int i = 1; i <= n; ++i)
{
    H[i] = H[i - 1] * p + str[i];
    P[i] = P[i - 1] * p;//find函数中有用
}

//find函数
int find(int l, int r)
{
    return H[r] - H[l - 1] * P[r - l + 1];//H[l - 1] * P[r - l + 1]的目的是去除1~l - 1这一段的哈希值，因为i从小到大，所以要乘以P[r - l + 1]
}

//判断两区间中的子串是否一致
find(l1, r1) == find(l2, r2);

这个方法可以用来判断字符串中某两个区间是否是相同的。