赞
踩
在学习本节课之前,请大家思考这样一个问题:如果我们要在一个长度为 N N N的随机整数序列 A A A中统计每个数出现的次数,可以用什么方法?
不难想到,我们可以建立一个数组 ,然后将整数序列A中的元素映射到数组的下标,最后遍历整个数组即可统计出随机整数序列 A A A中每个数出现的次数。但是如果数列 A A A中数比较大呢?我们就可以借助Hash表来解决这个问题。
散列表(Hash table,也叫哈希表),是根据键(Key)而直接访问在内存储存位置的数据结构。也就是说,它通过计算一个关于键值的函数,将所需查询的数据映射到表中一个位置来访问记录,这加快了查找速度当我们要对若干复杂信息进行统计时,可以用Hash函数把这些复杂信息映射到一个容易维护的值域内。
比如刚才那个问题,当N过于大时,我们可以设计Hash函数为 H ( x ) = ( x m o d P ) + 1 H(x)=(x\mod\ P)+1 H(x)=(xmod P)+1,其中P是一个较大的质数,但不超过N,这样这个Hash函数就把数列 A A A中的值映射到了不同的区域进行储存,然后继续进行后面的操作。
总的来说, 其基本原理是:使用一个下标范围比较大的数组来存储元素。可以设计一个函数(哈希函数,也叫做散列函数),使得每个元素的关键字都与一个函数值(即数组下标,hash值)相对应,于是用这个数组单元来存储这个元素。
但是,由于值域变简单、范围变小,有可能造成两个不同的原始信息被Hash函数映射为相同的值,这种情况叫做Hash冲突,我们下面会讲解如何处理这种冲突。
总结一下,Hash表主要包括两个基本操作:
1.计算Hash函数的值
2.定位到对应链表中依次遍历、比较。
hash函数构造原则
1.简答易算
2.能够使地址均匀分布
拉链法是借助邻接表实现的,当目标元素经过Hash函数计算后所得到的值与之前的元素计算得出的值相同,就将其插入以这个Hash值开头的链表中去。
例如:将$19\ 1\ 23\ 14\ 55\ 68\ 11\ 86\ 37\ $要存储在表长 11 11 11的数组中,其中 H ( k e y ) = k e y M O D 11 H(key)=key\ MOD \ 11 H(key)=key MOD 11,很显然这种Hash方式会造成Hash冲突,所以我们可以用下图的方式存储在Hash表中。
#include<iostream> #include<cstring> using namespace std; const int N=11; int h[N],e[N],ne[N],idx=0;//分别存储链表头,数值,指向的下一元素编号 void insert(int x){//插入 e[++idx]=x; int tmp=(x%N+N)%N; ne[idx]=h[tmp]; h[tmp]=idx; } bool query(int x){//查找 int tmp=(x%N+N)%N; for(int i=h[tmp];i!=-1;i=ne[i]){ if(e[i]==x) return true; } return false; } int main(){ int n,x; cin>>n; memset(h,-1,sizeof h); while(n--){ cin>>x; insert(x); } }
开放寻址法指的是当你发现这个位置已经被占用后,就按照一定的喜好去寻找没有被占用的位置。寻找新的位置的方法主要有以下三种:
一旦出现冲突后,就尝试后面邻接的位置,直到找到没有被占用的位置为止。但是这种方法虽然解决了当前的冲突,但可能会造成其他冲突,出现数据聚集现象
int h[N];
// 如果x在哈希表中,返回x的下标;如果x不在哈希表中,返回x应该插入的位置
int find(int x)
{
int t = (x % N + N) % N;
while (h[t] != null && h[t] != x)
{
t ++ ;
if (t == N) t = 0;
}
return t;
}
双重散列是用于开放寻址法的最好方法之一,所谓双重散列,意思就是不仅要使用一个散列函数。我们需要使用两个散列函数 h a s h 1 ( k e y ) hash1(key) hash1(key), h a s h 2 ( k e y ) hash2(key) hash2(key).我们先用第一个散列函数,如果发生冲突,则再利用第二个散列函数。也就是说定义两个hash函数,一个值映射成两个hash值存储在map里,只有两个都对应上了,才映射成功,这种主要是为了避免出题人卡你。
即将一个字符串转化成一个整数,并保证字符串不同,得到的哈希值不同,这样就可以用来判断一个该字串是否重复出现过。
一般来说P=131或者13331,q= 2 64 2^{64} 264时最不容易发生冲突
hash方法:字符串前缀Hash法
1.将字符串看成是一个P进制的数,然后把26个字母映射成1-26的数字,利用公式
H a s h [ i ] = ( H a s h [ i − 1 ] ∗ p + i d x ( s i ) ) m o d q Hash[i] = (Hash[i-1]*p+idx(si))\ mod \ q Hash[i]=(Hash[i−1]∗p+idx(si)) mod q
即可将该字符串的hash值计算出来
2.为了能够任意计算任意范围的hash值需要按照
H a s h [ r ] = h a s h [ r ] − H a s h [ l − 1 ] ∗ p ( r − l + 1 ) Hash[r] =hash[r]- Hash[l-1]*p^{(r-l+1)} Hash[r]=hash[r]−Hash[l−1]∗p(r−l+1)
小技巧:这里可以将数据类型定义成unsigned long long 类型,产生溢出时相当于自动对 2 64 2^{64} 264进行取模,提高效率,但有时会遭到恶毒的出题人卡你哈哈哈
例题:
给定一个长度为 n 的字符串,再给定 m 个询问,每个询问包含四个整数l1,r1,l2,r2,请你判断 [l1,r1] 和 [l2,r2] 这两个区间所包含的字符串子串是否完全相同。
字符串中只包含大小写英文字母和数字。
#include<bits/stdc++.h> using namespace std; typedef unsigned long long ULL; const int N=100010,P=131; ULL h[N],p[N]; char str[N]; int n,m; ULL get1(int l,int r) { return h[r]-h[l-1]*p[r-l+1]; } int main() { cin>>n>>m>>str+1; p[0]=1; for(int i=1;i<=n;i++) { h[i]=h[i-1]*P+str[i]; p[i]=p[i-1]*P; } int l1,r1,l2,r2; ULL temp1,temp2; while(m--) { cin>>l1>>r1>>l2>>r2; temp1=get1(l1,r1); temp2=get1(l2,r2); if(temp1==temp2) cout<<"Yes"<<endl; else cout<<"No"<<endl; } }
判断字符串中两个字串是否相等(最基本的用法)
判断给定的一些字符串不同的字串有多少
判断回文串(求最长回文子串)
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。