hash 算法

提到hash，相信大多数同学都不会陌生，之前很火现在也依旧很火的技术区块链背后的底层原理之一就是hash，下面就从hash算法的原理和实际应用等几个角度，对hash算法进行一个讲解。

 

1、什么是Hash

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

echo md5("这是一个测试文案");
// 输出结果：2124968af757ed51e71e6abeac04f98d

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

 

 2、Hash的特点

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

  • a)、从hash值不可以反向推导出原始的数据
    这个从上面MD5的例子里可以明确看到，经过映射后的数据和原始数据没有对应关系

  • b)、输入数据的微小变化会得到完全不同的hash值，相同的数据会得到相同的值

    echo md5("这是一个测试文案");
// 输出结果：2124968af757ed51e71e6abeac04f98d
echo md5("这是二个测试文案");
// 输出结果：bcc2a4bb4373076d494b2223aef9f702

    可以看到我们只改了一个文字，但是整个得到的hash值产生了非常大的变化。

  • c)、哈希算法的执行效率要高效，长的文本也能快速地计算出哈希值

  • d)、hash算法的冲突概率要小

    由于hash的原理是将输入空间的值映射成hash空间内，而hash值的空间远小于输入的空间。根据抽屉原理，一定会存在不同的输入被映射成相同输出的情况。那么作为一个好的hash算法，就需要这种冲突的概率尽可能小。

桌上有十个苹果，要把这十个苹果放到九个抽屉里，无论怎样放，我们会发现至少会有一个抽屉里面放不少于两个苹果。这一现象就是我们所说的“抽屉原理”。抽屉原理的一般含义为：“如果每个抽屉代表一个集合，每一个苹果就可以代表一个元素，假如有n+1个元素放到n个集合中去，其中必定有一个集合里至少有两个元素。” 抽屉原理有时也被称为鸽巢原理。它是组合数学中一个重要的原理。

3、Hash碰撞的解决方案

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

3.1 链地址法

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

链地址在处理的流程如下：
添加一个元素的时候，首先计算元素key的hash值，确定插入数组中的位置。如果当前位置下没有重复数据，则直接添加到当前位置。当遇到冲突的时候，添加到同一个hash值的元素后面，行成一个链表。这个链表的特点是同一个链表上的Hash值相同。java的数据结构HashMap使用的就是这种方法来处理冲突，JDK1.8中，针对链表上的数据超过8条的时候，使用了红黑树进行优化。由于篇幅原因，这里不深入讨论相关数据结构。

https://blog.csdn.net/weixin_41563161/article/details/105104239

3.2 开放地址法  

开放地址法是指大小为 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）来表示空位的多少。

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

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

                                                                          开放地址-线性探测法

这里的两种算法的区别是2这个元素，在链表法中还是在节点2的位置上，但是在线性探测法遇到冲突时会将冲突数据放到下一个空的位置下面。

4、hash算法在日常活动中的应用

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

4.1 信息加密

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

这里也友情提示一下大家：如果在使用中发现某网站还有提供找回密码的功能，就要好好担心下这个网站的安全性了。

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

25f9e794323b453885f5181f1b624d0b

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

 

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

 

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

这里也留给大家一个思考点，如果恶意用户直接抓取了你的活动参与链接，也就是拿到了你计算后的hash值，那从技术的角度上说，我们还有没有其他可以提升恶意用户的违法成本呢？

 

4.2 数据校验

 

布隆过滤器

布隆过滤器被广泛用于黑名单过滤、垃圾邮件过滤、爬虫判重系统以及缓存穿透问题。对于数量小，内存足够大的情况，我们可以直接用hashMap或者hashSet就可以满足这个活动需求了。但是如果数据量非常大，比如5TB的硬盘上放满了用户的参与数据，需要一个算法对这些数据进行去重，取得活动的去重参与用户数。这种时候，布隆过滤器就是一种比较好的解决方案了。

布隆过滤器其实是基于bitmap的一种应用，在1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数，用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都远远超过一般的算法，缺点是有一定的误识别率和删除困难，主要用于大数据去重、垃圾邮件过滤和爬虫url记录中。核心思路是使用一个bit来存储多个元素，通过这样的方式来减少内存的消耗。通过多个hash函数，将每个数据都算出多个值，存放在bitmap中对应的位置上。

布隆过滤器的原理见下图所示：

布隆过滤器原理示意

上图所示的例子中，数据a、b、c经过三次hash映射后，对应的bit位都是1，表示这三个数据已经存在了。而d这份数据经过映射后有一个结果是0，则表明d这个数据一定没有出现过。布隆过滤器存在假阳率（判定存在的元素可能不存在）的问题，但是没有假阴率（判断不存在的原因可能存在）的问题。即对于数据e，三次映射的结果都是1，但是这份数据也可能没有出现过。

误判率的数据公式如下所示：

其中，p是误判率，n是容纳的元素，m是需要的存储空间。由公示可以看出，布隆过滤器的长度会直接影响误报率，布隆过滤器越长其误报率越小。哈希函数的个数也需要权衡，个数越多则布隆过滤器 bit 位置位 1 的速度越快，且布隆过滤器的效率越低；但是如果太少的话，则会导致误报率升高。

参考文献

https://mp.weixin.qq.com/s/fpgLeo2ba4WiVD0Dd24MFA