哈希函数概述
1684 words - 9 mins哈希函数（Hash Function），又称散列算法、散列函数，能够将任意长度的输入值，转换成固定长度的无规律的输出值，该值称为哈希值，通常为数字，但多用十六进制（即字母与数字组合）来表示。
哈希函数特征
对哈希函数有了一个定义层面的理解后，我们再来看看哈希函数的特征。
1、输出的哈希值数据长度固定不变。即使输入了相当大的数据，其输出的哈希值的长度也保持不变。同样地，不管输入的数据多小，哈希值长度仍然相同。例如：Hash("abcedfeghiexyzopn") => 4af08e9e15、Hash("a") => 2ed06a6d23。
2、如果输入的数据相同，那么输出的哈希值也必定相同，例如：Hash("xyz") == Hash("xyz")。但必须在使用同一哈希算法的前提下，若使用的算法不同，那么就算输入的数据相同，输出的哈希值仍然不同。
3、即使输入的数据相似，哪怕它们只有一比特的差别，那么输出的哈希值会存在巨大的差异。也就是说，输入相似的数据并不会导致输出的哈希值也相似。例如：Hash("xyz") => 5d134a8c23、Hash("xya") => 4e258b9d15。
4、即使输入的两个数据完全不同，输出的哈希值也有可能相同，这种情况叫“哈希冲突”，但出现概率比较低。例如：存在某个数据x，使得Hash("xyz") == Hash(x)，但我们无法反向推算出该x值。
5、不可能从哈希值反向推算出原本的数据，即输入到输出不可逆，这一点与加解密存在很大不同。
6、哈希值计算相对容易，计算时间不宜过长，这就要求哈希算法过程是高效的。
常见哈希算法
哈希函数的算法中，具有代表性的是 MD5、SHA-1 和 SHA-2 等，SHA 的全称是 Secure Hash Algorithm，即安全哈希算法。除了这些耳熟能详的哈希算法，还存在很多其他实现，可以将它们分成三代：
- 第一代：CRC（1975）、FNVHash（1991）、MD5（1992）、SHA-1（1993）、SHA-2（2002）、Lookup3（2006）；
- 第二代：MurmurHash（2008）；
- 第三代：SpookyHash（2011）、CityHash（2013）；
现挑选其中几个哈希算法进行介绍。
MurmurHash
MurmurHash 是一种非加密型哈希函数，适用于一般的哈希检索操作。由 Austin Appleby 于 2008 年发明，该名称来自两个基本操作，乘法（MU）和旋转（R），在其内部循环中使用。与其它流行的哈希函数相比，对于规律性较强的 key，MurmurHash 的随机分布特征表现更良好。
MurmurHash 与加密散列函数不同，它不是专门设计为难以被逆转，因此不适用于安全加密目的。它常被应用于分布式系统，很多开源项目如 Kafka、Redis、Memcached、Cassandra、HBase、Lucene 及 Guava 等等都使用到了该算法。具有高运算性能（比安全哈希算法快几十倍）和变化足够激烈（随机分布均匀）的优点。
MurmurHash 的当前（2018）版本是 MurmurHash3，能够产生出 32-bit 或 128-bit 哈希值。使用 128-bit 时，x86 和x64 版本不会生成相同的值，因为算法针对各平台进行了优化。
CityHash
2011 年 Appleby 被 Google 雇佣，Google 于 2013 年推出基于 MurmurHash 变种的 CityHash 算法。CityHash 的主要优点是大部分步骤使用了至少两步独立的数学运算，能使现代 CPU 从该算法获得最佳性能。但因 Google 追求 CityHash 运算速度而不是为了简化算法，其算法实现代码较同类流行算法复杂。
CityHash 有 CityHash64 和 CityHash128 两种算法，它们用于计算字符串的 64-bit 或 128-bit 哈希值，是解决经典问题的全新算法，有完备的统计特性。实际应用中，CityHash64 在速度方面至少提高 30%，并有望提高多达两倍。同样地，该算法不适用于加密。
MurmurHash3 与 CityHash 使用都比较简单，主流语言基本有算法实现。速度方面，CityHash 略快于 MurmurHash3。
应用场景
以下为哈希算法的两个典型应用场景。
1、数据保护
将用户密码使用哈希函数后再保存到服务器。如果把密码直接保存到服务器，可能会被第三方窃听或拖库，因此需要计算密码的哈希值，并且只存储哈希值。就算保存的哈希值暴露了，鉴于上述哈希函数特征，第三方也无法反推出原本密码。当用户输入密码登录时，先计算该输入密码的哈希值，再把它和服务器中的哈希值进行比对。这样，哈希函数可以更安全地实现基于密码的用户认证。
2、数字签名
在网络请求中，请求数据存在被监听和篡改可能。比如，在一次客户端与服务端的请求过程中，从请求方到接收方中间要经过很多路由器和交换机，攻击者可以在中途截获请求的数据，篡改请求内容后再发往服务端，比如中间人攻击。假设在一个网上存款系统中，一条消息表示用户的一笔转账，攻击者完全可以多次将收款账号改为自己的账号后再将请求发到服务端。
对请求内容进行数字签名可以有效的防篡改，具体过程如下：
- 客户端与服务端约定好相同的用于生成数字签名的哈希算法以及秘钥；
- 客户端使用约定好的哈希算法及秘钥，计算请求参数的哈希值，即数字签名 signature1；
- 客户端将数字签名 signature1 也放入请求的参数中，发送给服务端；
- 服务端接收到客户端的请求，然后使用约定好的哈希算法及秘钥，计算请求参数的哈希值，即数字签名 signature2；
- 服务端比对 signature1 和 signature2，如果对比一致，认定为合法请求，否则为非法请求。
由于攻击者不知道签名的哈希算法和密钥，即使截取到请求参数，对请求参数进行篡改，仍然无法得到修改后参数的数字签名 signature。
参考资料：