🌹作者:云小逸
📝个人主页: 云小逸的主页
📝Github: 云小逸的Github
🤟motto:要敢于一个人默默的面对自己， ==强大自己才是核心==。不要等到什么都没有了，才下定决心去做。种一颗树，最好的时间是十年前，其次就是现在！学会自己和解，与过去和解，努力爱自己。==希望春天来之前，我们一起面朝大海，春暖花开！==🤟
👏专栏：C++👏 👏专栏：Java语言👏👏专栏：Linux学习👏
👏专栏：C语言初阶👏👏专栏：数据结构👏👏专栏：备战蓝桥杯👏
前言
今天这篇文章接着上一篇文章【哈希表（拉链法）】继续说解决哈希表冲突的第二种方法：开放寻址法。
——————————————————————————————
首先先写上几句话：献给坚持创作的我和点开这篇文章希望进步的你
1. 世界上最厉害的人，是说起床就起床，说睡觉就睡觉，说做事就做事，说玩就玩，说收心就收心，说不爱 就不爱。
2.一定要狠下心来努力变成一个很厉害的人，厉害到有一天，你可以随时离开那些令你不舒服的圈子和人， 让他们通通羡慕不已。
3.努力变得更厉害的原因是，以后遇到喜欢的人，除了真心，还有其他东西可以拿得出手。
4.我以为别人尊重我，是因为我很优秀。慢慢的我明白了，别人尊重我，是因为别人很优秀；优秀的人更懂 得尊重别人。对人恭敬其实是在庄严你自己。
5. 五粮液从不骂茅台，茅台也从不诋毁五粮液。双双成为世界名酒。人活着发自己的光就行，没必要灭别人 的灯。
例题： 模拟散列表
题目：
维护一个集合，支持如下几种操作：
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
输出样例：
Yes
No
开放寻址法：
核心思想：
与拉链法类似，要先建立一个哈希函数，将原数组映射到哈希函数上，
与拉链法相比，开放寻址法只需要建立一个数组，不用像拉链法那样再设置一个链表。
这里可以想象一下我们去上厕所的情景，先从k的位置【k是该数在哈希函数的映射值】开始看是否有人，有人就下一个坑位，没人就占这个位置。
添加：
从k的位置开始找，看这个坑位是否有人，有人就下一个
查找：
从第k的坑位开始查找：
当前坑位有人，是x,则查找到了。
当前坑位有人，但不是x，则下一个。
当前坑位没有人，说明x不存在。
删除：
按照查找的方式，如果找到x，一般不会将x删掉，只是打一个特殊的标志，以示删除掉了x，这个与拉链法类似。
代码：
#include <cstring>
#include <iostream>
using namespace std;
const int N = 200003;//题目要求N的范围是[0,10^5],但从经验上一维数组的长度要开到要求的2-3倍。
//这样就可以最大程度地降低冲突的概率，那么N取大于范围的第一个质数。
const int null = 0x3f3f3f3f;//设置一个数表示这个坑位没有人，即设定数组的初始化的值，
//且这个要在N的范围之外。
int h[N];
int find(int x)
{
int t = (x % N + N) % N;
while (h[t] != null && h[t] != x)//表示坑位不为0，且坑位内不是查找的值
{
t ++ ;//看下一个坑位
if (t == N) t = 0;//看完了最后的坑位，要返回到第一个坑位，循环回来看第一个坑位i
}
return t;//两种含义：k在哈希表中，返回k在哈希表的下标，如果不在哈希表中，则返回x应该存在哈希表的位置
}
int main()
{
memset(h, 0x3f, sizeof h);
int n;
scanf("%d", &n);
while (n -- )
{
char op[2];
int x;
scanf("%s%d", op, &x);
if (*op == 'I') h[find(x)] = x;
else
{
if (h[find(x)] == null) puts("No");
else puts("Yes");
}
}
return 0;
}代码解析：
1.N的范围：
const int N = 200003;//题目要求N的范围是[0,10^5],但从经验上一维数组的长度要开到要求的2-3倍。
//这样就可以最大程度地降低冲突的概率，那么N取大于范围的第一个质数。2.初始化的值：
const int null = 0x3f3f3f3f;//设置一个数表示这个坑位没有人，即设定数组的初始化的值，
//且这个要在N的范围之外。3.查找函数【核心操作】
int find(int x)
{
int t = (x % N + N) % N;
while (h[t] != null && h[t] != x)//表示坑位不为0，且坑位内不是查找的值
{
t ++ ;//看下一个坑位
if (t == N) t = 0;//看完了最后的坑位，要返回到第一个坑位，循环回来看第一个坑位i
}
return t;//两种含义：k在哈希表中，返回k在哈希表的下标，如果不在哈希表中，则返回x应该存在哈希表的位置
}
最后
十分感谢你可以耐着性子把它读完和我可以坚持写到这里，送几句话，对你，也对我：
1.我慢慢开始自渡了，变得不悲不喜，我接受世界上所有的不公平，善良并带点锋芒，我请求我自己，热爱 生活热爱自己。
2.人最怕的就是清醒的堕落，什么都懂，却不行动，没有压力，无忧无虑，没有目标，加上一点迷茫，到最 后还是维持现状。
3.我们总是喜欢用顺其自然来敷衍人生道路上的荆棘坎坷，却很少承认，真正的顺其自然，其实是竭尽所能 之后的不强求 ，而不是两手一摊的不作为。
4.你把性格交给星座，把努力交给鸡汤，把运气交给锦鲤，然后对自己说听过许多道理，但依然过不好这一 生。倒也是，过的好了才有鬼呢。
5. 你在人群中看到的每一个耀眼的人，都是踩着刀尖过来的。你如履平地般地舒适坦然，当然不配拥有任何 光芒。
最后如果觉得我写的还不错，请不要忘记==点赞==✌，==收藏==✌，加==关注==✌哦(｡･ω･｡)
愿我们一起加油，奔向更美好的未来，愿我们从懵懵懂懂的一枚==菜鸟==逐渐成为==大佬==。加油，为自己点赞！
