当前位置:   article > 正文

Hash——字符串Hash

字符串hash

Hash

在学习本节课之前,请大家思考这样一个问题:如果我们要在一个长度为 N N N的随机整数序列 A A A中统计每个数出现的次数,可以用什么方法?

不难想到,我们可以建立一个数组 ,然后将整数序列A中的元素映射到数组的下标,最后遍历整个数组即可统计出随机整数序列 A A A中每个数出现的次数。但是如果数列 A A A中数比较大呢?我们就可以借助Hash表来解决这个问题。

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表工作原理

Hash函数的构造

hash函数构造原则

1.简答易算

2.能够使地址均匀分布

直接定址法 H(key)=a*key+b
除留余数法 H(key)=key MOD p,p<=m (最简单,最常用)p的选取尽量是一个质数,并且离2的整次幂尽可能的远
Hash冲突的解决
拉链法

拉链法是借助邻接表实现的,当目标元素经过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 Hkey=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);
	}
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
开放寻址法

开放寻址法指的是当你发现这个位置已经被占用后,就按照一定的喜好去寻找没有被占用的位置。寻找新的位置的方法主要有以下三种:

线性勘测法

一旦出现冲突后,就尝试后面邻接的位置,直到找到没有被占用的位置为止。但是这种方法虽然解决了当前的冲突,但可能会造成其他冲突,出现数据聚集现象

    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;
    }


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
双重哈希

双重散列是用于开放寻址法的最好方法之一,所谓双重散列,意思就是不仅要使用一个散列函数。我们需要使用两个散列函数 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里,只有两个都对应上了,才映射成功,这种主要是为了避免出题人卡你。

字符串hash

即将一个字符串转化成一个整数,并保证字符串不同,得到的哈希值不同,这样就可以用来判断一个该字串是否重复出现过。

一般来说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[i1]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[l1]p(rl+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;
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
字符串hash的用法
  • 判断字符串中两个字串是否相等(最基本的用法)

  • 判断给定的一些字符串不同的字串有多少

  • 判断回文串(求最长回文子串)

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/2023面试高手/article/detail/350851
推荐阅读
相关标签
  

闽ICP备14008679号