Hash—拉链法存储

· · 个人记录

哈希（散列函数）定义

Hash，一般翻译做散列、杂凑，或音译为哈希，是把任意长度的输入（又叫做预映射pre-image）通过散列算法变换成固定长度的输出，该输出就是散列值。这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，所以不可能从散列值来确定唯一的输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。

模板题:P4305 [JLOI2011]不重复数字

题目描述： 给定 n 个数，要求把其中重复的去掉，只保留第一次出现的数。

对于 30\% 的数据，n≤100，给出的数∈[0,100]。

对于 60\% 的数据，给出的数∈[0,10^4]。

对于 100\%的数据，1≤T≤50，1≤n≤5×10^4，给出的数在 32 位有符号整数范围内。

这道题是用哈希过的。

易错点汇总

（既然能写出来，自然是自己踩过的坑）

1.若要用不定长数组储存要用vector，而不是string，鬼知道我刚开始怎么会用string的。

2.hash取模要二重：即y = (x % mod + mod) % mod; 首先我是没二次取模，其次，更离谱的是还有写成这样的：y = (y % mod + mod) % mod；和这样的：y = (y % mod + y) % mod;真是无语了。

3.拉链（即数组）一定要 大于或等于 模数，不然会RE。

时间优化

展示一下T4个点的代码，用快读加O2优化都不能过。

T 4个点

#include <cstdio>
#include <iostream>
#include <vector>
using namespace std;
const int N = 5e5 + 30;
const int mod = 500029;
int t, n;
int num[N];
vector <int> str[N], check[N];
void insert(int x) {
    int y = (x % mod + mod) % mod;
    int flag = 0;
    for (int i = 0; i < str[y].size(); i++)
        if (str[y][i] == x) {
            flag = 1;
            break;
        } 
    if (!flag) str[y].push_back(x), check[y].push_back(1);
}
bool find(int x) {
    int y = (x % mod + mod) % mod;
    for (int i = 0; i < str[y].size(); i++)
        if (str[y][i] == x && check[y][i]) {
            str[y][i] = 0;
            check[y][i] = 0;
            return true;
        }
    return false;
}
inline int read()
{
    int X=0; bool flag=1; char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') flag=0; ch=getchar();}
    while(ch>='0'&&ch<='9') {X=(X<<1)+(X<<3)+ch-'0'; ch=getchar();}
    if(flag) return X;
    return ~(X-1);
}
int main() {
    scanf("%d", &t);
    while (t--) {
        for (int i = 0; i < N; i++) str[i].clear(), check[i].clear();
        scanf("%d", &n);
        for (int i = 0; i < n; i++) {
            num[i] = read();
            insert(num[i]);
        }
        for (int i = 0; i < n; i++)
            if (find(num[i])) printf("%d ", num[i]);
        printf("\n");
    }
    return 0;
}

再看一下AC代码

无快读、无O2优化 AC

#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
const int N = 5e4 + 10;
const int mod = 50021;
int h[N], e[N], ne[N], idx;
int num[N], check[N];
int t, n; 
void insert(int x) {
    int y = (x % mod + mod) % mod;
    e[idx] = x;check[idx] = 1;
    ne[idx] = h[y];
    h[y] = idx++;
}
bool find(int x) {
    int y = (x % mod + mod) % mod;
    for (int i = h[y]; i != -1; i = ne[i])
        if (e[i] == x) {
            if (check[i]) {
                check[i] = 0;
                return true;
            } else break;
        }
    return false;
}
int main() {
    scanf("%d", &t);
    while (t--) {
        memset(h, -1, sizeof(h)); idx = 0;
        memset(check, 0, sizeof(check));
        scanf("%d", &n);
        for (int i = 0; i < n; i++) {
            scanf("%d", &num[i]); 
            insert(num[i]);
        }
        for (int i = 0; i < n; i++)
            if (find(num[i])) printf("%d ", num[i]);
        printf("\n");
    }
}

两个可以对比一下，发现一下为什么差不多的代码一个能过，另一个却会TLE。

可以发现主要就是vector的各种操作太费时间了，所以下次写就用链式前向星的吧！反正也很熟悉了。