哈希表

数字哈希 与 字符串前缀哈希法

哈希表主要作用为将一个较大的空间映射到一个较小的空间

一、数字哈希

将一些值域区间大的数字映射到一个较小的区间，一般将每个数字进行取模运算，模一般为一个离2的整次幂较远的一个质数(这样取可以减少冲突)，例:0—1e9 映射到 0—1e5，我们可以模1e5+3这个数字，（但是数组就得开得大于这个数字了） 有两种避免冲突的方法，分别为 拉链法 与 开放寻址法

拉链法

运用了邻接表的思想，将每次取模操作的结果作为相应的数组地址，将原数字储存于该数组地址的链表上，每次查找时则遍历取模操作结果的数组地址上的链表，来检查是否存在该数字

代码实现

查找操作

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

插入操作

int t = (x % p + N) % N; //p为模
e[++idx] = x;
ne[idx] = h[t];
h[t] = idx;

开放寻址法

一般将数组开为映射后区间大小的两倍，模的选择方法同拉链法，一般取小于映射区间的一个最大的质数，开放寻址法具体思路核心是首先将数组元素初始化为一个不存在于源区间值域的数字，(例如0x3f3f3f3f)，检查一个数x的取模操作的结果对应的数组地址上储存的元素如果同时满足不等于初始化元素并且不等于x，则继续检查下一个地址，如果检查到映射区间的最大地址时返回到第一个地址，直到不满足上述条件，则返回当前地址，如果x存在于哈希表，则该地址为x的地址，如果x不存在，则当前地址为x应当储存的地址

代码实现

查找操作

int find(int x)
{
    int t = (x % p + N) % N; //p为模
    while (a[t] != null && a[t] != x)
    {
        if (t == N)
            t = 0;
        t++;
    }
    return t;
}

插入操作

k = find(x);
a[k] = x;

二、字符串前缀哈希法

思路

通过将字符串看作一个p进制的数字，求出字符串的值对一个数字q取模得到的值作为前缀哈希数组的值，来求出整个前缀哈希数组的方式 注：

• 假设人品足够好不产生冲突的情况
• p一般取131或者13331，q取2^64，这样一般不会出现冲突，并且使用 unsigned long long 定义前缀数组则可通过溢出的方式免去取模的步骤

我们通过上述方法也可求出一个字符串任意子段的哈希值，公式为

a[r] - a[l - 1] * p ^ (r - l + 1) // 自己理解

代码实现

建立字符串前缀哈希数组

p[0] = 1;
for (int i = 1; i <= n; i++)
{ 
    p[i] = p[i - 1] * P;          // 简化求子段哈希
    a[i] = a[i - 1] * P + str[i]; // a为前缀数组
}

求子段哈希

a[r] - a[l - 1] * p[r - l + 1];