看到了这篇文章有种相见恨晚的感觉~之前上cloud computing纠结consistent hashing，做地图搜索也用到了geohash的知识，有时间再把consistent hashing复习一下。
1. 一致性哈希
一致性哈希算法是在1997年由麻省理工学院提出，设计的目标是为了解决因特网的热点问题。一致性哈希算法解决了在P2P环境中最为关键的问题，即如何在动态的网络拓扑中分布存储和路由。在分布式系统中用得比较广泛，当集群需要添加机器或者减少一台机器时，一致性哈希只影响一台机器，将数据受影响的机器数量降到最低。
在这里讲述了一致性哈希的原理，并且在最后有各种语言版本的实现。在Github上也有一个不错的实现版本。
2. 局部敏感哈希
局部敏感哈希是一种高维数据索引技术。英文名为Locality-Sensitive Hashing，简记为LSH，应用于计算机很多领域。想象在一个高维数据检索系统中，检索库中数据量很大，每条数据的维度也很高。常规的做法就是针对每一次检索，都从数据库中进行一一匹配，这样将花费大量的时间和空间，显然不可取。
然后，我们就可以从两个方面考虑：
（1）通过一些算法对原始高维数据进行降维
（2）在检索初始阶段排除一些数据，减少检索时的比较次数
针对（2）有局部敏感Hash恰好满足了我们的要求。它的原理也容易理解。局部敏感哈希的实现有多种方式。需要注意的是上述方法并不能够一定保证查找到查询点的最邻近的数据，而是减少需要匹配的数据点个数的同时保证查找到最近邻的数据点的概率很大。为了解决这个问题，又提出了增强LSH。
关于p-stableLSH算法可以参考这里。最后附上Java实现的局部敏感哈希工具。
3. Geohash
想象这样一个场景，你在北京西二旗附近想找附近的餐馆，只需要在手机上打开手机地图，然后搜索附近的餐馆就可以进一步找到你所满意的一家。那么问题来了，地图后台是如何根据自己的位置来搜索附近的餐馆呢？接下来的Geohash算法就是用来解决这个问题的，它将二维的经纬度转化为一个字符串。参见其原理详细介绍。
在github上有一个geohash的C语言实现代码，并且附上了使用方法。Google有一个开源的Geohash代码，详
见链接：http://Python-geohash.googlecode.com/svn/trunk/，包括Python和C++实现。
网友评论