【基础算法】哈希表（开放寻址法）

🌹作者:云小逸
📝个人主页:云小逸的主页
📝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. 你在人群中看到的每一个耀眼的人，都是踩着刀尖过来的。你如履平地般地舒适坦然，当然不配拥有任何 光芒。

​

最后如果觉得我写的还不错，请不要忘记点赞✌，收藏✌，加关注✌哦(｡･ω･｡)

愿我们一起加油，奔向更美好的未来，愿我们从懵懵懂懂的一枚菜鸟逐渐成为大佬。加油，为自己点赞！
​

​