哈希算法

前言

对于字符串的比较，如果我们想要判断这两个字符串是否相同，我们需要对字符串的每一个字符进行比较，但这实在是太费时了。那么有没有一种方法能让字符串的比较和数字的比较一样容易呢？哈希算法我为我们提供了思路。

---

单模哈希

原理

将字符串的ASCII码分别乘上a求和后再对b取模，最后得出Hash值，我们比较这两个字符串只需要比较它们的Hash值即可。 说明：a,b是任意设置的数，不过我们一般让b尽量大，因为b越大Hash值的情况越多，出现两个不同字符串的Hash值越小，而a是为了防止不同位数的字符串Hash值相同。

缺点

看完原理我们就会发现哈希算法其实并不算完全严谨的算法，它是通过使不同字符串Hash值相同的概率趋近于0来保证字符串比较的正确性。

例题1：HDOJ 1004

题目

Problem Description

Contest time again! How excited it is to see balloons floating around. But to tell you a secret, the judges' favorite time is guessing the most popular problem. When the contest is over, they will count the balloons of each color and find the result.

This year, they decide to leave this lovely job to you.

Input

Input contains multiple test cases. Each test case starts with a number N (0 < N <= 1000) -- the total number of balloons distributed. The next N lines contain one color each. The color of a balloon is a string of up to 15 lower-case letters.

A test case with N = 0 terminates the input and this test case is not to be processed.

Output

For each case, print the color of balloon for the most popular problem on a single line. It is guaranteed that there is a unique solution for each test case.

Sample Input

5
green
red
blue
red
red
3
pink
orange
pink
0

Sample Output

red
pink

题解

#include<stdio.h>  
#include<string.h>  
int main()  
{  
    long long int m;  
    while(1) {  
        int n;  
        scanf("%d", &n);  
        if(n==0)break;  
        struct colors {  
            long long int sum;  
            int count;  
            char arr1[16];  
        };  
        struct colors color[1003];
        //初始化结构体  
        for(int i=1;i<=1001;i++){  
            color[i].sum=0;  
            color[i].count=0;  
        }  
        int st=0,max1=1;  
        char arr[16];  
        for (int i = 1; i <= n; i++) {  
            m = 0;  
            scanf("%s", arr);  
            char *t = arr;  
            //将不同的颜色转化为长整型进行计数（哈希）
            while (*t != '\0') {  
                m += *t + 133331;  
                t++;  
            }  
            int j;  
            for (j = 1; j <= st; j++) {  
                if (color[j].sum == m) {  
                    color[j].count++;  
                }  
            }  
            if (j == st + 1) {  
                st++;  
                strcpy(color[st].arr1, arr);  
                color[st].count++;  
                color[st].sum = m;  
            }  
            for (int j = 1; j <= st; j++) {  
                if (color[j].count > color[max1].count)max1 = j;  
            }  
        }  
        printf("%s\n", color[max1].arr1);  
    }  
    return 0;  
}

---

例题2：P3370 【模板】字符串哈希 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题目描述

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

友情提醒：如果真的想好好练习哈希的话，请自觉。

输入格式

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

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

输出格式

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

样例 #1

样例输入 #1

5
abc
aaaa
abc
abcc
12345

样例输出 #1

4

提示

对于 \(30\%\) 的数据：\(N\leq 10\)，\(M_i≈6\)，\(Mmax\leq 15\)。

对于 \(70\%\) 的数据：\(N\leq 1000\)，\(M_i≈100\)，\(Mmax\leq 150\)。

对于 \(100\%\) 的数据：\(N\leq 10000\)，\(M_i≈1000\)，\(Mmax\leq 1500\)。

样例说明：

样例中第一个字符串(abc)和第三个字符串(abc)是一样的，所以所提供字符串的集合为{aaaa,abc,abcc,12345}，故共计4个不同的字符串。

题解

根据哈希算法的原理构建代码。不过要注意的是，因为无符号长整型在数值溢出时会自动对\(2^{64}\)取模，因此就不手动取模了。

代码如下：

#include <stdio.h>  
#include <string.h>  
long long unsigned int arr[10003];  
char ch[10003];  
int main() {  
    int n;  
    int count=0;  
    scanf("%d",&n);  
    for(int i=1;i<=n;i++){  
        scanf("%s",ch);  
        int len=strlen(ch);  
        for(int j=0;j<len;j++){  
            arr[i]=arr[i]*13331+ch[j];  
        }  
        count++;  
        for(int k=1;k<i;k++){  
            if(arr[k]==arr[i]){  
                count--;  
                break;  
            }  
        }  
    }  
    printf("%d",count);  
}

---

双模哈希

即使我们减少了两个不同字符串Hash值大小相同的概率，但是不排除偶然出现的情况，为了进一步使哈希算法能够达到我们的预期，我们可以分别对两个数取模，并认定同时满足的时候两个字符串是相等的，这样及基本上不会出现问题。

因为没有找到适合的题目，这里就用C++给出示范代码。（看懂就行，代码没有实际意义）

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using ull=unsigned long long;
const int N=1e6+6,mod=1e9+7;
ull kpow1[N],hs1[N];//% 2^64
ll kpow2[N],hs2[N];//% mod
char s[N];int n;
pair<ull,ll>gethash(int l,int r){
	ull a=hs1[r]-hs1[l-1]*kpow1[r-l+1];
	ll b=hs2[r]-hs2[l-1]*kpow2[r-l+1];
	b=(b%mod+mod)%mod;
	return {a,b};
}//pair是C++中的配对，可以类比C语言中的结构体
int main(){
	kpow1[0]=kpow2[0]=1;
	for(int i=1;i<N;++i){
		kpow1[i]=kpow1[i-1]*13331;
		kpow2[i]=kpow2[i-1]*13331%mod;
	}
	scanf("%s",s+1);n=strlen(s+1);
	for(int i=1;i<=n;++i){
		hs1[i]=hs1[i-1]*13331+s[i];
		hs2[i]=(hs2[i-1]*13331+s[i])%mod;
	}
}

---

开阔视野（哈希算法在密码学中）

Hash的特点

易压缩：对于任意大小的输入x，Hash值的长度很小，在实际应用中，函数H产生的Hash值其长度是固定的。

易计算：对于任意给定的消息，计算其Hash值比较容易。

单向性：对于给定的Hash值，要找到使得在计算上是不可行的，即求Hash的逆很困难。在给定某个哈希函数H和哈希值H（M）的情况下，得出M在计算上是不可行的。即从哈希输出无法倒推输入的原始数值。这是哈希函数安全性的基础。

抗碰撞性：理想的Hash函数是无碰撞的，但在实际算法的设计中很难做到这一点。

有两种抗碰撞性：一种是弱抗碰撞性，即对于给定的消息，要发现另一个消息，满足在计算上是不可行的；另一种是强抗碰撞性，即对于任意一对不同的消息，使得在计算上也是不可行的。

高灵敏性：这是从比特位角度出发的，指的是1比特位的输入变化会造成1/2的比特位发生变化。消息M的任何改变都会导致哈希值H（M）发生改变。即如果输入有微小不同，哈希运算后的输出一定不同。

哈希算法有什么用途？

哈希算法可以检验信息是否是相同的，这样的优势可以节省重复文件传送的时间。

举一个生活中很平常的例子，我们在生活工作中会使用一些软件给别人传送文件数据，如果有人传送了一份文件给一个人，然后又有一个人传送了相同的文件给了另外一个人，那么这个社交软件在第二次传送文件的时候会对比两次传送的哈希值，发现是相同的，该软件就不会再次上传文件给服务器了。

除此之外，哈希算法还可以检验信息的拥有者是否真实。

比如，我们在一个网站注册一个账号，如果网站把密码保存起来，那这个网站不论有多安全，也会有被盗取的风险。但是如果用保存密码的哈希值代替保存密码，就没有这个风险了，因为哈希值加密过程是不不可逆的。

哈希算法会不会被破解？

从理论上说，哈希值是可以被获得的，但是对应的用户密码很难获得。

假设一个网站被攻破，黑客获得了哈希值，但仅仅只有哈希值还不能登录网站，他还必须算出相应的账号密码。

计算密码的工作量是非常庞大且繁琐的，严格来讲，密码是有可能被破译的，但破译成本太大，被成功破译的几率很小，所以基本是不用担心密码泄露的。

当然，黑客们还可以采用一种物理方法，那就是猜密码。他可以随机一个一个的试密码，如果猜的密码算出的哈希值正好与真正的密码哈希值相同，那么就说明这个密码猜对了。

密码的长度越长，密码越复杂，就越难以猜正确。如果有一种方法能够提高猜中密码的可能，那么可以算是哈希算法被破解了。

开阔视野内容转载自紫天峰的博客