[数据结构与算法]模拟散列表

例题：
维护一个集合，支持如下几种操作：

“I x”，插入一个数x；
“Q x”，询问数x是否在集合中出现过；
现在要进行N次操作，对于每个询问操作输出对应的结果。

输入格式
第一行包含整数N，表示操作数量。

接下来N行，每行包含一个操作指令，操作指令为”I x”，”Q x”中的一种。

输出格式
对于每个询问指令“Q x”，输出一个询问结果，如果x在集合中出现过，则输出“Yes”，否则输出“No”。

第一种构造哈希表的方法为拉链法，但是这里又不使用链表，很神奇

h[]这个数组实际上存的是索引，存的是用哈希之后的关键词对应第几个数的索引，e[]为从左到右依次输入的数的数组，ne[]这个数组就比较巧妙，他记得是第x个数他的前一个数的索引，若他是第一个数，则是-1,idx就是那个索引。

#include <cstring>
#include <iostream>

using namespace std;

const int N=1e5+3；    //质数

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;
}

int main()
{
	int n,x; string ord;
	memset(h, -1, sizeof h);
	cin >> n;
	while (n--)
	{
		cin.ignore();
		cin >> ord >> x;
		if (ord[0] == 'I') Insert(x);
		else {
			if (Find(x)) cout << "Yes" << endl;
			else cout << "No" << endl;
		}
	}
	return 0;
}

开放定址法

这种方法思路较上一种方法简单一些，清晰一点，就是如果这个关键词重复的话就找下一个空的位置，然后放进去

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int null= 0x3f3f3f3f;
//它可以作为无穷大使用而不致出现数据大于无穷大的情形。
const int N = 2*1e5 + 3;//开放寻址法一般为题目范围的两三倍
int h[N];
void Insert(int x)
{
	int k = (x % N + N) % N;
	for (int i = k;; i++)
	{
		if (h[i] == null) {
			h[i] = x;
			return;
		}
	}
}
bool Find(int x)
{
	int k = (x % N + N) % N;
	while (h[k] != null && h[k] != x)  k++; //当发现一个位置是空关键词已经全部找完
	if (h[k] == x) return true;
	else return false;
}
int main()
{
	memset(h, null, sizeof h);//全部置空
	int n, x;
	char ord;
	cin >> n;
	while (n--)
	{
		cin.ignore();
		cin >> ord >> x;
		if (ord == 'I') Insert(x);
		else
		{
			if (Find(x)) cout << "Yes" << endl;
			else cout << "No" << endl;
		}
	}
	return 0;
}

总结

一般采用开放寻址法，因为开放寻址所需要的空间较拉链法少，拉链法比开放寻址法更容易造成冗余，但拉链法要比开放定址法所需时间更少