哈希函数介绍
什么是哈希
在记录的关键字与记录的存储地址之间建立的一种对应关系叫哈希函数。
哈希函数就是一种映射，是从关键字到存储地址的映射。
通常，包含哈希函数的算法的算法复杂度都假设为 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 经常用在分布式环境中，比如 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 |
function addictiveHash(key = '', prime){ let hash = 0; for(let i = 0; i < key.length; ++i){ hash += key.charCodeAt(i); } return hash % 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 |
function rotatingHash(key = '', prime) { let hash = 0; for (let i = 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 |
function adler32(str) { var a = 1, b = 0, L = str.length, M = 0, c = 0, d = 0; for (var i = 0; i < L;) { M = Math.min(L - i, 3850); while (M > 0) { c = str.charCodeAt(i++); if (c < 0x80) { a += c; } else if (c < 0x800) { a += 192 | ((c >> 6) & 31); b += a; --M; a += 128 | (c & 63); } else if (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 |
function signed_crc_table() { var c = 0, table = new Array(256); for(var n =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; } return typeof Int32Array !== 'undefined' ? new Int32Array(table) : table; } var T = signed_crc_table(); function crc32(str, seed) { var C = seed ^ -1; for(var i = 0, L=str.length, c, d; i < L;) { c = str.charCodeAt(i++); if(c < 0x80) { C = (C>>>8) ^ T[(C ^ c)&0xFF]; } else if(c < 0x800) { C = (C>>>8) ^ T[(C ^ (192|((c>>6)&31)))&0xFF]; C = (C>>>8) ^ T[(C ^ (128|(c&63)))&0xFF]; } else if(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]; } } return C ^ -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 |
const crypto = require('crypto'); let txt = 'test'; //通过伪随机码生成salt，进行加密 crypto.randomBytes(128, function (err, salt) { if (err) throw err; salt = salt.toString('hex'); console.log(salt); //生成salt crypto.pbkdf2(txt, salt, 4096, 256, function (err,hash) { if (err) throw err; 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。
nbnblv 2017 年 6 月 6 日
不错，学习了