hash 算法原理及应用漫谈( 四 ) _hash算法

服务器扩容

同样的，我们进行了服务器扩容以后，新增了一台服务器D，位置落在用户2和3之间。按照顺时针原则，用户2依然访问的是服务器C的数据，而用户3顺时针查询后，发现最近的服务器是D，后续数据就会存储到d上面。

文章插图
服务器扩容示意图

虚拟节点
当然这只是一种理想情况，实际使用中，由于服务器节点数量有限，有可能出现分布不均匀的情况。这个时候会出现大量数据都被映射到某一台服务器的情况，如下图左侧所示。为了解决这个问题，我们采用了虚拟节点的方案。虚拟节点是实际节点（实际的物理服务器）在hash环上的复制品，一个实际节点可以对应多个虚拟节点。虚拟节点越多，hash环上的节点就越多，数据被均匀分布的概率就越大。

文章插图
虚拟节点示意图
如右图所示，B、C、D 是原始节点复制出来的虚拟节点，原本都要访问机器D的用户1、4，分别被映射到了B,D 。通过这样的方式，起到了一个服务器均匀分布的作用。
5、几种hash算法的扩展应用
下面介绍几种大家可能不经常遇到的应用，由于篇幅原因，不做深入介绍，只抛砖引玉。
5.1 SimHash
simHash是google用于海量文本去重的一种方法，它是一种局部敏感hash 。那什么叫局部敏感呢，假定两个字符串具有一定的相似性，在hash之后，仍然能保持这种相似性，就称之为局部敏感hash 。普通的hash是不具有这种属性的。simhash被Google用来在海量文本中去重。
simHash算法的思路大致如下：

将Doc进行关键词抽取(其中包括分词和计算权重)，抽取出n个(关键词，权重)对，即图中的多个(feature, weight) 。记为 feature_weight_pairs = [fw1, fw2 … fwn]，其中 fwn = (feature_n,weight_n) 。
对每个feature_weight_pairs中的feature进行hash 。然后对hash_weight_pairs进行位的纵向累加，如果该位是1，则+weight,如果是0，则-weight，最后生成bits_count个数字，大于0标记1，小于0标记0
最后转换成一个64位的字节，判断重复只需要判断他们的特征字的距离是不是

文章插图
SimHash计算流程
如下图所示，当两个文本只有一个字变化时，如果使用普通Hash则会导致两次的结果发生较大改变，而SimHash的局部敏感特性，会导致只有部分数据发生变化。

文章插图
SimHash结果
5.2 GeoHash
GeoHash将地球作为为一个二维平面进行递归分解。每个分解后的子块在一定经纬度范围内拥有相同的编码。以下图为例，这个矩形区域内所有的点（经纬度坐标）都共享相同的GeoHash字符串，这样既可以保护隐私（只表示大概区域位置而不是具体的点），又比较容易做缓存。

文章插图
GeoHash示意图
下面以一个例子来理解下这个算法，我们对纬度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进制查出实际的base32编码就是类似WX4ER的hash值。

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

文章插图
这里有一篇文章详细介绍了GeoHash，有兴趣的同学可以移步这里：
是什么能让 App 快速精准定位到我们的位置？
5.3 布隆过滤器
布隆过滤器被广泛用于黑名单过滤、垃圾邮件过滤、爬虫判重系统以及缓存穿透问题。对于数量小，内存足够大的情况，我们可以直接用hashMap或者hashSet就可以满足这个活动需求了。但是如果数据量非常大，比如5TB的硬盘上放满了用户的参与数据，需要一个算法对这些数据进行去重，取得活动的去重参与用户数。这种时候，布隆过滤器就是一种比较好的解决方案了。