GeoHash
July 28, 2017
在做Redis页面控制台命令支持的过程中，对于Redis的GEO模块突然很感兴趣，不明白这个数据结构为什么突然就跟Set、Sorted Set一起出现了。然后发现这个数据结构居然是用来存地理位置信息的，很不简单，要看一下到底是什么幺蛾子。
Geo模块专用于存储地理位置信息，突出的有点是可以快速获取某一地理位置附近的相关位置信息。比如你要在某个地方找吃的，搜索附近2km的餐厅，后台使用的就是GeoHash的算法，Redis原生就支持这个数据算法结构，可见其应用场景支持非常丰富，有很大的应用空间。
GeoHash算法 #
其实这个原理是很简单的，对于地理位置信息，一般我们用经纬度来表示，这就将球面转换成了一个二维平面。在二维平面快速的定位一个位置并查找周围位置信息，就是这个算法解决的主要问题。、
传统的我们可能用一种树结构来搞，但是那样的时间效率和空间效率都不高。
GeoHash过程 #
Geohash的主要过程就是将经纬度信息Hash成一个字符串。
- 将经纬度各自Hash成一个二进制串。
- 将两个串插叠，奇数位插维度串，偶数位插经度串。
- 将该串用
base32进行编码生成字符串。
原理 #
在第一步中主要用二分的方法来Hash生成二进制串。例如对于维度：北纬30，其在北纬第一位设成1，由位于0-45所以第二位为0，这样一直做20次二分，就可以得到一个长度是20的串。
对于精度同样这样做一遍。
然后插叠得到一个长度为40的二进制串，然后用base32方式编码生成一个长度为8的字符串。
将这个字符串存下来就好啦。
Geohash特性 #
由过程可以看出来，这个Hash出来的字符串的特性，就是相同区域的两个点的Hash结果前缀一致。这样当我们要查找某个位置周围2km的餐厅只要匹配到字符串的前5位相同就可以了。
边缘误差 #
这个算法是存在边缘误差的，因为如果两个点相距的很近，但是在二分的过程中分在不同的两块中，这样的Hash结果就相差很大, 如下图中的红点位置与两个绿点位置。
解决这个问题的方式也很直观。
当我们在查找某一点周围的地理位置的时候，将其对应的周围8块区域的点都取出来，然后计算一下距离做个筛选就可以了。 这个区域的点并不会太大。
这些小算法还是很好玩的。