一般哈希

哈希表中取模所用的N应当取质数
如大于100000的第一个质数为100003

拉链法

处理冲突：

操作：
1. 添加
2. 查找
3. 删除(使用bool数组在要删除的点打一个标记)

// h[]为拉链, e[]为h上的单链表
int h[N], e[N], ne[N], idx;

// 初始化:
memset( h, -1, sizeof(h));

// 向哈希表中插入一个数
void insert(int x) {
    // + N 防止负数出现
    int k = (x % N + N) % N;
    // 单链表插入操作,插入到每条链表的表头处
    e[idx] = x, ne[idx] = h[k];
    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;
}

开放寻址法

核心思想: 从映射到的第k个位置开始找,向前遍历,直到找到一个数组的空缺位置来存放

1. 添加
2. 查找
3. 删除(在数组中要删除的点打一个标记)

// 数组长度一般为题目所给数据的2~3倍
int h[N];
//定义一个无穷大量 :
const int null = 0x3f3f3f3f;
// 初始化：
memset( h, 0x3f, sizeof(h));

/*
find函数: 
如果x在哈希表中，返回x的下标
如果x不在哈希表中，返回x应该插入的位置
*/
int find(int x) {
    int k = (x % N + N) % N;
    // h[k] != null 说明这个位置不是空缺的
    while (h[k] != null && h[k] != x) {
        k ++ ;
        if (k == N) k = 0;
    }
    return k;
}

字符串哈希

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

可快速判断一个长字符串两端区间内的子串是否相同

ex:
“ABCD”
( 1 2 3 4 ) [ P进制 ]；
转化为10进制:
1 * pow(P,3) + 2 * pow(P,2) + 3 * pow(P, 1) + 4 * pow(P, 0);
哈希映射: % Q ——> 1 ~ Q - 1 之间的数

注意: 不能映射成0,下标从1开始 h[0] = 0;
h[] 从高位到低位

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

// 初始化

p[0] = 1; // p[] 首位是 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] 的哈希值
ex:
"1234", "12"
1234 - 12 * 100 = 34;
*/
ULL get(int l, int r) {
    return h[r] - h[l - 1] * p[r - l + 1];
}