本笔记内容来源于算法基础课

哈希表

将较大范围的值域映射到连续的空间$0\sim N$,提供添加和查找操作,一般采用标记删除的方式

离散化是一种特殊的哈希,它需要保证映射后的数据的有序性

$h(x)$称为哈希函数

基本思路采用取余$h(x) = x \bmod N$

映射可能存在冲突,不同的数映射到相同的数,需要对冲突进行处理

确定$N$

$N$ 通常采用质数,离2的整此幂尽可能地远,从而使得冲突的概率降低

求质数模板

for (int i = N; ; i++) {
    boolean flag = true;
    for (int j = 2; j *j <= i; j++) {
        if (i % j == 0) {
            flag = false;
            break;
        }
    }
    if (flag) {
        System.out.print(i);
        break;
    }
}

开放寻址法

使用一个较长的数组h存储映射的所有的元素，数组长度为$2N \sim 3N$，避免冲突

代码较拉链法更加简单

数组初始化为超越数据范围的数,$0x3f3f3f3f > 10^9$,且乘以2后不会溢出

初始化

static final int Null = 0x3f3f3f3f;
void init() {
    for (int i = 0; i < N; i++) h[i] = Null;
}

对于冲突元素，从右向左分配一个空闲的空间

查询x的存储位置，存在为当前数组中的下标，若不存在则返回则为应该存储的位置

int find(int x) {
     int k = (x % N + N) % N;
     while (h[k] != Null && h[k] != x) { // 存在元素且不为x则向后查找
         k++;
         if (k == N) k = 0; // 移动到边界，回到0位置
     }
     return k;
}

插入操作

void insert(int x) {
    h[find(x)] = x;
}

查询操作

boolean query(int x) {
    return h[find(x)] != Null;
}

拉链法

对于数组中映射到相同的的元素,采用单链表的方式存储所有元素(当中包含了多条链表)，h数组只存储头节点的下标

h[M] 表示元素的映射到的数组,h[i]代表映射到i的头节点下标
e[N] 存储元素的值
ne[N] 存储元素的next
idx 哨兵

初始化

void init() {
    for (int i = 0; i < N; i++) h[i] = -1; // 链表的空节点用-1表示
}

插入操作

void insert(int x) {
    int k = (x % N + N) % N; // 保证无论正负数的余数都是正数
    // 插入x到头节点之前,并成为新的头节点    
    e[idx] = x; 
    ne[idx] = h[k]
    h[k] = idx;
    idx++;
}

查询操作

boolean query(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;
}

字符串哈希方式

字符串前缀哈希法

首先将字符串的所有前缀的哈希值求出，字符串下标从1开始

$h[0] = 0, h[1] = hash(str[1,1]), h[2] = hash(str[1,2]) …$

将字符串看成一个$P$进制的数，通过$\bmod Q$映射到$0 \sim Q-1$

注意

1. 不能将字母映射成数字0，否则$A, AA, AAA, …$的哈希值相同
2. 假定不存在冲突，通常取$P = 131, 13331, Q= 2^{64}$

利用前缀哈希能够计算任意子串$hash(str[l, r])$的哈希值

$h[r] = P^{R-1} … P^0$
$h[l-1] = P^{L-2} … P^0$

由于字符串的$P$进制数是从高位到低位，因此子串的哈希值需要移动到高位对齐相减

$h[r] - h[l-1] \times P ^{r - l + 1}$

中使用unsigned long long的溢出来相等于取模操作

初始化

static final int P = 131;
void init(char[] s) {
    p[0] = 1; // p^0 = 1
    for (int i = 1; i <= n; i++) {
        h[i] = h[i - 1] * P + s[i]; // 只要没有字符为0就可
        p[i] = p[i - 1] * P; // 同时记录p的次方
    }
}

查询哈希值

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