初识字符串哈希（Hash）

大家好，欢迎来到IT知识分享网。

目录

1.字符串哈希的介绍

2.自然溢出哈希

3.单哈希

4.双哈希

5.例题分析

1.自然溢出哈希AC代码

2.单哈希AC代码

3.双哈希AC代码

6.总结

1.字符串哈希的介绍

字符串哈希是一种将字符串映射为一个固定长度的整数或哈希值的技术。它的主要目的是加速字符串比较和搜索操作，通常用于在大量字符串中快速查找特定字符串或判断两个字符串是否相等。

字符串哈希的基本思想是将字符串视为一个较大的数字，然后使用哈希函数将其转换为一个较小的、固定长度的整数。这个哈希值可以作为字符串的”指纹”，用于快速比较字符串是否相等或用于在哈希表等数据结构中进行快速查找。

既然要保证这个哈希值可以作为某个字符串的“指纹”，那就证明这个哈希值是独一无二的，不存在两个不同的字符串有相同的哈希值的情况。

那么现在来介绍三种求哈希值的方法。

基本每种方法都要使用到base 和 mod，全部它们两都要是素数，base用于进制转换，mod用与取模，一般这样得到的一个数出重的概率是相当低的，当然base和mod要尽可能大，不然会出重概率会提升。

2.自然溢出哈希

先来看一下自然溢出法的代码公式。

ull Hash(string s) { ull ans=0; for(int i=0;i<s.size();i++){ ans=ans*base+(ull)s[i]; } return ans; }

这里的base我们给它定义的是131，也是符合素数的要求。

公式：

base=素数，ull=unsigned long long

ans=ans*base+(ull)s[i]

3.单哈希

其实单哈希和自然溢出哈希差不多，就是单哈希多了一个取模操作。

ull Hash(string s) { ull ans=0; for(int i=0;i<s.size();i++){ ans=(ans*base+(ull)s[i])%mod; } return ans; }

公式：

base=131，mod=01，ull=unsigned long long

ans=(ans*base+(ull)s[i])%mod

4.双哈希

既然是叫双哈希了，那就是两个单哈希组成的咯。

注意：里面的base1，base2，mod1，mod2都不一样，但是都是素数。

ull Hash1(string s) { ull ans=0; for(int i=0;i<s.size();i++){ ans=(ans*base1+(ull)s[i])%mod1; } return ans; } ull Hash2(string s) { ull ans=0; for(int i=0;i<s.size();i++){ ans=(ans*base2+(ull)s[i])%mod2; } return ans; } 

这时候我们可以给映射的整数数组搞一个结构体，里面放两个参数。

公式：

base1=131，base2=171，mod1=01，mod2=07

ans1=(ans1*base1+(ull)s[i])%mod1

ans2=(ans2*base2+(ull)s[i])%mod2

5.例题分析

例题链接

数据输入：

5 abc aaaa abc abcc 12345

1.自然溢出哈希AC代码

#include<bits/stdc++.h> #define ull unsigned long long using namespace std; const ull base=131; const ull mod=0ll; ull a[]; int n; string s[]; ull Hash(string s) { ull ans=0; for(int i=0;i<s.size();i++){ ans=ans*base+(ull)s[i]; } return ans; } int main() { cin>>n; for(int i=0;i<n;i++){ cin>>s[i]; } for(int i=0;i<n;i++){ a[i]=Hash(s[i]); } sort(a,a+n); ull ans=1; for(int i=1;i<n;i++){ if(a[i]!=a[i-1]) ans++; } cout<<ans<<endl; return 0; } 

2.单哈希AC代码

#include<bits/stdc++.h> #define ull unsigned long long using namespace std; const ull base=131; const ull mod=11; ull a[]; int n; string s[]; ull Hash(string k) { ull ans=0; for(int i=0;i<k.size();i++){ ans=(ans*base+(ull)k[i])%mod; } return ans; } int main() { cin>>n; for(int i=0;i<n;i++){ cin>>s[i]; } for(int i=0;i<n;i++){ a[i]=Hash(s[i]); } sort(a,a+n); ull ans=1; for(int i=1;i<n;i++){ if(a[i]!=a[i-1]) ans++; } cout<<ans<<endl; return 0; } 

3.双哈希AC代码

#include<bits/stdc++.h> #define ull unsigned long long using namespace std; const ull base1=131; const ull base2=171; const ull mod1=01; const ull mod2=07; struct node{ ull x,y; }a[]; int n; string s[]; ull Hash1(string s) { ull ans=0; for(int i=0;i<s.size();i++){ ans=(ans*base1+(ull)s[i])%mod1; } return ans; } ull Hash2(string s) { ull ans=0; for(int i=0;i<s.size();i++){ ans=(ans*base2+(ull)s[i])%mod2; } return ans; } bool cmp(node a,node b) { return a.x+a.y<b.x+b.y; } int main() { cin>>n; for(int i=0;i<n;i++){ cin>>s[i]; } for(int i=0;i<n;i++){ a[i].x=Hash1(s[i]); } for(int i=0;i<n;i++){ a[i].y=Hash2(s[i]); } sort(a,a+n,cmp); ull ans=1; for(int i=1;i<n;i++){ if(a[i].x!=a[i-1].x&&a[i].y!=a[i-1].y) ans++; } cout<<ans<<endl; return 0; } 

6.总结

运行速度：

自然溢出哈希>单哈希>双哈希

安全性：

双哈希>单哈希=自然溢出哈希

当然精准度也与base和mod定义的大小有关。