存储结构
1. 开放寻址法
const int N = 200003; // 开放寻址法数组大小开数据总数的2~3倍,最好是质数
const int null = 0x3f3f3f3f; // 用0x3f3f3f3f > 10^9 表示空指针
int find(int x)
{
int k = (x % N + N) % N; // x有可能是负数,所以先取模再加N再取模
while (h[k] != null && h[k] != x)
{
k ++;
if (k == N) k = 0;
}
return k;
}
2. 拉链法
void insert(int x)
{
int k = (x % N + N) % N;
e[idx] = x;
ne[idx] = h[k];
h[k] = idx ++;
}
int find(int x)
{
int k = (x % N + N) % N;
for (int i = h[k]; i != -1; i = ne[i])
if (e[i] == x)
return 1;
return 0;
}
字符串哈希
- 用途:快速判断两个字符串是否相等
- 注意点:
2.1 任意字符不可以映射成0,否则会出现不同的字符串都映射成0的情况,比如A,AA,AAA皆为0
2.2 冲突问题:通过巧妙设置P (131 或 13331) , Q (2^64)的值,一般可以理解为不产生冲突。
问题是比较不同区间的子串是否相同,就转化为对应的哈希值是否相同。
求一个字符串的哈希值就相当于求前缀和,求一个字符串的子串哈希值就相当于求部分和。
const int N = 100010, P = 131;
typedef unsigned long long ULL;
ULL h[N], p[N]; // 由于最后要模Q = 2^64,直接使用unsigned long long 溢出就是取模
// p[k]: p的k次方
ULL get(int l, int r) // 得到从l到r区间的哈希值
{
return h[r] - h[l - 1] * p[r - l + 1];
}
p[0] = 1;
for (int i = 1; i <= n; i ++) // 预处理每个字串的哈希值
{
h[i] = h[i - 1] * P + str[i];
p[i] = p[i - 1] * P;
}