Hash初探

发表于 | | 浏览 次

Hash，一般翻译做“散列”，也有直接音译为“哈希”的，就是把任意长度的输入（又叫做预映射， pre-image），通过散列算法，变换成固定长度的输出，该输出就是散列值。这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，所以不可能从散列值来确定唯一的输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。

什么是Hash?

hash就是把不同长度的数据映射到有限长度的域上. 直观起来解释,就是对一串数据m(message)进行杂糅, 输出另一段固定长度的数据h(hash),作为这段数据的特征(指纹). 即这两段数据都可以根据某种对应法则,相互唯一的转换(一对一).

也就是说,无论数据块m有多大, 其输出值h为固定长度. 到底这是什么原理? 将m分成固定长度(如128位),依次进行hash运算,然后用不同的方法进行迭代即可(如前一块的hash值与后一块的hash值进行异或运算). 如果不够128位怎么办? 用0补全或者用1补全都行(主要是针对它制定一个补全的规则,处处遵守就行),约定好.

常用的加密算法md5 sha1都是hash算法

算法都有一定的评估标准,比如时间复杂度、空间复杂度。hash算法也有他的评估标准。

  • 抗碰撞能力：对于任意两个不同的数据块，其hash值相同的可能性极小；对于一个给定的数据块，找到和它hash值相同的数据块极为困难。
  • 抗篡改能力：对于一个数据块，哪怕只改动其一个比特位，其hash值的改动也会非常大。
1
2
MD5("version1") = "966634ebf2fc135707d6753692bf4b1e";
MD5("version2") = "2e0e95285f08a07dea17e7ee111b21c8";

如上例，尽管version1 version2这两个字符串只相差一个字符，但是他们的hash值却差别很大，这就是 抗篡改能力

我们在网上下载文件的时候，有的东西会提供hash值，用于检验我们下载的东西是否被别人篡改过，比如下图的tomcat

tomcat-download

这是 apache-tomcat-8.5.19.zip.md5 文件里的内容

tomcat提供的md5hash值

这是对 apache-tomcat-8.5.19.zip 这个文件进行md5运算之后的结果

tomcat下载文件计算出的md5hash值

这里 是一个计算大文件hash的工具

计算出来的hash值和tomcat厂商提供的hash值一致，说明文件没被篡改

在用到hash进行管理的数据结构中，比如hashmap，hash值（key）存在的目的是加速键值对的查找，key的作用是为了将元素适当地放在各个桶里，对于抗碰撞的要求没有那么高。换句话说，hash出来的key，只要保证value大致均匀的放在不同的桶里就可以了。但整个算法的set性能，直接与hash值产生的速度有关，所以这时候的hash值的产生速度就尤为重要，以JDK中的String.hashCode()方法为例： 

1
2
3
4
5
6
7
8
9
10
11
12
13
public int hashCode() {
        int h = hash;
        //hash default value : 0 
        if (h == 0 && value.length > 0) {
        //value : char storage
            char val[] = value;
            for (int i = 0; i < value.length; i++) {
                h = 31 * h + val[i];
            }
            hash = h;
        }
        return h;
    }

很简洁的一个乘加迭代运算，在不少的hash算法中，使用的是异或+加法进行迭代，速度和前者差不多。

哈希表

哈希表是一种能实现关联数组的抽象数据结构，能把很多「键」映射到很多「值」上。哈希表使用哈希函数来计算索引，一个索引对应一个值。

哈希表的简单应用

先给出一道简单的题目

题目链接是 https://www.patest.cn/contests/pat-a-practise/1050

题意大概是这样的, 有两个字符串s1和s2,而且这两个字符串都只包含可见的ascii字符、空格和字符串结束符，字符川的长度保证不会超过10000。题目要求，只要s2中出现的字符，s1中都不能出现，s1要去掉s2中出现的字符，然后输出。

假如 s1=They are students. , s2=aeiou

首先我们要知道s2中出现了哪些字符，然后把它保存在数组里。那么此数组就是s2_arr=['a','e','i','o','u'],然后遍历s1的每一位，看看每一位是否在数组 s2_arr中，这样时间复杂度就是 O(n)

下面给出一种解决方案

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
#include <stdio.h>  
#include <string.h>  
   
#define N 10002  
  
char str1[N] ,str2[N];  
int ascii[128];//表示128个ASCII码表   
  
int main(){  
    gets(str1);  
    gets(str2);//输入两个字符串  
    int len1 = strlen(str1),len2 = strlen(str2);//求出两个字符串的长度  
      
    int i = 0 ;  
    for(i = 0;i < len2; i++){  
        ascii[str2[i]]++;   
    }  
      
    for(i = 0;i<len1;i++){  
        if(ascii[str1[i]]>0){  
            continue;  
        } else{  
            printf("%c",str1[i]);  
        }  
    }     
}

使用ascii[]这个数组来存储s2中出现的字符的acsii码值，出现一次，下标等于该字符ascii码值的元素值就加一。判断s1的字符是不是在s2中的时候，这种处理方式的复杂度是O(1)

这是一种典型的用空间换时间的算法

参考链接

https://www.zhihu.com/question/26762707

If you think the content is useful to you.