哈希函数介绍
什么是哈希
在记录的关键字与记录的存储地址之间建立的一种对应关系叫哈希函数。
哈希函数就是一种映射，是从关键字到存储地址的映射。
通常，包含哈希函数的算法的算法复杂度都假设为 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 |
const crypto = 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 |
var hash = crypto.createHash('md5'); hash.update('test'); console.log(hash.digest('hex')); // 098f6bcd4621d373cade4e832627b4f6 var hash = 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 |
var hash = 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 |
var hash = 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 |
var hash = 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 经常用在分布式环境中，比如 Hadoo