Hash算法

什么是Hash

Hash 也称散列、哈希，对应的英文都是 Hash。基本原理就是把任意长度的输入，通过 Hash 算法变成固定长度的输出。这个映射的规则就是对应的 Hash 算法，而原始数据映射后的二进制串就是哈希值。活动开发中经常使用的 MD5 和 SHA 都是历史悠久的 Hash 算法。

echo md5("嗨客网（www.haicoder.net）");
// 输出结果：c039822701479838d74267c87495db39

在这个例子里，这是一个测试文案是原始值，c039822701479838d74267c87495db39 就是经过 hash 算法得到的 Hash 值。整个 Hash 算法的过程就是把原始任意长度的值空间，映射成固定长度的值空间的过程。

Hash的特点

一个优秀的 hash 算法，需要什么样的要求呢？

从 hash 值不可以反向推导出原始的数据，这个从上面 MD5 的例子里可以明确看到，经过映射后的数据和原始数据没有对应关系。
输入数据的微小变化会得到完全不同的 hash 值，相同的数据会得到相同的值 echo md5("嗨客网（www.haicoder.net）"); 的输出结果：c039822701479838d74267c87495db39。echo md5("嗨客网（haicoder.net）"); 的输出结果：45d3a6204814003ddd13d395ccd00d7d。可以看到我们只改了三个字母，但是整个得到的 hash 值产生了非常大的变化。
哈希算法的执行效率要高效，长的文本也能快速地计算出哈希值。
hash 算法的冲突概率要小由于 hash 的原理是将输入空间的值映射成 hash 空间内，而 hash 值的空间远小于输入的空间。根据抽屉原理，一定会存在不同的输入被映射成相同输出的情况。那么作为一个好的 hash 算法，就需要这种冲突的概率尽可能小。

Hash碰撞的解决方案

前面提到了 hash 算法是一定会有冲突的，那么如果我们如果遇到了 hash 冲突需要解决的时候应该怎么处理呢？比较常用的算法是链地址法和开放地址法。

链地址法

链表地址法是使用一个链表数组，来存储相应数据，当 hash 遇到冲突的时候依次添加到链表的后面进行处理，如下图：

链地址在处理的流程为：添加一个元素的时候，首先计算元素 key 的 hash 值，确定插入数组中的位置。如果当前位置下没有重复数据，则直接添加到当前位置。当遇到冲突的时候，添加到同一个 hash 值的元素后面，行成一个链表。

这个链表的特点是同一个链表上的 Hash 值相同。Java 的数据结构 HashMap 使用的就是这种方法来处理冲突，JDK1.8 中，针对链表上的数据超过 8 条的时候，使用了红黑树进行优化。

开放地址法

开放地址法是指大小为 M 的数组保存 N 个键值对，其中 M > N。我们需要依靠数组中的空位解决碰撞冲突。基于这种策略的所有方法被统称为 “开放地址” 哈希表。线性探测法，就是比较常用的一种 “开放地址” 哈希表的一种实现方式。线性探测法的核心思想是当冲突发生时，顺序查看表中下一单元，直到找出一个空单元或查遍全表。简单来说就是：一旦发生冲突，就去寻找下一个空的散列表地址，只要散列表足够大，空的散列地址总能找到。

线性探测法的数学描述是：h(k, i) = (h(k, 0) + i) mod m，i 表示当前进行的是第几轮探查。i=1 时，即是探查 h(k, 0) 的下一个；i=2，即是再下一个。这个方法是简单地向下探查。mod m 表示：到达了表的底下之后，回到顶端从头开始。

对于开放寻址冲突解决方法，除了线性探测方法之外，还有另外两种比较经典的探测方法，二次探测（Quadratic probing）和双重散列（Double hashing）。但是不管采用哪种探测方法，当散列表中空闲位置不多的时候，散列冲突的概率就会大大提高。为了尽可能保证散列表的操作效率，一般情况下，我们会尽可能保证散列表中有一定比例的空闲槽位。我们用装载因子（load factor）来表示空位的多少。

散列表的装载因子=填入表中的元素个数/散列表的长度。装载因子越大，说明冲突越多，性能越差。

案例

链表法：假设散列长为 7，散列函数 H(K)=K mod 6，给定的关键字序列为 {20, 12, 23, 1, 19, 28, 7}，当使用链表法时，相应的数据结构如下图所示：

线性探测法：当使用线性探测法时，相应的数据结果如下图所示：

这里的两种算法的区别是在线性探测法遇到冲突时会将冲突数据放到下一个空的位置下面。

Hash应用

在日常运营活动中，我们活动开发经常遇到的应用场景是信息加密、数据校验、负载均衡。下面分别对这三种应用场景进行讲解。

信息加密

2011 年 CSDN 脱库事件，导致超过 600W 的用户的密码泄露，让人失望的是，CSDN 是明文存储用户的注册邮箱和密码的。作为用户的非常隐私的信息，最简单的保护措施就是对密码进行 hash 加密。在客户端对用户输入的密码进行 hash 运算，然后在服务端的数据库中保存用户密码的 hash 值。由于服务器端也没有存储密码的明文，所以目前很多网站也就不再有找回密码的功能了。

看到这里有些同学会觉得那么我们是不是对用户输入的密码进行一次 MD5 加密就可以了呢，这样就算恶意用户知道了 hash 值，也没有办法拿到用户的真实密码。假设用户的密码是 123456，经过一次 md5 以后得到的值是：

e10adc3949ba59abbe56e057f20f883e

那么是不是使用了这个加密后的字符串来存密码就万无一失了呢，理想总是很丰满，而现实总是很骨感的。我们可以使用这个网站：

https://www.cmd5.com/

进行 MD5 破解，运行结果如下：

我们看到，我们通过加密后的字符串反解出了原始字符串，那么一般针对这种问题，我们的解决之道就是引入salt(加盐)，即利用特殊字符（盐）和用户的输入合在一起组成新的字符串进行加密。通过这样的方式，增加了反向查询的复杂度。但是这样的方式也不是万无一失，如果发生了盐被泄露的问题，就需要所有用到的地方来重置密码。

针对 salt 泄露的问题，其实还有一种解决办法，即使用 HMAC 进行加密（Hash-based Message Authentication Code）。这种算法的核心思路是加密使用的 key 是从服务器端获取的，每一个用户的是不一样的。如果发生了泄露，那么也就是这一个用户的会被泄露，不会影响到全局。

数据校验

使用过 git 的同学都应该清楚，每次 git 提交后都有一个 commit id，比如:

5075586d67ca32a50fd46984fa30fdfe94d0e61f

就是一次 git commit 的结果，那么这个 id 是如何生成出来的呢？查阅了相关资料，使用如下代码可以进行查看：

printf “commit %s0” $(git cat-file commit HEAD | wc -c); git cat-file commit HEAD

执行结果如下图所示：

git 的 commit id 主要包括了以下几部分内容：Tree 哈希，parent 哈希、作者信息和本次提交的备注。针对这些信息进行 SHA-1 算法后得到值就是本次提交的 commit id。简单来讲，就是对于单次提交的头信息的一个校验和。

Linux kernel 开创者和 Git 的开发者——Linus 说，Git 使用了 sha1 并非是为了安全性，而是为了数据的完整性；它可以保证，在很多年后，你重新 checkout 某个 commit 时，一定是它多年前的当时的状态，完全一摸一样，完全值得信任。

但最新研究表明，理论上对其进行哈希碰撞（hash collision，不同的两块数据有相同的 hash 值）的攻击可以在2^51（2的51次方）左右的次数内实现。不过由于 commit id 是针对单个仓库里的，所以实际应用中我们可以认为如果两个文件的 SHA-1 值是相同的，那么它们确是完全相同的内容。

在数据校验方面的另一个应用场景就是版权的保护或者违禁信息的打击，比如某个小视频，第一个用户上传的时候，我们认为是版权所有者，计算一个 hash 值存下来。当第二个用户上传的时候，同样计算 hash 值，如果 hash 值一样的话，就算同一个文件。这种方案其实也给用户传播违禁文件提高了一些门槛，不是简单的换一个名字或者改一下后缀名就可以躲避掉打击了。（当然这种方式也是可以绕过的，图片的你随便改一下颜色，视频去掉一帧就又是完全不同的 hash 值了。）

负载均衡

对于同一个客户端上的请求，尤其是已登录用户的请求，需要将其会话请求都路由到同一台机器，以保证数据的一致性，这可以借助哈希算法来实现，通过用户 ID 尾号对总机器数取模（取多少位可以根据机器数定），将结果值作为机器编号。

分布式缓存

分布式缓存和其他机器或数据库的分布式不一样，因为每台机器存放的缓存数据不一致，每当缓存机器扩容时，需要对缓存存放机器进行重新索引（或者部分重新索引），这里应用到的也是哈希算法的思想。

唯一标识

比如 URL 字段或者图片字段要求不能重复，这个时候就可以通过对相应字段值做 md5 处理，将数据统一为 32 位长度从数据库索引构建和查询角度效果更好，此外，还可以对文件之类的二进制数据做 md5 处理，作为唯一标识，这样判定重复文件的时候更快捷。