终于掌握了两种处理哈希冲突的方法了！特意来总结
哈希是很好的一样东西。但是unordered_map更好啊
By the way, NOIP是可以用unordered_map的，需要这么用：
#include<tr1/unordered_map>
int main()
{
std::tr1::unordered_map<int.int> mmp;
.......
}亲测在NOI Linux下面可以编译，所以就ok了哇！
解决哈希冲突的好方法有两种：一种是开放地址法，一种是拉链法。
开放地址法
一句话的思路：自己的地方被人占了，我就占别人的地方。
一旦发生冲突，就把自己的下标++，然后再取哈希函数，直至不冲突为止，那么就在这个不冲突的地方直接安居。
期望的时间复杂度不是很优，但是还可以。至少比map快啊！
拉链法
一句话的思路：自己的地方被人占了，我就排在她后面就好了哇！
一旦发生冲突，就拉一条链表，把自己插在这条链表的尾部（或者首部）。
这样的期望复杂度真的很优秀。是值得学习的一种方法。
下面的代码是使用拉链法解决的。开放地址法的luogu的题解上面有，可以自己去学一下，很简单的。
讲道理拉链法比开放地址法跑得快太多太多了
拉链法用的时间是565ms，2.28M的内存。
开放地址法的时间是7176ms，七十多M的内存。
所以你懂了吧？
代码：
#include<cstdio>
#include<cstring>
const int MOD = 100007;
struct Hashtable
{
int head[MOD], next[MOD], key[MOD], value[MOD];
int tot;
int hash(int x)
{
if(x < 0) x = -x;
return x % MOD;
}
int count(int ke)
{
for(int i = head[hash(ke)]; i; i = next[i])
{
if(key[i] == ke) return value[i];
}
}
void insert(int ke, int val)
{
tot++;
key[tot] = ke; value[tot] = val; next[tot] = head[hash(ke)];
head[hash(ke)] = tot;
}
void clear()
{
tot = 0;
memset(head, 0, sizeof head);
memset(next, 0, sizeof next);
memset(key, 0, sizeof key);
memset(value, 0, sizeof value);
}
} hashtable;
int n;
int read()
{
int ans = 0, s = 1;
char ch = getchar();
while(ch > '9' || ch < '0'){ if(ch == '-') s = -1; ch = getchar(); }
while(ch >= '0' && ch <= '9') ans = ans * 10 + ch - '0', ch = getchar();
return s * ans;
}
int main()
{
int T = read();
while(T--)
{
hashtable.clear();
n = read();
bool first = true;
for(int i = 1; i <= n; i++)
{
int temp = read();
if(!hashtable.count(temp))
{
if(first) printf("%d", temp), first = false;
else printf(" %d", temp);
hashtable.insert(temp, 1);
}
}
printf("\n");
}
return 0;
}