怎么在百度建设一个网站,网站反连接,淘宝客手机网站搭建,wordpress对接静态网页作者#xff1a;指针不指南吗 专栏#xff1a;算法篇 #x1f43e;或许会很慢#xff0c;但是不可以停下来#x1f43e; 文章目录1.定义2.优点3.数字哈希3.1拉链法3.2开放寻址法3.3 例题4.字符串哈希1.定义 哈希表#xff08;Hash table#xff09;#xff0c;是根据键… 作者指针不指南吗 专栏算法篇 或许会很慢但是不可以停下来 文章目录1.定义2.优点3.数字哈希3.1拉链法3.2开放寻址法3.3 例题4.字符串哈希1.定义 哈希表Hash table是根据键Key直接访问在内存存储位置的数据结构。也就是说它通过计算一个关于键值的函数将所需查询的数据映射到表中一个位置来访问记录这样就加快了查找速度。这个映射函数称做散列函数哈希函数存放记录的数组称做散列表。 就是把一堆庞大数据映射到一个小的数据结构中比如把0~10910^9109 映射到0~10510^5105 的数组中。 h(x)一般用x mod nn表示数组大小一般取一个质数这样冲突出现的概率比较小。 冲突当两个不一样的数通过哈希函数映射成一个数的时候我们无法确定这两个数了被称为冲突。
2.优点
查找速度快 哈希表是种数据结构它可以提供快速的插入操作和查找操作。 不论哈希表中有多少数据插入和删除只需要接近常量的时间即 O( 1 ) 的时间复杂度。 哈希表运算得非常快在计算机程序中如果需要在一秒种内查找上千条记录通常使用哈希表例如拼写检查器)哈希表的速度明显比树快树的操作通常需要O(N)的时间级。哈希表不仅速度快编程实现也相对容易。
3.数字哈希
数字哈希是数字到数字的映射关系。
3.1拉链法 操作 开一个一维数组来存储哈希值 添加值处理冲突 把每一个数组变量看成是一个槽在槽上拉一个链映射 h(x)出来是对应在槽即添加在其链上。 每条链上的数的个数期望值是2个 整个数组链表大致地样子 将一个数插在链表上面 查找值 映射h(x)一下 x 遍历一下它对应 槽的链上有没有它 删除值 我们不会直接把它删掉而是定义一个标记 bool在对应想要删除的数值上打一个标记。 代码实现 向哈希表中插入一个数 void insert(int x)
{int k(x%NN)%N; //哈希映射函数先取模再加N再取模是为了保证最后的值是正数e[idex]x; //插在对应槽的链表里面ne[idex]h[k];h[k]idex;
}在哈希表中查询某个数是否存在 bool find(int x)
{int k(x%NN)%N; //先找出对应的槽for(int ih[k];i!-1;ine[i]){ //遍历槽的链表查找是否有相同的值if(e[i]x) return true;}return false;
}3.2开放寻址法 操作 只开一个一维数组数组的大小按经验来说一般是 数据范围的2~3倍先看一下对应的槽里有没有数有数的话找下一槽直到找到没有数的槽 代码实现 int h[N];
int null0x3f3f3f3f;
// 如果x在哈希表中返回x的下标如果x不在哈希表中返回x应该插入的位置
int find(int x)
{int k (x % N N) % N; //函数映射到槽上while (h[k] ! null h[k] ! x) //这个槽里面有数并且·这个数不是我循环继续{k ; //找下一个槽if (k N) k 0; //如果找到最后了返回0继续寻找}return t;
}添加元素 find(x)x x不在哈希表里面find的返回值就是该插入的位置 查找元素 int k find(x) 如果x不在哈希表中返回x应该插入的位置,则该位置为空 h[k]null 说明哈希表里面没有这个值 删除元素 和拉链法一样定义一个bool变量用作标记
3.3 例题 维护一个集合支持如下几种操作 I x插入一个数 xQ x询问数 x 是否在集合中出现过 现在要进行 N 次操作对于每个询问操作输出对应的结果。 输入格式 第一行包含整数 N表示操作数量。 接下来 N 行每行包含一个操作指令操作指令为 I xQ x 中的一种。 输出格式 对于每个询问指令 Q x输出一个询问结果如果 x 在集合中出现过则输出 Yes否则输出 No。 每个结果占一行。 数据范围 1 ≤ N ≤ 10510^5105 −10910^9109 ≤ x ≤ 10910^9109 输入样例 5
I 1
I 2
I 3
Q 2
Q 5输出样例 Yes
No方法一拉链法 #includebits/stdc.husing namespace std;const int N100003; // N取100010的最大质数100003
int h[N],ne[N],e[N],idex; //h表示数组中的槽剩下的表示链表有关
int n;void insert(int x) //添加值的函数
{int k(x%NN)%N; //哈希映射函数先取模再加N再取模是为了保证最后的值是正数e[idex]x; //插在对应槽的链表里面ne[idex]h[k];h[k]idex;
}bool find(int x) //查找值的函数
{int k(x%NN)%N; //先找出对应的槽for(int ih[k];i!-1;ine[i]){ //遍历槽的链表查找是否有相同的值if(e[i]x) return true;}return false;
}int main()
{scanf(%d,n ); //读入操作次数memset(h,-1,sizeof h); //清空数组空指针一般用 -1 表示char op[2]; //读入一个字符的时候直接用字符数组读入降低出错率int x; while(n--){scanf(%s%d,op,x); //读入要操作的类型以及数据if(op[0]I) insert(x);else{if(find(x)) puts(Yes);else puts(No);}}return 0;
}方法二开放寻址法 #includeiostream
#includecstringusing namespace std;const int N200003,null0x3f3f3f3f; //N数组长度一般为数据范围的2~3倍且为质数null表示空指针
int h[N]; //h表示槽的位置
int n;// 如果x在哈希表中返回x的下标如果x不在哈希表中返回x应该插入的位置
int find(int x)
{int k (x % N N) % N; //函数映射到槽上while (h[k] ! null h[k] ! x) //这个槽里面有数并且·这个数不是我循环继续{k ; //找下一个槽if (k N) k 0; //如果找到最后了返回0继续寻找}return t;
}int main()
{scanf(%d,n);memset(h,0x3f,sizeof h);while(n--){char op[2];int x;scanf(%s%d,op,x);int kfind(x);if(*opI) h[k]x; //往哈希表里面插入元素else{if(h[k]!null) puts(Yes); //在哈希表里面寻找元素else puts(No);}}return 0;
}4.字符串哈希
字符串哈希是字符串到数字的映射关系。
我认为这个记住模板就行。 映射 我们使用的映射关系是字符串到P进制数的映射关系P是任意的保证映射是一一对应的不能有冲突。使冲突最小化我们取P131 或者 P13331 并且把字符串映射到 2642^{64}264 范围内的数字 操作 先预处理出来字符串所有前缀的哈希 防止冲突不能映射成0。 求一段区间的哈希值 哈希映射的时候要对数值取N的模unsigned long long 的范围就是2642^{64}264 我们可以用它来巧妙地解决取模因为正好 超过 unsigned long long 就会溢出。 代码模板 typedef unsigned long long ULL;
ULL h[N], p[N]; // h[k]存储字符串前k个字母的哈希值, p[k]存储 P^k mod 2^64// 初始化
p[0] 1;
for (int i 1; i n; i )
{h[i] h[i - 1] * P str[i];p[i] p[i - 1] * P;
}// 计算子串 str[l ~ r] 的哈希值
ULL get(int l, int r)
{return h[r] - h[l - 1] * p[r - l 1];
}例题 给定一个长度为 n 的字符串再给定 m 个询问每个询问包含四个整数 l1,r1,l2,r2请你判断 [ l1 , r1 ] 和 [l2,r2]这两个区间所包含的字符串子串是否完全相同。 字符串中只包含大小写英文字母和数字。 输入格式 第一行包含整数 n 和 m表示字符串长度和询问次数。 第二行包含一个长度为 n 的字符串字符串中只包含大小写英文字母和数字。 接下来 m 行每行包含四个整数 l1,r1,l2,r2表示一次询问所涉及的两个区间。 注意字符串的位置从 1 开始编号。 输出格式 对于每个询问输出一个结果如果两个字符串子串完全相同则输出 Yes否则输出 No。 每个结果占一行。 数据范围 1≤n,m≤10510^5105 输入样例 8 3
aabbaabb
1 3 5 7
1 3 6 8
1 2 1 2输出样例 Yes
No
Yes#includebits/stdc.h
using namespace std;typedef unsigned long long ULL; //ULL代替取模映射哈希函数const int N100010,P131;
ULL p[N],h[N]; //p表示前缀哈希h表示哈希值int n,m;
char str[N];ULL get(int l,int r) //求某段区间的哈希值
{return h[r]-h[l-1]*p[r-l1]; //右端点的前缀哈希值-左端-1的前缀和哈希值*区间进制
}int main()
{scanf(%d%d%s,n,m,str1); //预处理直接从str1 开始输入后面涉及-1操作p[0]1; //初始化因为后面涉及-1和乘法for(int i1;in;i){p[i]p[i-1]*P; //哈希映射P进制h[i]h[i-1]*Pstr[i]; //前缀哈希值}while(m--){int l1,r1,l2,r2;scanf(%d%d%d%d,l1,r1,l2,r2);if(get(l1,r1)get(l2,r2)) puts(Yes); //区间哈希值相等则区间的字符相等else puts(No);}return 0;
}之后补充 STL 中哈希表用法
