🌹作者:云小逸
📝个人主页: 云小逸的主页
📝Github: 云小逸的Github
🤟motto:要敢于一个人默默的面对自己， ==强大自己才是核心==。不要等到什么都没有了，才下定决心去做。种一颗树，最好的时间是十年前，其次就是现在！学会自己和解，与过去和解，努力爱自己。==希望春天来之前，我们一起面朝大海，春暖花开！==🤟
👏专栏：C++👏 👏专栏：Java语言👏👏专栏：Linux学习👏
👏专栏：C语言初阶👏👏专栏：数据结构👏👏专栏：备战蓝桥杯👏
前言
今天我们来学习一下新知识【哈希表】，这个是算法中比较重要的知识点，希望下面我的讲解你可以喜欢。如果有错误，请私信告知，望见谅。
——————————————————————————————————————————
首先先写上几句话：献给坚持创作的我和点开这篇文章希望进步的你
1.很喜欢《稻盛和夫对年轻人的忠告》里这段话:“大部分人对吃苦的含义了解得太浅了。吃苦不是穷，而是一个人长时间为了某个目标而聚焦的能力。在这个过程中，放弃娱乐生活，放弃无效社交，放弃无意义的消费以及在此过程中不被理解的孤独。”它本质是一种自控力，自制力，坚持和深度思考的能力。
2.以前我被误解的时候，我总会想去解释，你误会我了，我不是这样的人，我会想尽一切办法去证明自己。而现在，对于别人的误解，我不在乎也不想去辩解，我信任的人误会我，我会觉得挺好的，原来我在你心里是这样的人。
鱼那么相信水，水却煮了鱼;叶子那么信任风，风却吹落了叶;在自己的世界里独善其身，取悦自己，在别人的世界里顺其自然。
3.看到过这样一段话:“我希望你努力，不是为了要跟别人比成绩，而是因为，我希望你将来拥有选择的权利，选择有意义的生活，而不是被迫谋生。
当我们努力之后，我们才有机会不拘泥于方寸之地，不用只过着毫无新意、一眼望到头、没任何期待的日子。拥有选择权，我们才有底气和实力去选择我们想要的生活。
哈希表：
哈希表的含义：
上面是百度百科的说法；
散列表（Hash table，也叫哈希表），是根据键（Key）而直接访问在内存储存位置的数据结构。也就是说，它通过计算出一个==键值的函数==，将所需查询的数据==映射==到表中一个位置来让人访问，这加快了查找速度。这个映射函数称做==散列函数==，存放记录的数组称做散列表。
这是维基百科的解释，
一个通俗的例子是，为了查找电话簿中某人的号码，可以创建一个按照人名首字母顺序排列的表〈和建立人名z到首字母F(赏)的一个函数关系)，在首字母为W的表中查找“王”姓的电话号码，显然比宜直接查找就要快得多。这里使用人名作为关键字，“==取首字母”是这个例子中散列函数的函数法则F()==，存放首字母的表对应荀列表。关键字和函数法则理论上可以任意确定.
两者在对于哈希表的解释都不约而同的说了两点：==码值和映射==。
下面借助百度百科的这张图便于你的理解：
先建立一个哈希函数（设定一个范围），再将不同的数分别映射到哈希函数上。
哈希表的作用：
把一个复杂的数据结构（值域，数据）映射到[0,n];
n一般是10的五次方或者10的六次方
如将[0,10^9^]映射到[0,10^5^]
哈希表的思想：
1.映射
将一段较大的数组映射到一段相对较小的数组，当要查找一个元素的时候，可以根据这个元素所映射对应的位置进行直接查找，而不是遍历查找，这样就可以更加高效的完成查找功能。
注：哈希一般常用的是增加和查找功能，如果想要删除一个数据，也不是真正意义上的删除，而是设定一个布尔数值，布尔值为false时代表删除这个数据。
2.冲突：
我们可以从这个图上的得知：多个数据可能会映射到同一个数值的情况。
针对这个情况，处理冲突有多重方法，如：
1.拉链法：
2.开放寻址法
3.再散列法
4.建立一个公共溢出区
这里详细介绍一下：拉链法和开放寻址法
例题：
题目：
维护一个集合，支持如下几种操作：
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
拉链法：
1.先将原数组值域映射到哈希函数：
如果值域为[-10^9^,10^9^]，将其映射到[0,10^5^]
则 x mod10^5^ （mod是取模）这样就可以使其范围在[0,10^5^]，
上面的数值都是假设便于你的理解。
真正的代码应该是这样的：
int k = (x % N + N) % N;这个代码的意思是将x取余将x映射到[0,N]范围内。
因为在C++中如果负数取模后仍然是负数，因此需要==先取模后加上N再对N取模==其结果一定是一个正数。
2.建立一个槽，将映射的结果链接到槽上
如上图所示，假设11的映射为3,23的映射也是3，将11链接槽上的3，将23链接在11后面，这个使用的是链表的结构存储拉链。
3.取模的N要为质数，且尽可能地离2的整数次幂尽可能的远。
这样的取N冲突的概率是最小的。
代码：
#include <cstring>
#include <iostream>
using namespace std;
const int N = 100003;//这里可以自己写一个求大于100000第一个质数的代码求出即可
int h[N];//这是上面说的开一个槽
int e[N], ne[N], idx;//与槽链接的拉链，用链表存储，
//e[N]用来存值，ne[N]下一个的位置，idx表示当前移动到哪一个位置
void insert(int x)
{
int k = (x % N + N) % N;//k是哈希值
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;
scanf("%d", &n);
memset(h, -1, sizeof h);//将槽清空，空指针一般用-1来表示
while (n -- )
{
char op[2];
int x;
scanf("%s%d", op, &x);
if (*op == 'I') insert(x);
else
{
if (find(x)) puts("Yes");
else puts("No");
}
}
return 0;
}代码解析：
1.
const int N = 100003;//这里可以自己写一个求大于100000第一个质数的代码求出即可
int h[N];//这是上面说的开一个槽
int e[N], ne[N], idx;//与槽链接的拉链，用链表存储，
//e[N]用来存值，ne[N]下一个的位置，idx表示当前移动到哪一个位置2.
这里存一个字符用的是字符数组，读入字符串，而不是直接的一个字符进行存储，因为将其以一个字符串进行读入，这样scanf可以自动忽略掉空格和回车，这样可以降低出错概率。
3.
void insert(int x)
{
int k = (x % N + N) % N;//k是哈希值
e[idx] = x;
ne[idx] = h[k];
h[k] = idx ++ ;//插入操作，类似于头插
}这个是插入操作，类似于链表的头插。
下面做一个动图，便于你的理解：
最后
十分感谢你可以耐着性子把它读完和我可以坚持写到这里，送几句话，对你，也对我：
1.这些年来一直在提醒自己一件事，千万不要感动自己，大部分人看似努力，不过是愚蠢导致的。什么熬夜看书到天亮，连续几天只睡几个小时，多久没放假了。如果这些东西也值得炫耀，那么富士康流水线上任何一个人都比你努力多了。
人难免天生有自怜情绪，唯有时刻保持清醒，才看得清真正的价值在哪里。
2.这一生中有许多的人朝我走来，然后又匆匆忙忙的消失在人山人海中，那些人与我短暂交错，尾声潮落。从开始的不舍到最后的习以为常，便明白这是人生常态。真心待人，开始不再执着任何一段关系，即使是阶段性的陪伴，在相处的过程中我们开心就好，就活在当下。
海阔凭鱼跃，天高任鸟飞，路要朝前走，人要往前看。山林不向四季起誓，枯荣随缘，海洋不需对沙岸许诺，遇合尽兴。
3.见了太多糟糕的事情，反倒觉得一切都会好起来。心情不好就听歌，饿了就找吃的，怕黑就开灯，喜欢的东西就赚钱买。
有人紧握你的手就可能会松开，有人给你承诺也会有失言的时候，长大后才发现真正想要的东西总归要自己争取，只有自己才不会辜负自己。
顺其自然真的是我对当下的生活态度了，人就应该活在当下，把今天过得很积极明天一定不会太差。别想太多，好好生活，也许日子过着过着就有答案了。
最后如果觉得我写的还不错，请不要忘记==点赞==✌，==收藏==✌，加==关注==✌哦(｡･ω･｡)
愿我们一起加油，奔向更美好的未来，愿我们从懵懵懂懂的一枚==菜鸟==逐渐成为==大佬==。加油，为自己点赞！
