C++ 模拟散列表 || 哈希表存储与查询，模版题（拉链法）

本文主要是介绍C++ 模拟散列表 || 哈希表存储与查询，模版题（拉链法），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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

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

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

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

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

每个结果占一行。

数据范围
1≤N≤105

−109≤x≤109
输入样例：
5
I 1
I 2
I 3
Q 2
Q 5

#include <iostream>
#include <cstring>using namespace std;const int N = 100003;int n;
int h[N], e[N], ne[N], idx; 
//h是哈希表（头结点数组）、e是元素数组、ne是链表中下一个元素的索引
/*h 数组是哈希表的数组，每个元素表示一个桶。
h[k] 存储的是第 k 个桶的头结点，即链表中第一个元素的索引。（存的拉链的头结点的下标）
e 数组存储具体的元素值，每个元素值对应一个索引。
ne 数组存储链表中每个元素的下一个元素的索引。
idx 是当前要插入的元素的索引。*/void insert(int x)
{// 计算哈希值，使用取模运算防止越界int k = (x % N + N) % N; // x % N x是负数的话保证这个哈希函数映射一定是正数// 插入到哈希表中，使用链地址法处理哈希冲突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()
{scanf("%d", &n);memset(h, -1, sizeof h);// 初始化哈希表的头结点为 -1，表示空链表while(n -- ){char op[2];int x;scanf("%s%d", op, &x);if(op[0] == 'I'){insert(x);}else{if(find(x)) printf("Yes\n");else printf("No\n");}}return 0;
}