一文讲懂GeoHash技术(一)

本文主要是讲GeoHash的技术原理及应用，在第二篇文章将会带大家从0到1实现GeoHash。
第二篇文章（代码实现）请移步从0到1实现GeoHash

1GeoHash背景

1.1背景问题

现在到饭点了家人们，暮雨c同学决定今天不点外卖出去吃，出门觅食肯定要有地图APP指路，于是我打开了我的地图导航

这时候我突然有一个疑问，在地图APP中，是怎么对这些饭店精准定位并推送的呢？而且为什么换一个定位找附近的餐馆还是这么快呢？

1.2 暴力解法

作为一个优秀的计算机同学，我们第一想法肯定是暴力遍历（bushi），由于我是在上海，上海是完全的二维化，可以用经纬坐标来表示，和重庆这种三维的不太一样。

暴力解法的步骤也比较简单：

• 先把所有餐馆的经纬坐标放到一个list里
• 然后获取用户的经纬坐标以及用户的要求最远距离
• 遍历list的所有坐标并计算和用户的距离
• 求出小于用户要求最远距离的饭店集合

这实现起来也很简单我就不贴伪代码了。

虽然说简单，但是问题也很明显，全球得有多少饭店啊，不得好几亿吗，每次范围搜索都要遍历这几亿的数据，先不说用户得等多少时间，你的服务器集群是肯定受不了的，所以这种方式显然不太行。

1.3 哈希解法

要说快的话，我们自然而然的就想起来用哈希，这也确实是一种可行解，但是哈希的关键就是如何设计合理的哈希策略，避免哈希碰撞。

如果说你的哈希函数哈希冲突非常严重，那其实就退化成暴力算法了，而且哈希怎么进行范围查询呢？我们知道目前很多数据库引擎用b+树不用哈希的很重要的原因就是哈希没法进行范围查询。

上述两个问题，一个可能退化成暴力，一个如何进行范围查询，这两个问题就是我们今天所探讨的GeoHash所解决的主要问题。我先提前说一下GeoHash的大致思路，就是把坐标一维化，把二维坐标编程一串索引，然后通过索引的前缀（是不是很自然的想到了前缀树，这很重要，我们在下一篇从0到1实现GeoHash的文章中会用到）来确定是否在一个区域内。

我先简单的举几个GeoHash的例子，xdm可以先提前想一下是怎么进行哈希转换的

经纬度具体忘了的xdm可以看一眼初中地理，毕竟这个东西还是在生活中经常用的

2 GeoHash实现原理

和xdm探讨完第一章后，肯定大家都有一个疑惑，为什么GeoHash能把二维坐标转换为一维索引呢？而且还不会发生哈希冲突，太神奇了这

下面我们一起来学习一下这个算法的原理

2.1 地球其实是矩形（dog）

地球当然不是矩形的，是椭圆形的，但是在我们计算机的眼里，地球就是矩形的

地球在纵向上由 -90°~90° 的纬度范围组成,在横向上由 -180°~180° 的经度范围组成. 因此我们把球面投影成一个矩形平面后，矩形的宽、高刻度就分别对应着经度和纬度，宽度方向上自左向右以 -180°为起点，180°为终点，每个刻度的单位为 1° 经度；高度自底向上以 -90°为起点，90°为终点，每个刻度单位为 1° 纬度.

2.2 把经纬度进行二分

如何把经纬度转换成一维坐标呢？GeoHash的思路就是不断二分，再利用二进制来进行处理，最终得到一个二进制索引串

2.2.1 经度拆分

具体来说步骤呢就是
• 第一轮：经度范围为 -180°-180° 拆成-180-0以及 0°~180° 两部分，如果经度从属于前者，则令首个 bit 位取 0，否则令首个 bit 位取 1；

• 第二轮：-180~°0° 可以拆分为 -180°~-90° 和 -90°~0°，如果经度从属于前者，则令第二个 bit 位取 0，否则令第二个 bit 位取 1；0°~180° 可以拆分为 0°~90° 和 90°~180°，前者令第二个 bit 位取 0，后者令第二个 bit 位取 1

• 第 3 ~ N 轮：重复上述步骤的思路，最终递归二分，将经度表示成一个由二进制数字组成的字符串

func binary(begin int , end int){
	if(begin==end){
		return
	}
	arg[begin][0.5*(end+begin)]=0
	arg[0.5*(end+begin)][end]=1
	binary(begin,0.5*(end+begin))
	binary(0.5*(end+begin),end)
}

上述代码是伪代码哈，没有说明终止位数，下一篇文章会给出全部代码

2.2.2 纬度拆分

这个就和经度一样了

然后地球就成了
拆完之后，要想把这两组二进制数改成一组，应该怎么办呢，我们按照经度字符串+纬度字符串依次交错排列的形式，将其组织在一起，最终形成一个一维字符串，那我们的A块的索引就是0000 B块就是0100 E块就是0010 依次类推
ps：斜体是经度

2.2.3 最终结果

有上文我们可以知道，索引越长，我们分的块就越少反之。

如果说两个块有相同前缀，我们就可以认为他在同一个大块中，比如说A和B。他们有公共前缀00，所以他们都属于00表示的这个大块中。

综上，我们得知这个一维字符串具有前缀索引的性质，他能够保证两个字符串前缀匹配位数越长，两个矩形块的相对位置就越靠近。

这肯定会存在一些问题，后面会具体来说

2.3 如何进行编码映射

具体来说的话GeoHash一般都是用Base32编码格式的，因为我们如果直接用经纬度映射结果的话映射结果有点太长了，要注意我们平常精确读书是要精确到小数点后三位的，也就是几十位映射结果甚至上百位。

所以采取Base32的编码格式来进行映射，在生成的二进制串中，从左向右开始，一次取五位，不足五位则在前补0（注意是不是在后，不影响映射数值），然后5个二进制数的十进制从0到31依次对应10 个数字字符 ‘0’-‘9’ 加上 26 个英文字母 ‘A’-‘Z’ 。

比如我们在第一章提到的YJXY433V A点对应十进制串就是30 17 29 30 4 3 3 27，二进制串大家就自己算吧。

2.4 长度决定精度

在 geohash 字符串中，字符串的长度决定了矩形块的大小，进一步决定了距离的精度. 在对经纬度进行递归二分时，每多一轮二分，矩形一个方向上的边长就会减半，因此矩形区域就越小，对应的精度就越高。

从小徐先生的编程世界中截的图，大家可以看一下

3 GeoHash步骤

来具体梳理一下GeoHash的步骤

• 获取目标经纬度
• 将经度按所需精度二分获得二进制串
• 将纬度按所需纬度二分获得二进制串
• 经前两步获得的两个二进制串进行Base32编码
• 进行查询等其他操作

看起来还是很简单的，具体实现会放在本系列的下一章来讲

4 常见问题

矩形块大小的问题

比如说还是这张图

我们在矩形块F的右上边缘，那么显然块I以及J都会有和我们距离比较近的点，但显然F和IJ的公共前缀是不够的，但是距离是要比F点内左下角要小很多的。

针对这个问题，显然矩形块的大小不能随便的继续减小，不然可能会出现距离的问题，所以我们一般是通过geohash 锁定一个小的矩形块后，以其作为中心，将周围 8 个矩形块范围内的点也同时检索出来，再根据实际的相对距离进行过滤。

范围检索
前面提到过GeoHash很重要的一点就是能进行范围检索
应用 geohash 技术的一类场景是：给定一个指定位置作为中心点，想要检索出指定半径范围内的所有点集合.

这是我们的思路一般是，获得中心块的GeoHash的哈希串，然后以九宫格的方向向外扩展，直到满足覆盖中心点按要求半径所形成的圆，这样做肯定会有多余结果，我们再通过与中心点的距离进行过滤，当然不是过滤全部，只过滤边缘块。

对于第四章这个话题肯定还有其他问题，欢迎评论区或者私信交流

本文主要讲的是GeoHash的技术原理，相信看完本文肯定会有比较深入的了解，下一篇文章我会带大家从0到1实现GeoHash

本文主要学习：小徐先生的编程世界