【模拟散列表】 - 实践

题目

拉链法

#include
using namespace std;
const int N = 1e5+3;
#define null -1
int h[N], ne[N], e[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 != null; i = ne[i]){if(e[i] == x) return true;}return false;
}
int main()
{memset(h, null, sizeof h);int n;scanf("%d", &n);char op[2];int num;for(int i = 1; i <= n; i++){scanf("%s %d", op, &num);int t = find(num);if(op[0] == 'I'){insert(num);}else{if(find(num)) puts("Yes");else puts("No");}}return 0;
}

注意

由于值域大于散射域，存在散射结果相同的情况，但是散射对象的数目是固定的，就是散射域的大小。

h数组用散射结果来访问，ne和e用当前指针来访问或者用h数组的内容来访问

insert函数：首先得到散射结果、然后利用当前指针存储e、结合h[k]和当前指针来头插，修改h[k]值为当前指针，当前指针增加。

find函数：首先得到散射结果、初始化头指针、以-1作为停止条件i = ne[i]作为迭代条件，找到e[i] == x就返回true，不然返回false;

开放寻址法

#include
using namespace std;
const int N = 2e5+3;
#define null 0x3f3f3f3f
int h[N];
int find(int x)
{int i = (x % N + N) % N;while(h[i] != null && h[i] != x){i++;if(i == N) i = 0;}return i;
}
int main()
{memset(h, 0x3f, sizeof h);int n;scanf("%d", &n);char op[2];int num;for(int i = 1; i <= n; i++){scanf("%s %d", op, &num);int t = find(num);if(op[0] == 'I'){h[t] = num;}else{if(h[t] != null) puts("Yes");else puts("No");}}return 0;
}

注意

find函数返回的是空地址或者是x的存在地址。循环条件是(不空)  && （不是）

理解：空了就返回空地址，不空而且是就返回存在地址。

前面储存数值在e，后面在h本身，所以后面不能拿-1来当空指针