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