在数据校验方面的另一个应用场景就是版权的保护或者违禁信息的打击，比如某个小视频，第一个用户上传的时候，我们认为是版权所有者，计算一个hash值存下来。当第二个用户上传的时候，同样计算hash值，如果hash值一样的话，就算同一个文件。这种方案其实也给用户传播违禁文件提高了一些门槛，不是简单的换一个名字或者改一下后缀名就可以躲避掉打击了。（当然这种方式也是可以绕过的，图片的你随便改一下颜色，视频去掉一帧就又是完全不同的hash值了。注意：我没有教你变坏，我只是和你在讨论这个技术。。。）另外我们在社区里，也会遇到玩家重复上传同一张图片或者视频的情况，使用这种校验的方式，可以有效减少cos服务的存储空间。
大文件分块校验
使用过bt的同学都有经验，在p2p网络中会把一个大文件拆分成很多小的数据各自传输。这样的好处是如果某个小的数据块在传输过程中损坏了，只要重新下载这个块就好。为了确保每一个小的数据块都是发布者自己传输的，我们可以对每一个小的数据块都进行一个hash的计算，维护一个hash List，在收到所有数据以后，我们对于这个hash List里的每一块进行遍历比对。这里有一个优化点是如果文件分块特别多的时候，如果遍历对比就会效率比较低。可以把所有分块的hash值组合成一个大的字符串，对于这个字符串再做一次Hash运算java集合中的hash算法java集合中的hash算法 从hash算法的原理和实际应用等几个角度，对hash算法进行一个讲解，得到最终的hash（Root hash）。在实际的校验中，我们只需要拿到了正确的Root hash，即可校验Hash List，也就可以校验每一个数据块了。
大文件分块示意图
4.3 负载均衡
活动开发同学在应对高星级业务大用户量参与时，都会使用分库分表，针对用户的进行取模，就可以得到对应的用户分库分表的节点了。
活动分库分表示意图
如上图所示，这里其实是分了10张表，计算后的hash值取模10java集合中的hash算法，得到对应的分表，在进行后续处理就好。对于一般的活动或者系统，我们一般设置10张表或者100张表就好。
下面我们来看一点复杂的问题，假设我们活动初始分表了10张，运营一段时间以后发现需要10张不够，需要改到100张。这个时候我们如果直接扩容的话，那么所有的数据都需要重新计算Hash值，大量的数据都需要进行迁移。如果更新的是缓存的逻辑，则会导致大量缓存失效，发生雪崩效应，导致数据库异常。造成这种问题的原因是hash算法本身的缘故，只要是取模算法进行处理，则无法避免这种情况。针对这种问题，我们就需要利用一致性hash进行相应的处理了。
一致性hash的基本原理是将输入的值hash后，对结果的hash值进行2^32取模，这里和普通的hash取模算法不一样的点是在一致性hash算法里将取模的结果映射到一个环上。将缓存服务器与被缓存对象都映射到hash环上以后，从被缓存对象的位置出发，沿顺时针方向遇到的第一个服务器，就是当前对象将要缓存于的服务器，由于被缓存对象与服务器hash后的值是固定的，所以，在服务器不变的情况下，一个必定会被缓存到固定的服务器上，那么，当下次想要访问这个用户的数据时，只要再次使用相同的算法进行计算，即可算出这个用户的数据被缓存在哪个服务器上，直接去对应的服务器查找对应的数据即可。这里的逻辑其实和直接取模的是一样的。如下图所示：
初始3台机器的情况
初始情况如下：用户1的数据在服务器A里，用户2、3的数据存在服务器C里，用户4的数据存储在服务器B里
下面我们来看一下当服务器数量发生变化的时候，相应影响的数据情况：
服务器缩容
服务器缩容
服务器B发生了故障，进行剔除后，只有用户4的数据发生了异常。这个时候我们需要继续按照顺时针的方案，把缓存的数据放在用户A上面。
服务器扩容
同样的，我们进行了服务器扩容以后，新增了一台服务器D，位置落在用户2和3之间。按照顺时针原则，用户2依然访问的是服务器C的数据，而用户3顺时针查询后，发现最近的服务器是D，后续数据就会存储到d上面。
服务器扩容示意图
虚拟节点
当然这只是一种理想情况，实际使用中，由于服务器节点数量有限，有可能出现分布不均匀的情况。这个时候会出现大量数据都被映射到某一台服务器的情况，如下图左侧所示。为了解决这个问题，我们采用了虚拟节点的方案。虚拟节点是实际节点（实际的物理服务器）在hash环上的复制品，一个实际节点可以对应多个虚拟节点。虚拟节点越多，hash环上的节点就越多，数据被均匀分布的概率就越大。
虚拟节点示意图
如右图所示，B、C、D 是原始节点复制出来的虚拟节点，原本都要访问机器D的用户1、4，分别被映射到了B,D。通过这样的方式，起到了一个服务器均匀分布的作用。
5、几种hash算法的扩展应用
下面介绍几种大家可能不经常遇到的应用，由于篇幅原因，不做深入介绍，只抛砖引玉。
5.1
是用于海量文本去重的一种方法，它是一种局部敏感hash。那什么叫局部敏感呢，假定两个字符串具有一定的相似性，在hash之后，仍然能保持这种相似性，就称之为局部敏感hash。普通的hash是不具有这种属性的。被用来在海量文本中去重。
算法的思路大致如下：
将Doc进行关键词抽取(其中包括分词和计算权重)，抽取出n个(关键词，权重)对， 即图中的多个(, )。记为 = [fw1, fw2 … fwn]，其中 fwn = (,)。
对每个中的进行hash。然后对进行位的纵向累加，如果该位是1，则+,如果是0，则-，最后生成个数字，大于0标记1，小于0标记0
最后转换成一个64位的字节，判断重复只需要判断他们的特征字的距离是不是
计算流程
如下图所示，当两个文本只有一个字变化时，如果使用普通Hash则会导致两次的结果发生较大改变，而的局部敏感特性，会导致只有部分数据发生变化。
结果
5.2
将地球作为为一个二维平面进行递归分解。每个分解后的子块在一定经纬度范围内拥有相同的编码。以下图为例，这个矩形区域内所有的点（经纬度坐标）都共享相同的字符串，这样既可以保护隐私（只表示大概区域位置而不是具体的点），又比较容易做缓存。
示意图
下面以一个例子来理解下这个算法，我们对纬度39.3817进行逼近编码 ：
地球纬度区间是[-90,90]，对于这个区间进行二分划分左区间[-90,0), 右区间[0,90]。39.3817属于右区间，标记为1
将右区间[0,90]继续进行划分，左区间[0,45) ,右区间[45,90]。39.3817属于左区间，标记为0
递归上面的过程，随着每次迭代，区间[a，b]会不断接近39.3817。递归的次数决定了生成的序列长度。
对于经度做同样的处理。得到的字符串，偶数位放经度，奇数位放纬度，把2串编码组合生成新串。对于新串转成对应10进制查出实际的编码就是类似WX4ER的hash值。
整体递归过程如下表所示：
这里有一篇文章详细介绍了，有兴趣的同学可以移步这里：
是什么能让 APP 快速精准定位到我们的位置？
5.3 布隆过滤器
布隆过滤器被广泛用于黑名单过滤、垃圾邮件过滤、爬虫判重系统以及缓存穿透问题。对于数量小，内存足够大的情况，我们可以直接用或者就可以满足这个活动需求了。但是如果数据量非常大，比如5TB的硬盘上放满了用户的参与数据，需要一个算法对这些数据进行去重，取得活动的去重参与用户数。这种时候，布隆过滤器就是一种比较好的解决方案了。
布隆过滤器其实是基于的一种应用，在1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数，用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都远远超过一般的算法，缺点是有一定的误识别率和删除困难，主要用于大数据去重、垃圾邮件过滤和爬虫url记录中。核心思路是使用一个bit来存储多个元素，通过这样的方式来减少内存的消耗。通过多个hash函数，将每个数据都算出多个值，存放在中对应的位置上。
布隆过滤器的原理见下图所示：
布隆过滤器原理示意
上图所示的例子中，数据a、b、c经过三次hash映射后，对应的bit位都是1，表示这三个数据已经存在了。而d这份数据经过映射后有一个结果是0，则表明d这个数据一定没有出现过。布隆过滤器存在假阳率（判定存在的元素可能不存在）的问题，但是没有假阴率（判断不存在的原因可能存在）的问题。即对于数据e，三次映射的结果都是1，但是这份数据也可能没有出现过。
误判率的数据公式如下所示：
其中，p是误判率，n是容纳的元素，m是需要的存储空间。由公示可以看出，布隆过滤器的长度会直接影响误报率，布隆过滤器越长其误报率越小。哈希函数的个数也需要权衡，个数越多则布隆过滤器 bit 位置位 1 的速度越快，且布隆过滤器的效率越低；但是如果太少的话，则会导致误报率升高。
6、总结
Hash算法作为一种活动开发经常遇到的算法，我们在使用中不仅仅要知道这种算法背后真正的原理，才可以在使用上做到有的放矢。Hash的相关知识还有很多，有兴趣的同学可以继续深入研究。