哈希函数介绍 | 哈希算法 -- 算法 -- IT技术博客大学习 -- 共学习共进步！

您现在的位置：首页 --> 算法 --> 哈希函数介绍 | 哈希算法

哈希函数介绍 | 哈希算法

浏览:781次出处信息

什么是哈希

在记录的关键字与记录的存储地址之间建立的一种对应关系叫哈希函数。
哈希函数就是一种映射，是从关键字到存储地址的映射。
通常，包含哈希函数的算法的算法复杂度都假设为O(1)，这就是为什么在哈希表中搜索数据的时间复杂度会被认为是”平均为O(1)的复杂度”.

基本概念

在讲解具体内容前，首先我们要清楚以下几个概念：
1. 冲突（碰撞）
对于不同的关键字ki、kj，若ki != kj，但H(ki) = H(kj)的现象叫冲突(collision) ，即不同的输入却有相同的输出。我们应该尽量避免冲突，因为冲突不仅会使我们在查找的时候效率变慢，还甚至会被攻击者利用从而大量消耗系统资源。
至于冲突的解决方案有很多种，具体可以参考这篇哈希表针对冲突的两种方式优缺点是什么?。

哈希函数的应用

哈希算法广泛应用于很多场景，例如安全加密和数据结构中哈希表的查找，布隆过滤器和负载均衡（一致性哈希）等等。
下面介绍几个常用的哈希算法。

加密哈希算法

在安全方面应用主要体现在以下三个方面：
（1) 文件校验
（2) 数字签名
（3) 鉴权协议

在nodejs中我们可以使用原生crypto模块对数据进行加密，crypto.getHashes()查看支持的哈希算法。

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
constcrypto=require('crypto');
console.log(crypto.getHashes());
/*
[ 'DSA',
  'DSA-SHA',
  'DSA-SHA1',
  'DSA-SHA1-old',
  'RSA-MD4',
  'RSA-MD5',
  'RSA-MDC2',
  'RSA-RIPEMD160',
  'RSA-SHA',
  'RSA-SHA1',
  'RSA-SHA1-2',
  'RSA-SHA224',
  'RSA-SHA256',
  'RSA-SHA384',
  'RSA-SHA512',
  'dsaEncryption',
  'dsaWithSHA',
  'dsaWithSHA1',
  'dss1',
  'ecdsa-with-SHA1',
  'md4',
  'md4WithRSAEncryption',
  'md5',
  'md5WithRSAEncryption',
  'mdc2',
  'mdc2WithRSA',
  'ripemd',
  'ripemd160',
  'ripemd160WithRSA',
  'rmd160',
  'sha',
  'sha1',
  'sha1WithRSAEncryption',
  'sha224',
  'sha224WithRSAEncryption',
  'sha256',
  'sha256WithRSAEncryption',
  'sha384',
  'sha384WithRSAEncryption',
  'sha512',
  'sha512WithRSAEncryption',
  'shaWithRSAEncryption',
  'ssl2-md5',
  'ssl3-md5',
  'ssl3-sha1',
  'whirlpool' ]
*/
 

除了我们常用的md5，sha-1，sha-2族外，还有像DSA-SHA1，RSA-SHA1，sha1WithRSAEncryption，其中sha1WithRSAEncryption和RSA-SHA1等价，DSA和RSA都是加密算法，DSA和RSA的区别在于，DSA用于签名，而RSA可用于签名和加密。

下面简单介绍下几种比较常用的加密哈希算法：

1、 MD5
MD5即Message-Digest Algorithm 5（信息-摘要算法5），用于确保信息传输完整一致。是计算机广泛使用的杂凑算法之一，主流编程语言普遍已有MD5实现。将数据（如汉字）运算为另一固定长度值，是杂凑算法的基础原理，MD5的前身有MD2、MD3和MD4。
MD5是输入不定长度信息，输出固定长度128-bits的算法。经过程序流程，生成四个32位数据，最后联合起来成为一个128-bits散列。基本方式为，求余、取余、调整长度、与链接变量进行循环运算。得出结果。
NodeJS中使用MD5：

1
2
3
4
5
6
7
varhash=crypto.createHash('md5');
hash.update('test');
console.log(hash.digest('hex'));    // 098f6bcd4621d373cade4e832627b4f6
varhash=crypto.createHash('md5');
hash.update('test1');
console.log(hash.digest('hex'));    // 5a105e8b9d40e1329780d62ea2265d8a
 

MD5一度被广泛应用于安全领域。但是在2004年王小云教授公布了MD5、MD4、HAVAL-128、RIPEMD-128几个 Hash函数的碰撞。这是近年来密码学领域最具实质性的研究进展。使用他们的技术，在数个小时内就可以找到MD5碰撞。使本算法不再适合当前的安全环境。目前，MD5计算广泛应用于错误检查。例如在一些BitTorrent下载中，软件通过计算MD5和检验下载到的碎片的完整性。

2、SHA-1
SHA-1曾经在许多安全协议中广为使用，包括TLS和SSL、PGP、SSH、S/MIME和IPsec，曾被视为是MD5的后继者。
SHA-1是如今很常见的一种加密哈希算法，HTTPS传输和软件签名认证都很喜欢它，但它毕竟是诞生于1995年的老技术了(出自美国国安局NSA)，已经渐渐跟不上时代，被破解的速度也是越来越快。
微软在2013年的Windows 8系统里就改用了SHA-2，Google、Mozilla则宣布2017年1月1日起放弃SHA-1。
当然了，在普通民用场合，SHA-1还是可以继续用的，比如校验下载软件之类的，就像早已经被淘汰的MD5。

1
2
3
4
varhash=crypto.createHash('sha1');
hash.update('test');
console.log(hash.digest('hex'));    // a94a8fe5ccb19ba61c4c0873d391e987982fbbd3
 

3、SHA-2
SHA-224、SHA-256、SHA-384，和SHA-512并称为SHA-2。
新的哈希函数并没有接受像SHA-1一样的公众密码社区做详细的检验，所以它们的密码安全性还不被大家广泛的信任。
虽然至今尚未出现对SHA-2有效的攻击，它的算法跟SHA-1基本上仍然相似；因此有些人开始发展其他替代的哈希算法。

1
2
3
4
varhash=crypto.createHash('sha256');
hash.update('test');
console.log(hash.digest('hex'));    // 9f86d081884c7d659a2feaa0c55ad015a3bf4f1b2b0b822cd15d6c15b0f00a08
 

4、SHA-3
SHA-3，之前名为Keccak算法，是一个加密杂凑算法。
由于对MD5出现成功的破解，以及对SHA-0和SHA-1出现理论上破解的方法，NIST感觉需要一个与之前算法不同的，可替换的加密杂凑算法，也就是现在的SHA-3。

5、RIPEMD-160
RIPEMD-160 是一个 160 位加密哈希函数。
它旨在用于替代 128 位哈希函数 MD4、MD5 和 RIPEMD。
RIPEMD-160没有输入大小限制，在处理速度方面比SHA2慢。
安全性也没SHA-256和SHA-512好。

1
2
3
4
varhash=crypto.createHash('ripemd160');
hash.update('test');
console.log(hash.digest('hex'));    // 5e52fee47e6b070565f74372468cdc699de89107
 

其它加密算法相关

nodejs除了提供常用加密算法，还提供了HMAC（密钥相关的哈希运算消息认证，类似加盐处理），对称加密算法Cipher（加密）和Decipher（解密），非对称加密算法Signer（签名）和Verify（验证），这里篇幅太长，详细可以参考这几篇讲解得很详细的文章：
Node.js加密算法库Crypto
浅谈nodejs中的Crypto模块
 浅谈nodejs中的Crypto模块（补完）

查找哈希算法

下面列举几个目前在查找方面比较快的哈希算法（不区分先后），比较老的或者慢的就没举例了，毕竟篇幅有限。

1、lookup3
Bob Jenkins在1997年发表了一篇关于哈希函数的文章《A hash function for hash Table lookup》，这篇文章自从发表以后现在网上有更多的扩展内容。这篇文章中，Bob广泛收录了很多已有的哈希函数，这其中也包括了他自己所谓的“lookup2”。随后在2006年，Bob发布了lookup3。
Bob很好的实现了散列的均匀分布，但是相对来说比较耗时，它有两个特性，1是具有抗篡改性，既更改输入参数的任何一位都将带来一半以上的位发生变化，2是具有可逆性，但是在逆运算时，它非常耗时。

2、Murmur3
murmurhash是 Austin Appleby于2008年创立的一种非加密哈希算法，适用于基于哈希进行查找的场景。murmurhash最新版本是MurMurHash3，支持32位、64位及128位值的产生。
MurMur经常用在分布式环境中，比如Hadoop，其特点是高效快速，但是缺点是分布不是很均匀。

3、FNV-1a
FNV又称Fowler/Noll/Vo，来自3位算法设计者的名字（Glenn Fowler、Landon Curt Noll和Phong Vo）。FNV有3种：FNV-0（已过时）、FNV-1、FNV-1a，后两者的差别极小。FNV-1a生成的哈希值有几个特点：无符号整形；哈希值的bits数，是2的n次方（32, 64, 128, 256, 512, 1024），通常32 bits就能满足大多数应用。

4、CityHash
2011年，google发布CityHash（由Geoff Pike 和Jyrki Alakuijala编写）,其性能好于MurmurHash。
但后来CityHash的哈希算法被发现容易受到针对算法漏洞的攻击，该漏洞允许多个哈希冲突发生。

5、SpookyHash
又是Bob Jenkins哈希牛人的一巨作，于2011年发布的新哈希函数性能优于MurmurHash，但是只给出了128位的输出，后面发布了SpookyHash V2，提供了64位输出。

6、FarmHash
FarmHash也是google发布的，FarmHash从CityHash继承了许多技巧和技术，是它的后继。FarmHash声称从多个方面改进了CityHash。

7、xxhash
xxhash由Yann Collet发表，http://cyan4973.github.io/xxHash/ 这是它的官网，据说性能很好，似乎被很多开源项目使用，Bloom Filter的首选。

查找哈希函数的性能比较

一般性能好的哈希算法都会根据不同系统做优化。
这里有一篇文章详细介绍了各种非加密哈希的性能比较（http://aras-p.info/blog/2016/08/09/More-Hash-Function-Tests/ ）。

文章详细列出了各个平台（甚至包括手机和XBOXOne以及asm.js）之间的哈希算法性能比较，同时也对不同输入数据量做了对比。
似乎在跨平台使用方面CityHash64在64位系统性能最佳，而xxHash32在32位系统性能最好。
在数据量大方面，不同平台也有不同的选择
Intel CPU：总体来说xxhash64更好，随之FarmHash64（如果使用了SSE4.2），xxHash32更适合32位系统。
苹果手机CPU（A9）：CityHash64在64位系统性能最佳，而xxHash32在32位系统性能最好。
SpookyV2更适合在XBOXOne中使用。
而短字符串输入使用FNV-1a性能最优（在pc，手机和XBOX中少于8字节，在asm.js中少于20字节），而且它的实现很简单。

哈希函数的分类

介绍了那么多哈希函数，实际上哈希函数主要分为以下几类：

1、加法Hash；
所谓的加法Hash就是把输入元素一个一个的加起来构成最后的结果，prime是素数。

1
2
3
4
5
6
7
8
9
10
11
12
13
functionaddictiveHash(key='',prime){
    let hash=0;
    for(leti=0;i<key.length;++i){
        hash+=key.charCodeAt(i);
    }
 
    returnhash%prime;
}
 
console.log(addictiveHash('test',31));// 14
console.log(addictiveHash('abc',31));// 15
console.log(addictiveHash('abb',31));// 14
 

2、位运算Hash；
这类型Hash函数通过利用各种位运算（常见的是移位和异或）来充分的混合输入元素。

1
2
3
4
5
6
7
8
9
10
11
functionrotatingHash(key='',prime){
    let hash=0;
    for(leti=0;i<key.length;++i){
        hash=(hash<<4)^(hash>>28)^key.charCodeAt(i);
    }
    return(hash%prime);
}
console.log(rotatingHash('test',31));// 13
console.log(rotatingHash('abc',31));// 23
console.log(rotatingHash('abb',31));// 22
 

3、乘法Hash；
这样的类型的哈希函数利用了乘法的不相关性.乘法哈希里最有名的就是adler32，reactJS的checksum校验就是使用的adler32的改良版。
https://github.com/facebook/react/blob/b1b4a2fb252f26fe10d29ba60d85ff89a85ff3ec/src/renderers/dom/stack/server/ReactMarkupChecksum.js
https://github.com/facebook/react/blob/b1768b5a48d1f82e4ef4150e0036c5f846d3758a/src/renderers/shared/utils/adler32.js

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
34
functionadler32(str){
    vara=1,b=0,L=str.length,M=0,c=0,d=0;
 
    for(vari=0;i<L;){
        M=Math.min(L-i,3850);
        while(M>0){
            c=str.charCodeAt(i++);
            if(c<0x80){a+=c;}
            elseif(c<0x800){
                a+=192|((c>>6)&31);b+=a;--M;
                a+=128|(c&63);
            }elseif(c>=0xD800&&c<0xE000){
                c=(c&1023)+64;d=str.charCodeAt(i++)&1023;
                a+=240|((c>>8)&7);b+=a;--M;
                a+=128|((c>>2)&63);b+=a;--M;
                a+=128|((d>>6)&15)|((c&3)<<4);b+=a;--M;
                a+=128|(d&63);
            }else{
                a+=224|((c>>12)&15);b+=a;--M;
                a+=128|((c>>6)&63);b+=a;--M;
                a+=128|(c&63);
            }
            b+=a;--M;
        }
        a=(15*(a>>>16)+(a&65535));
        b=(15*(b>>>16)+(b&65535));
    }
    return((b%65521)<<16)|(a%65521);
}
console.log(adler32('test',31));// 73204161
console.log(adler32('abc',31));// 38600999
console.log(adler32('abb',31));// 38535462
 
 

4、除法Hash；
和乘法一样用了不相关性，但性能不好。

5、查表Hash；
查表Hash最有名的样例莫过于CRC系列算法。尽管CRC系列算法本身并非查表，可是，查表是它的一种最快的实现方式。以下是CRC32的实现：

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
functionsigned_crc_table(){
    varc=0,table=newArray(256);
 
    for(varn=0;n!=256;++n){
        c=n;
        c=((c&1)?(-306674912^(c>>>1)):(c>>>1));
        c=((c&1)?(-306674912^(c>>>1)):(c>>>1));
        c=((c&1)?(-306674912^(c>>>1)):(c>>>1));
        c=((c&1)?(-306674912^(c>>>1)):(c>>>1));
        c=((c&1)?(-306674912^(c>>>1)):(c>>>1));
        c=((c&1)?(-306674912^(c>>>1)):(c>>>1));
        c=((c&1)?(-306674912^(c>>>1)):(c>>>1));
        c=((c&1)?(-306674912^(c>>>1)):(c>>>1));
        table[n]=c;
    }
 
    returntypeofInt32Array!=='undefined'?newInt32Array(table):table;
}
 
varT=signed_crc_table();
functioncrc32(str,seed){
    varC=seed^-1;
    for(vari=0,L=str.length,c,d;i<L;){
        c=str.charCodeAt(i++);
        if(c<0x80){
            C=(C>>>8)^T[(C^c)&0xFF];
        }elseif(c<0x800){
            C=(C>>>8)^T[(C^(192|((c>>6)&31)))&0xFF];
            C=(C>>>8)^T[(C^(128|(c&63)))&0xFF];
        }elseif(c>=0xD800&&c<0xE000){
            c=(c&1023)+64;d=str.charCodeAt(i++)&1023;
            C=(C>>>8)^T[(C^(240|((c>>8)&7)))&0xFF];
            C=(C>>>8)^T[(C^(128|((c>>2)&63)))&0xFF];
            C=(C>>>8)^T[(C^(128|((d>>6)&15)|((c&3)<<4)))&0xFF];
            C=(C>>>8)^T[(C^(128|(d&63)))&0xFF];
        }else{
            C=(C>>>8)^T[(C^(224|((c>>12)&15)))&0xFF];
            C=(C>>>8)^T[(C^(128|((c>>6)&63)))&0xFF];
            C=(C>>>8)^T[(C^(128|(c&63)))&0xFF];
        }
    }
    returnC^-1;
}
console.log(crc32('test',31));// -804963899
console.log(crc32('abc',31));// 576628111
console.log(crc32('abb',31));// 1431934233
 
 

查表Hash中有名的样例有：Universal Hashing和Zobrist Hashing。他们的表格都是随机生成的。

6、混合Hash；
混合Hash算法利用了以上各种方式。各种常见的Hash算法，比方MD5、Tiger都属于这个范围。它们一般非常少在面向查找的Hash函数里面使用。

哈希函数的选择

那么多种哈希函数，我们究竟该选择哪种呢？
不同的应用场景对哈希的算法设计要求也不一样，但一个好的哈希函数应该具备以下三点：
1. 抗碰撞性，尽量避免冲突。
2. 抗篡改性，只要改动一个字节，其哈希值也会很大不同。
3. 查找效率。

在加密方面，哈希函数应该对抗碰撞性和抗篡改性要求很高，而会牺牲查找效率。
而且随着时代的变化我们最好还是选择更现代化的哈希函数。
目前来说我们可以选择SHA-2族用于安全加密中，SHA-3更安全但对性能损耗更大。更保险的做法是加盐后混合加密。
在nodejs中我们可以很方便地用crypto.pbkdf2()函数加盐加密，默认会调用hmac算法，用sha-1进行加密，并且可以设置迭代次数和密文长度。常用于用户注册和登录校验流程中。下面的例子我们用伪随机函数randomBytes()生成16字节的盐（更安全的做法是多于16字节）

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
constcrypto=require('crypto');
 
let txt='test';
 
//通过伪随机码生成salt，进行加密
crypto.randomBytes(128,function(err,salt){
    if(err)throwerr;
    salt=salt.toString('hex');
    console.log(salt);//生成salt
 
    crypto.pbkdf2(txt,salt,4096,256,function(err,hash){
        if(err)throwerr;
        hash=hash.toString('hex');
        console.log(hash);//生成密文
    })
})
 
/*
6e5e20869916c5aea5f6188807abb0dcd83ca0d3c21ec880bab71c483e7cca624af8c5b6fe2ec820e296452e6e43476
98411aa545d4c3a21056e02659446b694383b3eedd3a7cbcb9592ede2d5875206f6b764fee69e65271c99d73b818837
9d0c92e345b046d760b84954babd6740b6928e76ef86e9bfd07c2867837678b575
(node:1264) DeprecationWarning: crypto.pbkdf2 without specifying a digest is deprecated. Please
 specify a digest
4572e319f6f5e05ee2507dacc43cd9c6f970e1ed37e76c2a86c99afde11c75f35f04322ee3fec4775a21f1181c0e357
d00bdf1f1aef4cffe9f11f7859fea658df76553ae37deacc5e085d5e7e38a13ec0f7b0d8f29d738f0cd00cddbd74493
53547eb651244a6c3e599d86878f80e1be2d269afd3d9ea678982150163fa9e61385f40fabedae2403085e8432a723e
da8693466068523c9e26afdd0764a21d2372bde7f607af6bcbc8fd4a325ad942688ee770efdf038332a470b7ed7c49e
7c9b0f8d6a1f9557dd51c3747ac4a7ecabda7089d5685403e6af525de5f84d0b4d7a53ea1fb879afa2cfee4a60775b5
39614ef451de2dd1ca995a14a79c4236d6089
*/
 
 

而在查找方面，哈希函数更追求查找的效率和良好的抗碰撞性。
短字符串输入使用FNV-1a，数量大的在32位系统使用xxhash，64位系统使用FarmHash。

参考文献

建议继续学习：

QQ技术交流群：445447336，欢迎加入！
扫一扫订阅我的微信号：IT技术博客大学习

<< 前一篇：一维数组的聚类

后一篇：图数据库简介 >>

文章信息

作者：lin, dongpeng 来源： AlloyTeam
标签：哈希
发布时间：2019-01-01 20:23:19

建议继续学习

近3天十大热文