哈希表

散列函数

将关键字映射到存储地址的函数
两个原则：简单、均匀
1. 简单：快速计算
2. 均匀：避免聚集，减少冲突

常用方法

直接定址法：$hash(key) = a * key + b$
除留余数法：$hash(key) = key \% p$
MAD法：$hash(key) = (a * key + b) \% p$
随机数法：$hash(key) = rand(key) \% p$
平方取中法：尽可能让每一位的取值都影响到地址，从而减少冲突

处理冲突的方法

开放寻址法

\[hash'(key) = (hash(key)+d_i)\%m$$ 其中$d_i$为增量序列，以下方法针对该增量序列做出区分 - 其中$m$应尽量取为**素数** 1. **线性探测法** $$d_i = 1, 2……,m-1$$ - 即逐个向后搜索空位置 1. 优点：无需附加的空间、查找链具有局部性、可以充分利用系统缓存（加速）、有效减少IO 2. 缺点：一次冲突可能导致后续的冲突出现 2. **二次探测法** $$d_i = \pm 1^2, \pm 2 ^ 2,……,\pm k ^ 2$$ - 增大冲突距离 1. 优点：避免线性探测中的后续冲突 2. 缺点：可能无法找到空位置；若涉及外存，可能导致IO - 针对缺点的解决方法：取表长为$4*k + 3$ 的**素数$M$**，必然可以保证查找链的前$M$项互异 3. 随机探测法 $$d_i = 伪随机序列\]

链地址法（拉链法）

将映射至同一地址的关键字存储在一个线性链表中

再散列法

设置另外一个散列函数 1. 缺点：内存空间跳跃，非连续，无法利用系统缓存加速存储 2. 优点：节省空间

模拟散列表

拉链法

#include <iostream>
#include <cstring>
using namespace std;
const int N = 100003;
//令N为质数，可以最大程度上避免重复的问题
int h[N], e[N], ne[N], idx;

void insert(int x){
    int t = (x % N + N) % N;
    e[idx] = x;             //建立链表
    ne[idx] = h[t];
    h[t] = idx++;
}

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

int main(){
    int a, n;
    char op[2];
    memset(h, -1, sizeof h);
    cin >> n;

    while(n--){
        scanf("%s%d", op, &a);
        if(*op == 'I'){
            insert(a);
        }
        else{
            if(find(a)){
                cout << "Yes" << endl;
            }
            else{
                cout << "No" << endl;
            }
        }
    }

    return 0;
}

字符串哈希

预处理所有前缀的哈希值

问题： 1. 如何定义字符串的哈希值 1. 通过前缀定义一个P进制数据 2. 不能映射成0 3. 假定不存在冲突（P取131， Q取2^64）

用处： 1. 快速判断两个字符串是否相等

#include <iostream>
using namespace std;
const int N = 100010, P = 131;

typedef unsigned long long ULL;

int n, m;
char str[N];
int h[N], p[N];

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


int main(){
    scanf("%d%d%s", &n, &m, 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];
    }

    int l1, r1, l2, r2;
    while(m--){
        scanf("%d%d%d%d", &l1, &r1, &l2, &r2);
        if(getnum(l1, r1) == getnum(l2, r2)) puts("Yes");
        else puts("No");
    }

    return 0;
}