前言
最近项目需要使用到通过用户的经纬度查询附近的地理位置，了解到geohash可以快速的查找附近的地点，就找时间了解下是geohash的实现方式。
geohash介绍
geohash能将地理位置编码成字母和数字组成字符串。每个字符串表示一个地图上的矩形区域，举行区域的大小取决于字符串的长度，长度越长，矩形区域越小。每个矩形区域中的位置都共享相同的geohash字符串。正因为如此，我们可以将geohash的字符串当做key，来存储所有的地理位置坐标。
上边提到字符串越长，表示的区域越小，也就是位置越精确。我们可以从geohash字符串的后边移除字符串来增大矩形区域的位置，当然也降低了经度。
geohash字符串相近的地点其距离也越近，相似前缀越长，两个地点越近。但也有特殊情况，地理位置近但其geohash字符串差别很大，这种情况在下边介绍。
主要用途
geohash主要用在如下两个场景：
- 将geohash字符串当做一个唯一的标识
- 用来表示地点数据，将其存储到数据库中
geohash也经常用于地理标记。
使用geohash有两个优点：一是用geohash索引的数据表示的是一个矩形区域中所有的点，在数据库中单个索引的效率也比多个索引高；二是我们可以使用geohash来进行快速但不精确的查询：geohash相近的字符串也有相近的距离。
算法和例子
geohash的字符串其实是base32的结果。
我们用ws104来作为例子说明如何从geohash解析成经纬度。
先使用base32对字符串ws104进行解码。
下面是base32的字符表：
| 十进制 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|---|
| base32 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| 十进制 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
| base32 | 8 | 9 | b | c | d | e | f | g |
| 十进制 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 |
| base32 | h | j | k | m | n | p | q | r |
| 十进制 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 |
| base32 | s | t | u | v | w | x | y | z |
由此可以得到ws104对应的二进制串是：11100 11000 00001 00000 00100
从左边开始数从0开始，偶数位是经度(1101 0001 0001 0)，奇数位是维度(1010 0000 0000)
这些二进制数从左到右对经纬度进行一系列分解，对于维度其范围在-90到90度，对于经度其范围在-180到180度。0表示较小的部分，1表示较大的部分。经度第一位是1，因此经度的范围在0到180度的范围内。我们依次进行此操作，对于维度的操作一样。
这样我们也可以理解为什么geohash字符串长度越长，表示的数据越准确。
下面是对维度进行分解的数据：
| 位置 | 二进制值 | 最小值 | 中间值 | 最大值 | 平均值 | 最大误差 |
|---|---|---|---|---|---|---|
| 0 | 1 | -90.000 | 0 | 90.000 | 45.000 | 45.000 |
| 1 | 0 | 0 | 45.000 | 90.000 | 22.500 | 22.500 |
| 2 | 1 | 0 | 22.500 | 45.000 | 33.750 | 11.250 |
| 3 | 0 | 22.500 | 33.750 | 45.000 | 28.125 | 5.625 |
| 4 | 0 | 22.500 | 28.125 | 33.750 | 25.3125 | 2.8125 |
| 5 | 0 | 22.500 | 25.3125 | 28.125 | 23.90625 | 1.40625 |
| 6 | 0 | 22.500 | 23.90625 | 25.3125 | 23.203125 | 0.703125 |
| 7 | 0 | 22.500 | 23.203125 | 23.90625 | 22.8515625 | 0.3515625 |
| 8 | 0 | 22.500 | 22.8515625 | 23.203125 | 22.67578125 | 0.17578125 |
| 9 | 0 | 22.500 | 22.67578125 | 22.8515625 | 22.587890625 | 0.087890625 |
| 10 | 0 | 22.500 | 22.587890625 | 22.67578125 | 22.5439453125 | 0.0439453125 |
| 11 | 0 | 22.500 | 22.5439453125 | 22.587890625 | 22.52197265625 | 0.02197265625 |
因此这个位置的维度在范围22.500到22.5439453125之间，误差为0.02197265625。
同理可以算出经度范围在113.994140625到114.0380859375之间，误差为0.02197265625。
| 位置 | 二进制值 | 最小值 | 中间值 | 最大值 | 平均值 | 最大误差 |
|---|---|---|---|---|---|---|
| 0 | 1 | -180.000 | 0 | 180.000 | 90.000 | 90.000 |
| 1 | 1 | 0 | 90.000 | 180.000 | 135.000 | 45.000 |
| 2 | 0 | 90.000 | 135.000 | 180.000 | 112.500 | 22.500 |
| 3 | 1 | 90.000 | 112.500 | 135.000 | 123.750 | 11.250 |
| 4 | 0 | 112.500 | 123.750 | 135.000 | 118.125 | 5.625 |
| 5 | 0 | 112.500 | 118.125 | 123.750 | 115.3125 | 2.8125 |
| 6 | 0 | 112.500 | 115.3125 | 118.125 | 113.90625 | 1.40625 |
| 7 | 1 | 112.500 | 113.90625 | 115.3125 | 114.609375 | 0.703125 |
| 8 | 0 | 113.90625 | 114.609375 | 115.3125 | 114.2578125 | 0.3515625 |
| 9 | 0 | 113.90625 | 114.2578125 | 114.609375 | 114.08203125 | 0.17578125 |
| 10 | 0 | 113.90625 | 114.08203125 | 114.2578125 | 113.994140625 | 0.087890625 |
| 11 | 1 | 113.90625 | 113.994140625 | 114.08203125 | 114.0380859375 | 0.0439453125 |
| 12 | 0 | 113.994140625 | 114.0380859375 | 114.08203125 | 114.01611328125 | 0.02197265625 |
下面我们给出geohash字符串长度跟精度的关系
| geohash长度 | 维度位数 | 经度位数 | 维度误差 | 经度误差 | 距离误差（km） |
|---|---|---|---|---|---|
| 1 | 2 | 3 | $\pm$23 | $\pm$23 | $\pm$2500 |
| 2 | 5 | 5 | $\pm$2.8 | $\pm$5.6 | $\pm$630 |
| 3 | 7 | 8 | $\pm$0.70 | $\pm$0.70 | $\pm$78 |
| 4 | 10 | 10 | $\pm$0.087 | $\pm$0.18 | $\pm$20 |
| 5 | 12 | 13 | $\pm$0.022 | $\pm$0.022 | $\pm$2.4 |
| 6 | 15 | 15 | $\pm$0.0027 | $\pm$0.0055 | $\pm$0.61 |
| 7 | 17 | 18 | $\pm$0.00068 | $\pm$0.00068 | $\pm$0.076 |
| 8 | 20 | 20 | $\pm$0.000085 | $\pm$0.00017 | $\pm$0.019 |
使用上的限制
边界情况
前面提到我们可以通过前缀匹配来大致的寻找附近的点。但是，这不是总能够成立的。
南极和北极的地点相近但是它们的经度差别很大，没有相同的前缀；在180度子午线(经线)两侧的地点，距离很近，但是在不同的区域内，也不会有相同的前缀。同样的，划分的区域边界，也存在类似的情况。
非线性的距离
由于geohash是基于经纬度坐标的距离进行计算，两个geohash点映射出来的距离并不是真实的距离。这是因为我们很难将球体上的坐标映射到一个均匀的二维空间。
尽管存在许多问题，但仍有可能的解决办法，这些算法已经成功的在Elasticsearch，MongoDB，HBase中实现用于近似查找。
