数据结构_哈希

哈希表

开放寻址法: 找到初位置， 如果该位置已经有元素， 在其下一个位置放置

代码模板

int find(int x)
{
    int t = (x % N + N) % N;
    while (h[t] != null && h[t] != x)
    {
        t ++ ;
        if (t == N) t = 0;
    }
    return t;
}
void solve() {
    char op[2];
    int x;
    scanf("%s%d", op, &x);
    if (*op == 'I') h[find(x)] = x;
    else {
        if (h[find(x)] == null) puts("No");
        else puts("Yes");
    }
}

拉链法： 使用邻接表存储

代码模板

void insert(int x) {
    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;
}

void solve() {
    char op[2];
    int x;
    scanf("%s%d", op, &x);

    if (*op == 'I') insert(x);
    
    else {
        if (find(x)) puts("Yes");
        else puts("No");
    }
}

字符串哈希

实现思路：

• 预处理前缀哈希: p数组

str = "ABCDEFGHI";
p[1] = A;
p[2] = AB;
p[3] = ABC;
......

• 将字符串看作是P进制的数， P = 131 or 13331 (经验值)
• 前缀哈希值: h数组

str = ABCD;
p[1] = A;
p[2] = AB;
p[3] = ABC; 
p[4] = ABCD;

例如： (h[4] = (1 imes P^3 + 2 imes P^2 + 3 imes P^1 + 4 imes P^0)) (\%) (Q)

• 判断中间子串是否相同：

h[r] - h[l - 1] * p[r - l + 1]

分析：以数的进制为例：

已知 (R) = ((1111 | 1111 | 1111)_p)、(L) = ((1111|1111)_p)
求(res) = ((1111)_p)

• 将(L)左移至与(R)左边对齐
• 得到 (L) = ((1111|0000)_p)
• (res) = (R - L)

注意

• 不要映射为零：减少冲突
• (P)取经验值131或者13331，(Q = 2^{64})
• 可采用(unsigned) (long) (long) 类型的数组，溢出时自动取模

代码

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

void solve() {
    scanf("%d%d%s", &n, &m, str + 1); //  字符串从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];
    }
    while(m--) {
        int l1, l2, r1, r2; scanf("%d%d%d%d", &l1, &r1, &l2, &r2);
        if(get(l1, r1) == get(l2, r2)) puts("Yes");
        else puts("No");
    }
}