Geohash

什么是Geohash

Geohash是一种通过将地球通过网格的形式切分之后的一种编码格式，可以将我们常用的经纬度转换为由数字和字母组成的字符串。

这个字符串存在一个特征，相近的地点（经纬度）其前缀是相同的。

生活中，可能我们用的更多的是经纬度，但是在诸如附近的人、附近的点这种场景下，遍历整个库的经纬度，然后通过Haversine或者Vincenty公式计算两点距离，再过滤出我们想要的数据，在大数据量的情况下，其查询速度是不能接受的。

由于Geohash具有空间邻近性的特征，对于临近区域的表示，其前缀是相同的。因此geohash非常适合用于计算地图上某个点x范围内的其他点，对应到实际应用就是附近的人、附近的店等等。

上面说到，Geohash的本质是一种编码，这个编码是用来表示地球上某一部分区域的。

日常生活中使用比较多的经纬度是以赤道和本初子午线的交接点作为(0,0)，南北各90度，东西各180度。但是这种表示是二维的，且存在负数和小数。如何处理这个负数和小数呢？

Geohash的做法是将经纬度进行多次二分，以纬度为例，-90到90，以中值为分界点，[-90,0）使用0表示，[0,90]使用1表示。而[0,90]，再次以中值为分界点，[0,45)使用0表示,[45,90]使用1表示，同理[-90,0]也是。如下图

以北京天安门广场为例，其经纬度是116.39767767426531, 39.90280407974144，进行15次二分之后可以得到下图的结果

经度的值是110100101100010，纬度的值是101110001100000。

第二步，在得到两个二进制表示之后，将其交错拼接，经度放在偶数位（0,2,4,6,8,….)，纬度放在奇数位(1,3,5,7,9,….)。下标从0开始，因此第一位应该是经度的首位，得到的结果是111001110100100011110000001000。

然后将其每5位进行一次分隔，得到11100 11101 00100 01111 00000 01000，再将每一部分转为10进制并进行base32编码，base32的映射参考下图，最终得到结果–wx4g08

可以通过网站 https://geohash.softeng.co/ ，来检测计算的是否正确。下图表示wx4g08这整个区域，由于只进行了15次二分，因此其覆盖范围并不能具体到原经纬度对应的位置

英文维基百科上有不同的精度大概的误差，参考下图。

就像把大象放进冰箱是一样的——打开冰箱，把大象放进去，关上冰箱。

geohash的计算也可以分为三步，

这里着重讲一下最重要的第二步，两个坐标糅合成一个值的本质上是将二维压缩为一维。

在数学和计算机学中，多维数据转换为一维，通常是由一种叫做空间填充曲线的函数来实现的；所谓空间填充曲线，就是可以在n维空间中经过这个空间中的每一个点的一条曲线，常见的有皮亚诺曲线，Z阶曲线，希尔伯特曲线等。Geohash编码可以说就是Z阶曲线的一种应用实现。

Z阶曲线，是基于分形思想，对空间进行递归的划分和连接，其特征就是其路径是由形似字符“Z”多次迭代组成。

如上图1-4阶的曲线，将正方形划分为1/4后依然可以以相同的方式进行处理，当分隔次数足够多之后，就可以填充整个正方形。

从坐标表示的角度来看，以正方形左上角为原点，在通过位交织的方式将（x,y)转换为Z值，这个Z阶曲线走过的路线，刚好是一维中自增的值（0，1，2，3，4…..)。如下图。

我在了解的时候一直在纠结为什么非要位交织呢？拍脑袋得出来的吗？

其实位交织就是Z阶曲线的数学标识。