【常用算法总结——字符串哈希】

不念不忘少年蓝@ 2021-11-10 08:24 412阅读 0赞

# 一、哈希（hash）是什么 #

对于我来说，HASH就像一个加密软件，你输入一个值，他就会输出值，并且比之前的值更优，更方便。而这个值呢，就叫做**哈希值**。然后字符串哈希就是输入一个字符串，把它转成对应的HASH值就行了。

# 二，转换过程 #

对于每个字符串，我们通过一个固定的转换方式，使相同字符串的**哈希值一定相同，不同字符串的值尽量不同**。因为很可能存在两个不同的字符串哈希值一样的操作，我们称之为“**哈希冲突”**。

我们此处传换的方式，就是最常见的**进制哈希**，它的核心是**给出一个固定进制base，把字符串上面的每一个元素看成base进制的每一个数字，然后转换成十进制，最后的结果就是HASH值。最后我们只需要比较每一个字符串的HASH值就可以知道他们是不是同一个字符串。**

关于进制的选择，还是很自由的，但是**一定不要含有mod的质因子**（那你还模什么模），所以我们取进制和mod时，一般都是**质数**。但是简单的还是**利用unsigned long long，不手动进行取模，它溢出时会自动对2^64取模**

下面我利用【模板】字符串哈希 给大家介绍一下这两种**进制哈希：**

**——————————————————————————————————————————————————————————————**

### 题目描述 ###

如题，给定N个字符串（第i个字符串长度为Mi，字符串内包含数字、大小写字母，大小写敏感），请求出N个字符串中共有多少个不同的字符串。

### 输入输出格式 ###

**输入格式：**

第一行包含一个整数N，为字符串的个数。

接下来N行每行包含一个字符串，为所提供的字符串。

**输出格式：**

输出包含一行，包含一个整数，为不同的字符串个数。

**输入样例1**

5
    abc
    aaaa
    abc
    abcc
    12345

**输出样例1**

**———————————————————————————————————————————————————————————————**

## **　　1、自然溢出哈希** ##

**　　　　对于这个哈希，我们不对它取模，而是利用unsigned long long的溢出取模。****　　　**

1 #include<bits/stdc++.h>
     2 #define FAST std::ios::sync_with_stdio(false),std::cin.tie(0),std::cout.tie(0)
     3 using namespace std;
     4 typedef unsigned long long ull;//typedef专门把C++的值的类型改名字，和宏定义一个道理，如自带的int，char或者自定义的struct 
     5 int n,ans=1;//种类因为不搜第一个，所以初值是一 
     6 ull base=131;//进制数 
     7 int a[10001];//记录hash值 
     8 int hash(string s)
     9 {
    10     ull sum=0;//哈希值
    11     for(int i=0;i<s.size();i++)
    12     {
    13         sum=sum*base+(ull)(s[i]);//乘进制数加上这一位 
    14     }
    15     return sum;//返回hash值 
    16 }
    17 int main()
    18 {
    19     FAST;//优化输入输出 
    20     cin>>n;
    21     for(int i=1;i<=n;i++)
    22     {
    23         string s;//输入字符串 
    24         cin>>s;
    25         a[i]=hash(s);//给它hash值 
    26     }
    27     sort(a+1,a+1+n);//hash值排序 
    28     for(int i=2;i<=n;i++)
    29     {
    30         if(a[i]!=a[i-1])ans++;//不一样种类就加一 
    31     }
    32     cout<<ans;
    33 }

## 　　2、单哈希 ##

自定义取模的值就行了。

1 #include<bits/stdc++.h>
     2 #define FAST std::ios::sync_with_stdio(false),std::cin.tie(0),std::cout.tie(0)
     3 using namespace std;
     4 int mod=20160817;//神奇的数字（质数）但是交上去只能得80分，所以我们用一个大一点的质数（212370440130137957ll） 不要在意后面的两个符号，交上去就对了 
     5 int n,ans=1;
     6 long long base=131;
     7 int a[100001];
     8 int hash(string s)
     9 {
    10     int sum=0;//哈希值
    11     for(int i=0;i<s.size();i++)
    12     {
    13         sum=sum*base+(int)(s[i]);//乘进制数加上这一位 
    14         sum%=mod;//模一下 
    15     }
    16     return sum;//返回hash值 
    17 }
    18 int main()
    19 {
    20     FAST;//优化输入输出 
    21     cin>>n;
    22     for(int i=1;i<=n;i++)
    23     {
    24         string s;//输入字符串 
    25         cin>>s;
    26         a[i]=hash(s);//给它hash值 
    27     }
    28     sort(a+1,a+1+n);//hash值排序 
    29     for(int i=2;i<=n;i++)
    30     {
    31         if(a[i]!=a[i-1])ans++;//不一样种类就加一 
    32     }
    33     cout<<ans;
    34 }

### 　　很显然，大家看到上面的代码，还是有可能出现**哈希冲突**的情况，针对这种情况，我们要不就把模的数再大一点，要不就一下两种方式，来解决。 ###

## 　　1、无错哈希 ##

其实原理很简单，就是我们要记录每一个已经诞生的哈希值，然后对于每一个新的哈希值，我们都可以来判断是否和已有的哈希值冲突，如果冲突，那么可以将这个新的哈希值不断加上一个大质数，直到不再冲突（比如somebody’s birthday qwq）。

![1710567-20190716165354894-1138629737.png][]

但是，这种方法类似桶查找，但是桶查找的弊端2就会很恶心——数据过大，checkcheck数组无能为力来支持上亿个空间（弊端1是由于数据具有跳跃性，浪费最后的统计次数，但在此不是特别明显，就当我皮了一下qwq）————————————转自洛谷第一篇题解

## 　　2、多重哈希 ##

这其实就是你用不同的两种或多种方式哈希，然后分别比对每一种哈希值是否相同——显然是增加了空间和时间，但也确实增加了其正确性。

![1710567-20190716165447983-1437613490.png][]

1 #include<bits/stdc++.h>
     2 #define FAST std::ios::sync_with_stdio(false),std::cin.tie(0),std::cout.tie(0)
     3 using namespace std;
     4 int mod1=20160817;
     5 int mod2=19260817; 
     6 int n,ans=1;
     7 int base=131;
     8 struct node{
     9     int x,y;
    10 }a[100001];
    11 int hash1(string s)
    12 {
    13     int sum=0;
    14     for(int i=0;i<s.size();i++)
    15     {
    16         sum=base*sum+(int)(s[i]);
    17         sum%=mod1;
    18     }
    19     return sum;
    20 }
    21 int hash2(string s)
    22 {
    23     int sum=0;
    24     for(int i=0;i<s.size();i++)
    25     {
    26         sum=base*sum+(int)(s[i]);
    27         sum%=mod2;
    28     }
    29     return sum;//返回hash值 
    30 }
    31 bool sj(node x,node y)
    32 {
    33     return x.x<y.x;
    34 }
    35 int main()
    36 {
    37     FAST;//优化输入输出 
    38     cin>>n;
    39     for(int i=1;i<=n;i++)
    40     {
    41         string s;//输入字符串 
    42         cin>>s;
    43         a[i].x=hash1(s);//给它hash值 
    44         a[i].y=hash2(s);
    45     }
    46     sort(a+1,a+1+n,sj);//hash值排序 
    47     for(int i=2;i<=n;i++)
    48     {
    49         if(a[i].x!=a[i-1].x||a[i].y!=a[i-1].y)ans++;
    50     }
    51     cout<<ans;
    52 }

————————————转自洛谷第一篇题解

转载于:https://www.cnblogs.com/hualian/p/11195493.html

[1710567-20190716165354894-1138629737.png]: /images/20211109/2e40d1e03bff43f3b6d4ff6bed869dd6.png
[1710567-20190716165447983-1437613490.png]: /images/20211109/063fe86efd5a4c24b2498d7da74f6f53.png