geoHash的数学局限
geoHash的问题这篇博客（https://www.jianshu.com/p/7332dcb978b2）里已经写得非常完善了， 本文从数学方面来解释一下它的一些缺陷。明白GeoHash原理的话可以直接看最后一段
一、皮亚诺曲线的数学论证
以下内容节选自知乎：
皮亚诺曲线很有名气，它是一个“填满单位正方形的曲线”，不过它也让人迷惑，一个坑是它其实有过好几个定义，而即使是维基百科，上面的介绍也是错的；另一个坑是，它是按照曲线族的极限定义的，而极限与曲线族中的任意一条曲线，性质未必相同。
比如维基说：“1890年，意大利数学家[朱塞佩·皮亚诺]发明能填满一个正方形的曲线，叫做皮亚诺曲线“——嗯，到这里，是对的，让我们把这个称为定义一。
维基继续说：”其构造方法如下：取一个正方形并且把它分出九个相等的小正方形，然后从左下角的正方形开始至右上角的正方形结束，依次把小正方形的中心用线段连接起来；下一步把每个小正方形分成九个相等的正方形，然后上述方式把其中中心连接起来……将这种操作手续无限进行下去，最终得到的极限情况的曲线就被称作皮亚诺曲线。”图如下：
——嗯，这个说法也成立，让我们称这个为定义二。
两个都成立阿，那不挺好吗？问题就在于，这两个定义是不等价的——皮亚诺当年的构造方法，跟定义二里的构造方法，是不一样的。
——————分割线——————
OK，让我们从头说起。严谨一点，称“填满一个正方形的曲线，叫做皮亚诺曲线“这种最广义的说法，为定义零。皮亚诺的方法为定义一，上面整整齐齐的构造方法，为定义二。
皮亚诺当初首要目的，是为了填满正方形，他并不在乎如上图那样整整齐齐。与皮亚诺最类似的构造方法，在张筑生老师《数学分析新讲》第三册里有介绍，是索恩伯格（Isaac Jacob Schoenberg）1938年提出的：
image
image
image
image
整个过程比较罗嗦，其实想法也很简单，就是把小数拆开，一分为二——比如有小数0.12345678，按奇偶拆成0.1357和0.2468——这样单位区间上0到1的一个小数，就拆成了两个，让它们是纵横坐标，就指定了一个点，这样就填满正方形了。用数学语言说，我们要在单位区间[0,1]上定义两个函数phi和psai，使得对任意x属于[0,1]，phi(x),psai(x)也属于[0,1]。x从跑到1，(phi(x), psai(x))从(phi(0), psai(0))跑到(phi(1), psai(1))，把点连起来，就是曲线，然后想办法找到合适的phi和psai，让这个曲线能走遍正方形的所有点，就大功告成。
一分为二最简单的就是如上面例子所示按奇数和偶数位拆开——小数0.12345678，拆成小数对(0.1357, 0.2468).
这里让我们再进一步，用二进制表示，那么十进小数0.5，换成二进制就是0.1，写成0.100000....，可以拆成二进制的小数对(0.10000, 0.00000)，换成十进制就是(0.5,0)。
到这里似乎还好，问题在于，这样拆，是不连续的，即，phi和psai不连续！不连续的话，x从跑到1，(phi(x), psai(x))跑的点连不起来，就不是曲线。
验证一下：十进小数0.49999999....，换成二进制就是0.0111111.......，可以拆成二进制的小数对(0.011111...., 0.11111.....)，这就是(0.1, 1.0)，换成十进制就是(0.5,1)。这样，x从0.49999...跳到0.5，(phi(x), psai(x))从(0.5,1)跳到了(0.5,0)，步子太大，断了。
怎么办？上面Schoenberg的构造方法就是来解决这个问题的，简而言之，他引入了三进制，多了一个缓冲区间，这样就把两边连起来了。
Schoenberg function，是这个样子的：
image
上面张老师的书里的图19-10是基本函数w，Schoenberg fucntion是w的一个无穷级数，即函数序列的极限。
可以证明，Schoenberg function处处连续，处处不可导。
Schoenberg function是phi，phi(3x)是psai(x)，形成的曲线是这样的：
image
可以看到，跟上面维基的定义二里的乖宝宝相比，这样形成的皮亚诺曲线（定义一），是狂野的多了。
但不管好不好看，可以看到，任何一个单位正方形内的点，都能合并成一个单位区间的数，换句话说，这样定义的皮亚诺曲线，确实是一个满射，它填满了整个正方形。
——————分割线——————
好，现在让我们讨论定义二的曲线。这个曲线明显舒服的多，它的简化版本是希尔伯特曲线(Hilbert Curve)
image
这个定义很直观，唯一要说明的是一个坑：这样的曲线，似乎每一个条线段端点，至少有一个坐标是有理数，那这样的曲线能否经过两个坐标都是无理数的点呢？比如(1/pi, 1/pi)。
甚至有人证明了它”不可能遍历正方形“：按照皮亚诺曲线的定义，它应该无法遍历平面啊？ | 死理性派小组 | 果壳网 科技有意思。
这就回到了开头说的：曲线族的极限与曲线族中的任意一条曲线，性质未必相同。
例如有这样的曲线族fk(x) =1/k，很显然任意一条曲线都有f_k(x)>0，但这个曲线族的极限很显然是f(x)=0。
可以证明，定义二所述的皮亚诺曲线，作为曲线族的极限，是经过正方形内的每一个点的，它也是满射。
——————分割线——————
关于皮亚诺曲线的维度和面积，”等待飞翔“的回答里已经阐述，不再赘述。
——————分割线——————
geoHash问题
Geohash 一个点附近的地方(但不绝对) hash 字符串总是有公共前缀，并且公共前缀的长度越长，这两个点距离越近。
由于这个特性，Geohash 就常常被用来作为唯一标识符。用在数据库里面可用 Geohash 来表示一个点。Geohash 这个公共前缀的特性就可以用来快速的进行邻近点的搜索。越接近的点通常和目标点的 Geohash 字符串公共前缀越长（但是这不一定，也有特殊情况，下面举例会说明）
Geohash 也有几种编码形式，常见的有2种，base 32 和 base 36。
| 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 |
base 36 的版本对大小写敏感，用了36个字符，“23456789bBCdDFgGhHjJKlLMnNPqQrRtTVWX”。
| Decimal | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Base 36 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | b | B | C | d | D | F | g | G | h | H | j |
| Decimal | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 | 33 | 34 | 35 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Base 36 | J | K | I | L | M | n | N | P | q | Q | r | R | t | T | V | W | X |
Geohash 实际应用举例
接下来的举例以 base-32 为例。举个例子。
假设需要查询距离美罗城最近的餐馆，该如何查询？
第一步我们需要把地图网格化，利用 geohash。通过查表，我们选取字符串长度为6的矩形来网格化这张地图。
经过查询，美罗城的经纬度是[31.1932993, 121.43960190000007]。
先处理纬度。地球的纬度区间是[-90,90]。把这个区间分为2部分，即[-90,0)，[0,90]。31.1932993位于(0,90]区间，即右区间，标记为1。然后继续把(0,90]区间二分，分为[0,45)，[45,90]，31.1932993位于[0,45)区间，即左区间，标记为0。一直划分下去。
| 左区间 | 中值 | 右区间 | 二进制结果 |
|---|---|---|---|
| -90 | 0 | 90 | 1 |
| 0 | 45 | 90 | 0 |
| 0 | 22.5 | 45 | 1 |
| 22.5 | 33.75 | 45 | 0 |
| 22.5 | 28.125 | 33.75 | 1 |
| 28.125 | 30.9375 | 33.75 | 1 |
| 30.9375 | 32.34375 | 33.75 | 0 |
| 30.9375 | 31.640625 | 32.34375 | 0 |
| 30.9375 | 31.2890625 | 31.640625 | 0 |
| 30.9375 | 31.1132812 | 31.2890625 | 1 |
| 31.1132812 | 31.2011718 | 31.2890625 | 0 |
| 31.1132812 | 31.1572265 | 31.2011718 | 1 |
| 31.1572265 | 31.1791992 | 31.2011718 | 1 |
| 31.1791992 | 31.1901855 | 31.2011718 | 1 |
| 31.1901855 | 31.1956786 | 31.2011718 | 0 |
再处理经度，一样的处理方式。地球经度区间是[-180,180]
| 左区间 | 中值 | 右区间 | 二进制结果 |
|---|---|---|---|
| -180 | 0 | 180 | 1 |
| 0 | 90 | 180 | 1 |
| 90 | 135 | 180 | 0 |
| 90 | 112.5 | 135 | 1 |
| 112.5 | 123.75 | 135 | 0 |
| 112.5 | 118.125 | 123.75 | 1 |
| 118.125 | 120.9375 | 123.75 | 1 |
| 120.9375 | 122.34375 | 123.75 | 0 |
| 120.9375 | 121.640625 | 122.34375 | 0 |
| 120.9375 | 121.289062 | 121.640625 | 1 |
| 121.289062 | 121.464844 | 121.640625 | 0 |
| 121.289062 | 121.376953 | 121.464844 | 1 |
| 121.376953 | 121.420898 | 121.464844 | 1 |
| 121.420898 | 121.442871 | 121.464844 | 0 |
| 121.420898 | 121.431885 | 121.442871 | 1 |
纬度产生的二进制是101011000101110，经度产生的二进制是110101100101101，按照“偶数位放经度，奇数位放纬度”的规则，重新组合经度和纬度的二进制串，生成新的：111001100111100000110011110110，最后一步就是把这个最终的字符串转换成字符，对应需要查找 base-32 的表。11100 11001 11100 00011 00111 10110转换成十进制是 28 25 28 3 7 22，查表编码得到最终结果，wtw37q。
我们还可以把这个网格周围8个各自都计算出来。
image.png
从地图上可以看出，这邻近的9个格子，前缀都完全一致。都是wtw37。
如果我们把字符串再增加一位，会有什么样的结果呢？Geohash 增加到7位。
image.png
当Geohash 增加到7位的时候，网格更小了，美罗城的 Geohash 变成了 wtw37qt。
看到这里，读者应该已经清楚了 Geohash 的算法原理了。咱们把6位和7位都组合到一张图上面来看。
可以看到中间大格子的 Geohash 的值是 wtw37q，那么它里面的所有小格子前缀都是 wtw37q。可以想象，当 Geohash 字符串长度为5的时候，Geohash 肯定就为 wtw37 了。
接下来解释之前说的 Geohash 和 Z 阶曲线的关系。回顾最后一步合并经纬度字符串的规则，“偶数位放经度，奇数位放纬度”。读者一定有点好奇，这个规则哪里来的？凭空瞎想的？其实并不是，这个规则就是 Z 阶曲线。看下图：
image.png
几个问题
GeoHash的缺点
我们发现在前面的皮亚诺曲线推倒的过程中， 把小数拆开， 一分为二的过程其实和GeoHash中将经纬度合二为一是个相反过程。 以base-32 为例， 我们假设有一个地理位置二进制为(11111, 111111)和另一个（100000，000000）显然他们离的很远， 我们把它变为GeoHash值， 则一个为11111111111， 一个为100000000000，转换为十进制后为001zz 和 00200： 在数值上这两个点相差很小， 但是实际距离相差很大。 这里对应的数学现象就是前边提到的， 单纯的奇偶交叉排列二进制下是不连续的， 我们可以把精度设的越来越高， 但是终究它的极限是跳跃的。 再看上图我们发现凡是涉及到进位操作的时候都有可能会有跳跃。
所以我们可以看出GeoHash在使用过程中不能简单通过GeoHash值是否近似来判断是否离的很近， 而应一次获取圆心附近的九个方框（通过前缀是否相同判定， 由于进位的情况会改变前缀所以会把这种跳跃点忽略）， 拿到所有点位后， 通过求欧氏距离来算定远近。
如何找到附近的区块
我们很容易联想到如果一个点在格林尼治天文台附近， 那么单纯通过前缀他会忽略掉离自己很近的目标。 事实上所有处于二分位置的线附近都会有一样的问题， 即明明离的很近， 但是前缀完全不同。 事实上查找附近区块是有规律的
image.png
通过这个图我们可以看出来， base32会把空间分为32块， 每一个小空间的空间排序也是一样的， 这样通过简单的排序规则， 我们就可以找到附近的8个区块的前缀， 然后一次获取9个区块， 再进行欧氏距离计算。
