随着移动互联网的发展，很多基于地理位置信息的服务越来越受欢迎。比如我们平时用它来找附近的人，或者附近的饭店、共享单车等等。那么，大家有没有想过这个搜索功能是如何实现的呢？作为一个受过高等教育的人，大家肯定第一时间想到可以通过经纬度进行计算。具体算法类似这样：地球近似为一个球体，地球赤道的周长约为40075.04公里，半径约为6371公里。因此，距离很容易通过立体几何的方法计算出来，例如最常见的大圆距离（Great-CircleDistance）。公式如下：式中R为地球半径，Aj和Aw分别代表A点的经度和纬度；Bj和Bw分别代表B点的经度和纬度。这样，它的距离可以很容易地用简单的立体几何方法计算出来。如果对地理信息比较了解的人，也会知道哈弗正弦公式（Haversineformula），因为大圆距离公式使用了大量的余弦函数，所以当两点之间的距离太短时，会导致到比较大的舍入误差。而haversine公式采用的是正弦函数的方法，所以即使距离太小，也可以保留足够的有效数字。haversine公式的形式如下：式中R为地球半径，取平均值6371km；φ1、φ2表示两点的纬度；Δλ表示两点的经度差。有了这些算法，理论上找附近的人就很方便了。但是为什么说理论上呢？因为在工程实践中，这样的搜索计算量太大。几个经纬度的数据还可以，但是对于大规模的数据查询，就不实用了。例如，如果要找出百万条数据的数据库5公里以内有哪些餐厅，对一百万条数据进行各种三角运算显然是不现实的，更不用说应用在该数据库上的数据量了。互联网比一百万块大得多。而且，这样的数据也很难优化其查询效率。那么，如何解决这个问题呢？这就是我们今天要介绍的神奇算法，Geohash算法。通过Geohash算法，我们可以将两个坐标的距离计算简化为两个字符串的比较，从而最大限度的应用更快的字符串相关函数，对它们进行排序或索引。我们来看看Geohash算法是如何做到的。Geohash的本质是将整个使用的地图区域划分为矩形，然后在每个矩形中再次进行矩形划分，每次划分中的区域用一个字符表示，这样每次划分后，最大可能近似于实际坐标位置。而这个坐标可以用一串字符代替。在常用的Geohash算法中，每个字符用5位来标识，所以会有32种不同的组合（0-31），所以我们可以把这个地图区域分成32个区域。这样划分之后，按照第一个字母划分的区域如下图所示：然后我们继续划分每个区域，我们会得到一个类似于wx4eqzrx的字符串。这时候我们可以方便的使用类似的sql语句：Select*fromwheregeohashlike'wx4eqw%';查询附近我们要查询的东西。是不是很方便？通过这种方式，我们将复杂的三角函数计算转化为字符串运算，计算处理效率非常高。那么，大家肯定要问了，生成的坐标是如何转换成字符串的呢？其实很简单。我们以纬度39.928167为例。A。首先，我们将区间[-90,90]划分为[-90,0]，[0,90]，称为左右区间。可以确定39.928167属于右区间[0,90]，标记为1b。然后将区间[0,90]划分为[0,45),[45,90]，可以确定39.928167属于左边区间[0,45)，标记为0c。上面的递归过程39.928167总是属于某个区间[a,b]。由于每次迭代的区间[a,b]一直在缩小，而且越来越接近39.928167，划分的越多，距离越精确，字符串也越长，如下图所示：方式，我们得到了纬度的二进制表示，我们也可以进行经度的二进制表示。然后，我们把经度放在偶数，纬度放在奇数，将两个二进制串合并在一起，最后将得到的二进制串每5位进行base32编码，最后得到我们想要的。对于每个由一个小方块表示的Geohash字符串序列。但是这样做之后很多人会发现一个问题，就是每一个Geohash字符串其实都代表一个小方块，然后就会出现越界的问题。就像下图中的红点，它和上面的绿点不在同一个格子里，所以如果我们只查询红点所在的格子，是查询不到上面的绿点的显然离它很近，反而下面的绿点离得远一点可以查询。那么如何解决这个问题呢？其实也很简单，就是查询的时候考虑周围的8个格子，一起查询。你是怎么做到的？我们可以看到周围的8个格子本质上就是经纬度二进制数和中间的格子相差1，所以我们只需要对红点的经纬度二进制数加减1即可也可以获取附近的Gridded字符串。这样做本质上会失去网格的准确性。在经纬度位数足够的情况下，这个误差可以忽略不计。通过计算，我们可以得出：在纬度相等的情况下，经度每0.00001度的距离相差约1米；在经度相等的情况下，纬度每0.00001度的距离相差约1.1米；当号码为9位时，距离为2米左右；如果是8位数字，就是附近19米左右。对于大多数人来说，可以说是可以接受的错误。
