说到哈希，相信大多数同学都会比较熟悉。 区块链是一项以前非常流行、现在仍然非常流行的技术，其背后的基本原理之一就是哈希。 下面从哈希算法的原理和实际应用几个角度来阐述： 对哈希算法进行解释。 1.什么是哈希？

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

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

在本例中，这是一个测试副本，即原始值，即通过哈希算法得到的哈希值。 Hash算法的整个过程就是将原来任意长度的值空间映射到固定长度的值空间的过程。

2. 哈希的特点

优秀的哈希算法需要哪些条件？

桌子上有十个苹果。 我们需要把这十个苹果放进九个抽屉里。 不管我们怎么摆放，我们都会发现至少有一个抽屉，里面至少有两个苹果。 这种现象就是我们所说的“抽屉原理”。 抽屉原则的大致含义是：“如果每个抽屉代表一个集合，那么每个苹果可以代表一个元素。如果n个集合中放置了n+1个元素，那么一个集合中必须至少有两个元素。 ” 抽屉原理有时也称为鸽子洞原理。它是组合数学中的一个重要原理 3. 哈希碰撞的解决方案

前面提到，哈希算法肯定会产生冲突，那么如果遇到需要解决的哈希冲突怎么办呢？ 比较常用的算法是链地址法和开放地址法。

3.1 链地址法

链表寻址方式使用链表数组来存储对应的数据。 当哈希遇到冲突时，将其添加到链表的后面进行处理。

链地址的处理过程如下：

添加元素时，首先计算元素key的哈希值，以确定插入数组的位置。 如果当前位置没有重复数据，则直接添加到当前位置。 遇到冲突时，将其添加到具有相同哈希值的元素末尾，形成链表。 这种链表的特点是同一个链表上的Hash值是相同的。 Java的数据结构就是用这种方法来处理冲突的。 在JDK1.8中，当链表上的数据超过8个时，就会使用红黑树进行优化。 由于篇幅原因，我们这里不深入讨论相关的数据结构。 有兴趣的同学可以参考这篇文章：

《Java宝典一——》

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 的意思是：到达表底后，回到表顶，从头开始。

对于开放寻址冲突解决方法，除了线性检测方法外，还有另外两种比较经典的检测方法，二次检测（ ）和双重哈希（ ）。 但无论采用哪种检测方法，当哈希表中空闲位置不多时，哈希冲突的概率都会大大增加。 为了尽可能保证哈希表的运行效率，一般情况下，我们会尽力保证哈希表中有一定比例的空闲槽。 我们用负载系数（load）来表示职位空缺的数量。

哈希表的加载因子=表中填充的元素数量/哈希表的长度。 负载因子越大，冲突越多，性能越差。

3.3 两种方案的Demo示例

假设哈希长度为8，哈希函数H(K)=K mod 7，给定关键字序列为{32,14,23,2, 20}

使用链表方法时，对应的数据结构如下图：

当使用线性检测方法时，对应的数据结果如下所示：

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

4.哈希算法在日常活动中的应用

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

4.1 信息加密

首先我们看一下信息加密的应用。 2011年，CSDN下架事件导致超过600万用户密码泄露。 令人失望的是，CSDN以明文形式存储用户的注册邮箱地址和密码。 作为用户非常私密的信息，最简单的保护措施就是对密码进行哈希处理。 在客户端，对用户输入的密码进行哈希处理，然后将用户密码的哈希值保存在服务器端的数据库中。 由于服务器不以明文形式存储密码，因此许多网站不再具有找回密码的功能。

看到这里，有的同学会想到，我们只要对用户输入的密码进行MD5加密即可。 这样，即使恶意用户知道哈希值，也没有办法获取用户的真实密码。 假设用户的密码为，经过一次md5后得到的值为：

那么用这个加密字符串来存储密码就万无一失了吗？ 理想总是很丰满，但现实总是很骨感。

你可以看一下这个网站：

/

下面是网站的介绍：

本站对md5、sha1等全球通用的加密算法进行反向查询，通过穷举的字符组合创建明文和密文对应的查询数据库。 大约创建了90万亿条记录，占用硬盘超过500TB。 查询成功率95%以上，很多复杂的密文只能在本站查询。已稳定运行十余年，在国内外享有很高的声誉。

所以一般对于这个问题，我们的解决方案是引入salt（加盐），即使用特殊字符（salt）和用户输入组成一个新的字符串进行加密。 这样就增加了反向查询的复杂度。 但这种方法并非万无一失。 如果盐泄露，所有使用盐的地方都需要重置密码。

盐泄漏问题其实还有另一种解决方案，那就是使用HMAC进行加密（Hash-based Code）。 该算法的核心思想是，用于加密的密钥是从服务器获取的，并且对于每个用户来说都是不同的。 如果发生泄露，那么只会泄露这个用户的信息，不会影响全局。

这里也是一个值得大家思考的点。 如果恶意用户直接抓取了你的活动参与链接，即得到了你计算出的哈希值，那么从技术角度来说，我们还有什么办法可以改善恶意用户的行为呢？ 违法成本怎么办？

4.2 数据验证

- git ID

用过git的同学应该知道，每次git提交都有一个ID，比如：

是一个git的结果，那么这个ID是怎么生成的呢？ 查阅相关资料后，可以使用以下代码查看：

printf "commit %s\0" $(git cat-file commit HEAD | wc -c); git cat-file commit HEAD

git ID主要包括以下部分：树hash、hash、作者信息和本次提交的评论。

对该信息进行SHA-1算法后，得到的值就是本次提交的ID。 简单来说，就是对单次提交中提交的头信息进行校验和。

Linux 创始人、Git 开发者 Linus 表示，Git 使用 sha1 不是为了安全，而是为了数据完整性； 它可以保证很多年后，当你在某个时刻重新启动它时，它一定和很多年一样。 当时的情况一模一样，完全值得信赖。

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

注：对git中的树等结构感兴趣的同学可以参考这篇文章《Git内部原理-Git对象》。 由于篇幅原因，这里就不深入分析了。

4.3 负载均衡

活动开发同学在处理高星级业务、大用户参与时，会用到分库、分表。 通过基于用户的模型，可以得到相应的用户子库和表的节点。

如上图所示，这里实际上有10张表。 计算出的哈希值模10得到对应的表，可以进行后续处理。 对于一般的活动或系统，我们通常设置10张桌子或100张桌子。

我们来看看一些复杂的问题。 假设我们的最初被分成10张表。 运行一段时间后，发现10张表不够用，需要改为100张表。 如果此时直接扩容，所有数据都需要重新计算哈希值，大量数据需要迁移。 如果更新缓存逻辑，会导致大量缓存失效、雪崩效应、数据库异常。 造成这个问题的原因是哈希算法本身。 只要采用取模算法进行处理，就无法避免这种情况。 为了解决这个问题，我们需要使用一致性哈希来进行相应的处理。

一致性哈希的基本原理是对输入值进行哈希，然后对所得哈希值执行模 2^32。 这里与普通哈希取模算法的区别在于，在一致性哈希算法中，取模结果被映射到一个环上。 将缓存服务器和缓存对象都映射到哈希环后，从缓存对象的位置开始，顺时针方向遇到的第一个服务器就是当前对象将被缓存的服务器。 由于缓存的对象和服务器的哈希值是固定的，所以如果服务器不变，肯定会在固定的服务器上缓存一个。 那么，下次想要访问用户的数据时，只需要使用相同的算法再次计算即可。 ，就可以计算出用户的数据缓存在哪台服务器上，去对应的服务器查找对应的数据即可。 这里的逻辑其实和直接取模是一样的。 如下所示：

初始情况如下：用户1的数据存储在服务器A中，用户2和3的数据存储在服务器C中，用户4的数据存储在服务器B中。

我们看一下服务器数量变化时会影响到的数据：

服务器 B 失败。 排除后，只有用户4的数据出现异常。 这时我们需要继续按照顺时针计划，将缓存的数据放到用户A上。

如右图所示，B、C、D是从原节点复制而来的虚拟节点。 用户1和4本来想访问机器D，分别映射到B和D。 这样服务器就分布均匀了。

5、几种哈希算法的扩展应用

下面介绍几个你可能不常遇到的应用。 由于篇幅原因，我们不会深入介绍它们，只是给出一些想法。

5.1

它是一种用于从大量文本中删除重复项的方法。 它是本地敏感的哈希。 那么什么是局部敏感度呢？ 假设两个字符串具有一定的相似性，并且经过哈希处理后仍能保持这种相似性，称为局部敏感性哈希。 普通的hash不具备这个属性。 它用于删除大量文本中的重复项。

算法的思路大致如下：

如下图所示，当两个文本中只有一个单词发生变化时，使用普通的Hash会导致两个结果发生较大变化，而局部敏感特性只会导致部分数据发生变化。

5.2

递归地将地球分解为二维平面。 每个分解的子块在一定的经纬度范围内具有相同的代码。 以下图为例。 该矩形区域中的所有点（纬度和经度坐标）共享相同的字符串。 这不仅可以保护隐私（它只代表该区域的大致位置而不是具体点），而且还使缓存更容易。

让我们举一个例子来理解这个算法。 我们对纬度 39.3817 进行近似编码：

整体递归流程如下表所示：

这里有一篇文章详细介绍了它。 有兴趣的同学可以去这里：

腾讯技术工程：APP如何快速定位我们的位置？深入了解算法及其实现

5.3 布隆过滤器

布隆过滤器广泛应用于黑名单过滤、垃圾邮件过滤、爬虫判断系统和缓存穿透问题。 对于数量较少，内存又足够大的情况，我们可以直接使用，也可以满足本次活动的需要。 但如果数据量非常大，比如5TB的硬盘里存满了用户参与数据，就需要一种算法对数据进行去重，获取活跃去重的参与用户数。 在这种情况下，布隆过滤器是一个更好的解决方案。

布隆过滤器实际上是基于布卢姆在1970年提出的一个应用程序。它实际上是一个长二进制向量和一系列随机映射函数，用于检索某个元素是否在集合中。 其优点是空间效率和查询时间远高于普通算法。 其缺点是有一定的误识别率和删除困难。 主要应用于大数据去重、垃圾邮件过滤、爬虫URL记录等方面。 核心思想是用一位存储多个元素，从而减少内存消耗。 通过多个哈希函数，为每个数据计算出多个值并存储在相应的位置。

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

上图所示的例子中，数据a、b、c经过3次哈希后，对应的位都为1，说明这3个数据已经存在。 d的数据映射后，有一个结果是0，也就是说d的数据之前肯定没有出现过。 布隆过滤器存在误报率问题（判断存在的元素可能不存在），但不存在漏报率问题（判断不存在的原因可能存在）。 即对于数据e，3次映射的结果都是1，但是这个数据之前可能没有出现过。

误报率的数据公式如下：

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

六、总结

哈希算法是活动开发中经常遇到的算法。 我们在使用的时候不仅要知道这个算法背后的真正原理，而且在使用时才能有的放矢。 关于Hash的相关知识还是很多的，有兴趣的同学可以继续深入研究。