[数据结构与算法]数据结构——哈希

一般哈希

模板

(1) 拉链法
    int h[N], e[N], ne[N], idx;

    // 向哈希表中插入一个数
    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;
    }

(2) 开放寻址法
    int h[N];

    // 如果x在哈希表中，返回x的下标；如果x不在哈希表中，返回x应该插入的位置
    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;
    }

模板题

代码

#include <iostream>
#include <cstring>

using namespace std;

const int N = 200003, null = 0x3f3f3f3f;    //  N取质数比较好，且比原N大2~3倍比较好

int h[N], n;

//  开放寻址法：
int find(int x) // 如果x在哈希表中，返回x的下标；如果x不在哈希表中，返回x应该插入的位置
{
    int t = (x % N + N) % N;    //  防止因为负数取模在C++里是负数
    while(h[t] != null && h[t] != x)
    {
        t++;
        if(t == N)  t = 0;
    }
    return t;
}

int main()
{
    memset(h, 0x3f, sizeof(h)); //  这里的0x3f就是null，4个字节

    scanf("%d", &n);
    while(n--)
    {
        char op;
        int x;
        scanf("%s%d", &op, &x); //  %c改成%s避免不必要的空白读入（%c可以读入空格）

        if(op == 'I')
            h[find(x)] = x;
        else if(h[find(x)] == null)
            puts("No");
        else
            puts("Yes");
    }

    return 0;
}

字符串哈希

模板

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

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

// 初始化
p[0] = 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] 的哈希值
ULL get(int l, int r)
{
    return h[r] - h[l - 1] * p[r - l + 1];
}

模板题

代码

#include <iostream>

using namespace std;

typedef unsigned long long ULL;

const int N = 100010, P = 131;

int n, m, l1, r1, l2, r2;
char str[N];
ULL h[N], p[N];

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

int main()
{
    cin >> n >> m >> str+1;

    p[0] = 1;
    for(int i = 1; i <= n; i++)
    {
        h[i] = h[i-1] * P + str[i];
        p[i] = p[i-1] * P;
    }

    while(m--)
    {
        cin >> l1 >> r1 >> l2 >> r2;

        if(get(l1, r1) == get(l2, r2))
            puts("Yes");
        else
            puts("No");
    }

    return 0;
}