HASH算法介绍

• Hash，一般翻译做“散列”，也有直接音译为“哈希”的，就是把任意长度的输入（又叫做预映射， pre-image），通过散列算法，变换成固定长度的输出，该输出就是散列值。这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，而不可能从散列值来唯一地确定输入值。
• 数学表述为：h = H(M) ，其中H( )--单向散列函数，M--任意长度明文，h--固定长度散列值。

各个HASH算法比较

哈希算法是一个大杂烩，除了 MD5、SHA1 这一类加密哈希算法（cryptographic hash），还有很多或家喻户晓或寂寂无闻的算法。
哈希算法只需满足把一个元素映射到另一个区间的要求。鉴于该要求是如此之低，像 Java 的 hashCode 其实也算一种哈希算法。
不过今天当然不会讲 Java 的 hashCode，我们来聊聊一些更具实用性的算法，某些场景下它们不仅可以替代加密哈希算法，甚至还有额外的优势。
评价一个哈希算法的好坏，人们通常会引用 SMHasher 测试集的运行结果。从这里可以看到关于它的介绍：SMHasher wiki。此外还有人在 SMHasher 的基础上，添加更多的测试和哈希算法：demerphq/smhasher。demerphq/smhasher 这个项目有个好处，作者把 SMhasher 运行结果放到 doc 目录下，为本文的分析提供了丰富的数据。
在需要进行比较的时候，我会选择 MD5 作为加密哈希算法阵营的代表。原因有三：

1. MD5 通常用在不需要加密的哈希计算中，以致于有些场合下“哈希”就意味着计算 MD5。
2. MD5 计算速度跟其他加密哈希算法差不多。
3. MD5 生成的哈希值是 128 比特的。这里的哈希值指的是二进制的值，而不是 HEX 或 base64 格式化后的人类可读的值。通常我们提到的 32 位 MD5 是指由 32 个字符组成的，HEX 格式的 MD5。下面提到的 32 位、128 位，如果没有特殊说明，都是指比特数。

MurMurHash

设想这样的场景：当数据中有几个字段相同，就可以把它当作同类型数据。对于同类型的数据，我们需要做去重。
一个通常的解决办法是，使用 MD5 计算这几个字段的指纹，然后把指纹存起来。如果当前指纹存在，则表示有同类型的数据。
这种情况下，由于不涉及故意的哈希碰撞，并不一定要采用加密哈希算法。（加密哈希算法的一个特点是，即使你知道哈希值，也很难伪造有同样哈希值的文本）
而非加密哈希算法通常要比加密哈希算法快得多。如果数据量小，或者不太在意哈希碰撞的频率，甚至可以选择生成哈希值小的哈希算法，占用更小的空间。
就个人而言，我偏好在这种场景里采用 MurMurHash3，128 位的版本。理由有三：

1. MurMurHash3 久经沙场，主流语言里面都能找到关于它的库。
2. MurMurHash3，128 位版本的哈希值是 128 位的，跟 MD5 一样。128 位的哈希值，在数据量只有千万级别的情况下，基本不用担心碰撞。
3. MurMurHash3 的计算速度非常快。

MurMurHash3 哈希算法是 MurMurHash 算法家族的最新一员。虽说是“最新一员”，但距今也有五年的历史了。无论从运算速度、结果碰撞率，还是结果的分布均衡程度进行评估，MurMurHash3 都算得上一个优秀的哈希算法。
除了 128 位版本以外，它还有生成 32 位哈希值的版本。在某些场景下，比如哈希的对象长度小于 128 位，或者存储空间要求占用小，或者需要把字符串转换成一个整数，这一特性就能帮上忙。当然，32 位哈希值发生碰撞的可能性就比 128 位的要高得多。当数据量达到十万时，就很有可能发生碰撞。
贴一个简略的 MurMurHash3 和 MD5、MurMurHash2 的 benchmark：
lua-resty-murmurhash3#benchmark
可以看到，MurMurHash3 128 位版本的速度是 MD5 的十倍。有趣的是，MurMurHash3 生成 32 位哈希的用时比生成 128 位哈希的用时要长。原因在于生成 128 位哈希的实现受益于现代处理器的特性。

CRC32

MurMurHash3 是我的心头好，另一个值得关注的是 CRC 系列哈希算法。诸位都知道，CRC 可以用来算校验和。除此以外，CRC 还可以当作一个哈希函数使用。
目前常用的 CRC 算法是 CRC32，它可以把一个字符串哈希成 32 位的值。CRC32 的碰撞率要比 MurMurHash3（32位）低，可惜它的运算速度跟 MD5 差不多。一个 32 位的哈希值，再怎么样，碰撞的概率还是比 128 位的多得多。更何况选用非加密哈希算法，运算速度往往是首先考虑的。看样子 CRC32 要出局了。
好在 CRC 系列一向有硬件加持。只要 CPU 支持 sse4.2 特性，就能使用 _mm_crc32_* 这一类硬件原语。（参见 Intel 的 文档，更详细的用法可以在网上搜到）硬件加持之后，CRC32 的计算速度可以达到十数倍以上的提升。换个说法，就是有硬件加持的 CRC32，比 MurMurHash3 要快。
不过要注意的是，有 sse4.2 加持的是 CRC32c，它是 CRC32 的一个变种。CRC32c 跟我们通常用的 CRC32 并不兼容。所以如果你要编写的程序会持久化 CRC32 哈希值，在使用硬件加速之前先关注这一点。

FNV

跟 FNV 的初次邂逅，是在 Go 的标准库文档里。我很惊讶，一门主流语言的标准库里，居然会有不太知名的哈希算法。从另一个角度看，非加密哈希算法还是有其必要性的，不然 Go 这门以实用著称的语言也不会内置 FNV 算法了。
可惜跟其他哈希算法相比，FNV 并无出彩之处（参考 SMHasher 测试结果）。FNV 家族较新的 FNV-1a 版本，对比于 FNV-1 做了一些改善。尽管如此，除非写的是 Go 程序，我通常都不会考虑使用它。

SipHash

大部分非加密哈希算法的改良，都集中在让哈希速度更快更好上。SipHash 则是个异类，它的提出是为了解决一类安全问题：hash flooding。通过让输出随机化，SipHash 能够有效减缓 hash flooding 攻击。凭借这一点，它逐渐成为 Ruby、Python、Rust 等语言默认的 hash 表实现的一部分。
如果你愿意尝试下新技术，可以看看 2016 新出的 HighwayHash。它宣称可以达到 SipHash 一样的效果，并且凭借 SIMD 的加持，在运算速度上它是 SipHash 的 5.2 倍（参考来源：https://arxiv.org/abs/1612.06257 ）。

xxHash

为什么要用一个不知名的哈希函数？最首要的理由就是性能。对性能的追求是无止境的。如果不考虑硬件加持的 CRC32，xxHash可以说是哈希函数性能竞赛的最新一轮优胜者。
xxHash 支持生成 32 位和 64 位哈希值，多个 benchmark 显示，其性能比 MurMurHash 的 32 位版本快接近一倍。如果程序的热点在于哈希操作，作为一种优化手段，xxHash 值得一试。
顺便一提，MetroHash 声称其速度在 xxHash 之上。不过前者用的人不多，如果想尝鲜，可以关注下。

HASH**算法的实际应用-**加密

• 常见的哈希加密算法：MD5，SHA-1，SHA-2，SHA-256，SHA-X（系列）
• 1) 文件校验:MD5 Hash算法的“数字指纹”特性，使它成为目前应用最广泛的一种文件完整性校验和(Checksum)算法，不少Unix系统有提供计算md5 checksum的命令；
• 2) 数字签名：在这种签名协议中，双方必须事先协商好双方都支持的Hash函数和签名算法。签名方先对该数据文件进行计算其散列值，然后再对很短的散列值结果--如Md5是16个字节，SHA1是20字节，用非对称算法进行数字签名操作。对方在验证签名时，也是先对该数据文件进行计算其散列值，然后再用非对称算法验证数字签名； （实际是HASH+非对称加密）
• 3) 鉴权协议:需要鉴权的一方，向将被鉴权的一方发送随机串（“挑战”），被鉴权方将该随机串和自己的鉴权口令字一起进行 Hash 运算后，返还鉴权方，鉴权方将收到的Hash值与在己端用该随机串和对方的鉴权口令字进行 Hash 运算的结果相比较（“认证”），如相同，则可在统计上认为对方拥有该口令字，即通过鉴权。（摘要）
• HASH加密算法与其他加密算法的主要不同点是：哈希(Hash)算法是一种单向密码体制,即只有 加密过程,没有解密过程

HASH**算法的实际应用-**查找

• 常见的哈希查找算法：BKDRHash，APHash，DJBHash，JSHash，RSHash，SDBMHash等
• 1) 基本思想是：以数据对象的关键词 key 为自变量，通过一个确定的函数关系 h ,计算出对应的函数值 h(key) ，把这个值解释为数据对象的存储地址，并按此存放，即“存储位置=h(key)存储位置=h(key)”。
• Gdb下函数符号实际对应的是一个内存地址，映射大小为32bit或64bit（即32位系统或64位系统）

FNV算法介绍

• FNV哈希算法全名为Fowler-Noll-Vo算法，是以三位发明人Glenn Fowler，Landon Curt Noll，Phong Vo的名字来命名的，最早在1991年提出

• 特点和用途：FNV能快速hash大量数据并保持较小的冲突率，它的高度分散使它适用于hash一些非常相近的字符串，比如URL，hostname，文件名，text，IP地址等。

• 适用范围：比较适用于字符串比较短的哈希场景

  　　FNV哈希算法有如下两种，FNV-1a相比FNV-1，散列分布更好。二者不同点为：for循环两行代码的顺序相反
  　　哈希函数一般适用移位和乘除法来实现。哈希函数一般都比较精简，算法复杂度比较低。哈希函数的移位和乘除法可能会导致数据丢失，这也是哈希不可逆的原因

  FNV**算法说明-1**

• hash值：一个n位的unsigned int型hash值，初始值为offset_basis.

• offset_basis：初始的哈希值，该值在最早的版本中是0，为了增强哈希的可靠性，后续修改为非0的值，通过如下算法获取

参见《生成offset_basis.py》

FNV**算法说明-2**

　　octet_of_data：8位数据（即一个字节）：即需要被哈希的字符串
　　FNV_prime：FNV用于散列的质数（质数在哈希算法中发挥着重要作用，在一般使用的哈希除留余数法中： H(key) = key MOD p，p也要求是一个质数（质数也称为素数））

• 32 bit FNV_prime = 224 + 28 + 0x93 = 16777619
• 64 bit FNV_prime = 240 + 28 + 0xb3 = 1099511628211
• 128 bit FNV_prime = 288 + 28 + 0x3b = 309485009821345068724781371
• 256 bit FNV_prime = 2168 + 28 + 0x63 = 374144419156711147060143317175368453031918731002211
• 512 bit FNV_prime = 2344 + 28 + 0x57 = 35835915874844867368919076489095108449946327955754392558399825615420669938882575126094039892345713852759

FNV**算法使用**

• 支持将字符串哈希为32/64/128/256/512/1024bit的数字
• 支持将字符串哈希为任意bit的数字，比如11/33bit
• 支持将字符串哈希为特定范围的数字，比如[0,99999]

将字符串哈希为32bit**的数字**

hash = offset_basis 

for each octet_of_data to be hashed

    hash = hash xor octet_of_data

    hash = hash * FNV_prime

return hash

将字符串哈希为特定范围的数字

将字符串哈希为[0,999]的数字
#define TRUE_HASH_SIZE ((u_int32_t)50000) /* range top plus 1 */
#define FNV_32_PRIME ((u_int32_t)16777619)
#define FNV1_32_INIT ((u_int32_t)2166136261)
#define MAX_32BIT ((u_int32_t)0xffffffff) /* largest 32 bit unsigned value */
#define RETRY_LEVEL ((MAX_32BIT / TRUE_HASH_SIZE) * TRUE_HASH_SIZE)
u_int32_t hash;
void *data;
size_t data_len;

hash = fnv_32_buf(data, data_len, FNV1_32_INIT);
while (hash >= RETRY_LEVEL) {
    hash = (hash * FNV_32_PRIME) + FNV1_32_INIT;
}
hash %= TRUE_HASH_SIZE;

参见《生成任意范围哈希.py》，代码附件链接