geohash 是 Gustavo Niemeyer发明的一种对地理位置进行编码的算法， 是一种分层的空间数据结构，核心原理是将分成网格状的区域。并将一个区域编码成一定长度的字符串。 例如 将坐标 (57.64911, 10.40744)（lat, lon） 编码成11 位的 geohash 得到了4pruydqqvj。
geohash 的特点
- 纬度和经度是二维的数据，建索引的时候需要对纬度和经度同时建索引，geohash 能将二维的数据转化为一维的数据，可以用B树等索引
- geohash 生成的字符串代表的不是地图上的一个点， 而是地图上一个矩形的区域，在一定程度上能保证隐私。
字符串越长，表示的范围能够更加的精确。 8位的geohash 编码的经度能达到19米左右，9位的geohash经度能达到米级，一般情况下能满足我们大部分的需求
/* // ******* length lat bits lng bits lat error lng error km error // ******* 1 2 3 ±23 ±23 ±2500 // ******* 2 5 5 ±2.8. ±5.6. ±630 // ******* 3 7 8 ±0.70 ±0.70 ±78 // ******* 4 10 10 ±0.087 ±0.18. ±20 // ******* 5 12 13 ±0.022 ±0.022 ±2.4 // ******* 6 15 15 ±0.0027 ±0.0055 ±0.61 // ******* 7 17 18 ±0.00068 ±0.00068 ±0.076 // ******* 8 20 20 ±0.00008 ±0.00017 ±0.019 // ******* 9 22 23 ±0.00002 ±0.000021 ±0.00478 // ******* 10 25 25 ±0.000002. ±0.0000054. ±0.0006 // ******* 11 27 28 ±0.00000067 ±0.00000067. ±0.00015 */字符串前缀相同的越多，代表的距离也就越近（有特殊的情况）
编码
原理
接下来以将(57.64911, 10.40744)编码为11位的 geohash 为例，说明geohash的编码过程
首先对纬度和经度分别划分， 将（-90～90， -180～180）划分为四个字区域（-90～0，-180～0）
（-90～0， 0～180）（0～90， -180～90）（0～90， 0～180）， 四个区域分别编码为00，01， 10， 11 (57.64911, 10.40744) 所在的区域是11， 然后对geohash 所在的区域进行继续编码，最后得到一个56位的比特串（后面将会说明为什么是56位） 1101000100101011011111010111100110010110101101101110
(90, -180) (90,180)
| 01 | 11 |
|______|_____|
| | |
| 00 | 10 |
(-90, -180) (-90,180)
实现
通常的实现方式是对维度和经度分别编码，然后将经度放在偶数位，纬度放在奇数位
even := true
for i := 0; i < int(step)*2; i++ {
bits = bits << 1
if even {
if m := (max_lon + min_lon) / 2; longitude > m {
bits = bits | 0x01
min_lon = m
} else {
max_lon = m
}
} else {
if m := (max_lat + min_lat) / 2; latitude > m {
bits = bits | 0x01
min_lat = m
} else {
max_lat = m
}
}
even = !even
}
在 redis （一个高性能的 key-value 数据库）的实现中，作者巧妙的利用了 IEE754 表示浮点数的原理，算法的核心代码表示如下。 （对于这个理解的不是很透测，自己用 go 语言验证了一遍，得到的结果是正确的）
double lat_offset = //(57.64911 - -90)/(90 - -90)
(latitude - lat_range->min) / (lat_range->max - lat_range->min);
double long_offset = //(10.40744 - -180)/(180 - -180)
(longitude - long_range->min) / (long_range->max - long_range->min);
/* convert to fixed point based on the step size */
lat_offset *= (1 << step);
long_offset *= (1 << step);
hash->bits = interleave64(lat_offset, long_offset);
／／ interleave 是将lat_offset he long_offset 分别放到偶数和奇数位上去，
编码
在得到上述的二进制串之后，我们采用一种。base32 的编码方式，对字符串进行编码
Decimal 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Base 32 0 1 2 3 4 5 6 7 8 9 b c d e f g
Decimal 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
Base 32 h j k m n p q r s t u v w x y z
如上表所示，将26个字母去掉 a、 i、 l、 o 自个字母再加上 0～9 一共 32个字符，刚好能代表 5 bit 的数据 (2^5 = 32). 对于我们得到的 56 位二进制串，我们能最高编码11 位的 hashstr 4pruydqqvj
