Geohash 是 Gustavo Niemeyer 在 2008 年發明的一個地理編碼系統（geocode system），它将經度和緯度這個二維的地理坐标編碼成一個由數字和字母組成的字元串。雖然 geohash 是從經緯度計算出來的，但是 geohash 并不能像經緯度那樣能夠表示出某個點在地圖上的确切位置。實際上，Geohash 表示的是一個區域，這個區域内所有的點都有着相同的 geohash 值。這意味着，geohash 可以幫助使用者隐藏确切的位置資訊，進而更好地保護使用者的隐私。雖然我們可以通過 geohash 得知使用者所在的區域，但是我們卻無法知道使用者到底在這個區域中的哪個點。
很多基于位置的個性化服務都是基于 geohash 實作的。比如查找附近的人，尋找附近的餐廳等等。以查找附近的人為例，如果兩個人所處位置的 geohash 相同，那麼我們可以認為這兩個人在空間上是相近的。至于具體有多近，這取決于 geohash 所表示的位置精度。通過改變 geohash 的長度，我們可以表示任意精度的位置：geohash 越短，其表示的區域越大，位置精度越低；相反，geohash 越長，其表示的區域越小，位置精度越高。
以天府廣場（latitude: 30.6599157, longitude: 104.0638546）為例，下圖展示了通過不斷增加 geohash 長度提高展示位置精度的過程：
- 當 geohash 長度為 1 時，選擇
w
- 當 geohash 長度為 2 時，選擇
wm
- 當 geohash 長度為 3 時，選擇
wm6
- 當 geohash 長度為 4 時，選擇
wm6n
- 當 geohash 長度為 5 時，選擇
wm6nj
- 當 geohash 長度為 6 時，選擇
wm6nj2
需要注意的是，同一個地點在不同地圖下的經緯度可能是不一樣的。本文采用的是 OpenStreeMap。
經度與緯度
經緯度是由地球表面經線和緯線相交組成的一個坐标系統。每根經線和緯線都有不同的度數，叫經度和緯度。
地球是一個球體，經線連接配接南北兩極，是半圓弧狀。經過英國首都倫敦格林尼治天文台原址的那一條經線被定為 0° 經線，又叫本初子午線。本初子午線往東為東半球，往西為西半球。東西兩個半球的經度範圍均在 0° 至 180° 之間，合計360度。一般将西半球的經度範圍記為
[-180°, 0°)
，而将東半球的為
(0°, 180°]
。
緯線與經線垂直的圓圈，任意兩根緯線互相平行。赤道（實際上是地球表面的點随着地球自轉産生的軌迹中最長的圓周線）是最大的緯線圈，緯度為 0°。赤道将地球分為南北兩個半球，南北兩個半球的緯度範圍都是 90°，合計 180°。從赤道出發，向兩極靠近，緯度越來越大，緯線圈越來越小。一般将南半球的緯度範圍記為
[-90°, 0°)
，而将北半球的緯度記為
(0°, 90°]
。
南極點的緯度記為 90°S（或 -90°），北極點的緯度記為 90°N（或 +90°）。
算法原理
Geohash 是一種将二維的經緯度編碼成一個字元串的地理編碼方法，核心思想是區間二分：将地球編碼看成一個二維平面，然後将這個平面遞歸均分為更小的子塊。
當我們對一個地理坐标進行 geohash 編碼時，先分别計算出經度和緯度各自的二進制編碼，然後按照“從第 0 位開始，偶數位放經度，奇數位放緯度”的規則将經度和緯度的編碼交叉組合，得到一個完整的二進制編碼。接着，将二進制編碼按照五個一組進行劃分，算出每一組二進制編碼的十進制值并将其作為索引查找 base32 編碼表中對應的值。最後将這些值拼接在一起就得到了 geohash 值。
不難看出，geohash 越長，對地圖的劃分次數就越多。劃分的次數多了，矩形區域就小了，位置精度也就上去了。那麼是不是 geohash 越長越好呢？當然不是，我們應該根據實際的應用場景來選擇合适的長度。如果使用記憶體存儲 geohash，geohash 越長，其所占的空間就越大。為了保護使用者的位置隐私，也需要将位置精度控制在合理的範圍内。
接下來還是以成都市天府廣場的位置為例，來看看 geohash 具體是如何計算的。
計算出經度和緯度各自對應的二進制編碼
計算經度或緯度的二進制編碼的方法如下：
- 确定初始區間，經度為
[-180°, +180°]
[-90°, +90°]
- 将初始區間對半拆分得到左半區間和右半區間，根據目标位置的經度或緯度是落在左區間還是右區間，決定目前位的二進制編碼。左區間取 0，右區間取 1。
- 對上一步中目标位置所在的子區間進行對半劃分，按照同樣的方式計算出下一位的二進制編碼。
- 重複劃分上面的步驟，直到達到期望的編碼長度。
首先對緯度進行二進制編碼：
- 将
[-90°, 90°]
[-90°, 0°]
[0°, 90°]
- 将
[0°, 90°]
[0°, 45°]
[45°, 90°]
- ……
按照這個流程，計算天府廣場緯度 30.6599157 的 15 位二進制編碼的過程：
疊代 左端點 區間中點 右端點 0/1
1 -90.000000 0.000000 90.000000 1
2 0.000000 45.000000 90.000000 0
3 0.000000 22.500000 45.000000 1
4 22.500000 33.750000 45.000000 0
5 22.500000 28.125000 33.750000 1
6 28.125000 30.937500 33.750000 0
7 28.125000 29.531250 30.937500 1
8 29.531250 30.234375 30.937500 1
9 30.234375 30.585938 30.937500 1
10 30.585938 30.761719 30.937500 0
11 30.585938 30.673828 30.761719 0
12 30.585938 30.629883 30.673828 1
13 30.629883 30.651855 30.673828 1
14 30.651855 30.662842 30.673828 0
15 30.651855 30.657349 30.662842 1
通過以上計算，緯度 30.6599157 的二進制編碼為：
10101 01110 01101
。
同理，我們也可以計算出經度 104.0638546 的 15 位二進制編碼：
疊代 左端點 區間中點 右端點 0/1
1 -180.000000 0.000000 180.000000 1
2 0.000000 90.000000 180.000000 1
3 90.000000 135.000000 180.000000 0
4 90.000000 112.500000 135.000000 0
5 90.000000 101.250000 112.500000 1
6 101.250000 106.875000 112.500000 0
7 101.250000 104.062500 106.875000 1
8 104.062500 105.468750 106.875000 0
9 104.062500 104.765625 105.468750 0
10 104.062500 104.414062 104.765625 0
11 104.062500 104.238281 104.414062 0
12 104.062500 104.150391 104.238281 0
13 104.062500 104.106445 104.150391 0
14 104.062500 104.084473 104.106445 0
15 104.062500 104.073486 104.084473 0
經度 104.0638546 的二進制編碼為
11001 01000 00000
。
交叉合并經度和緯度的二進制編碼
從第 0 位開始，偶數位放經度，奇數位放緯度，得到完整的二進制編碼：
将二進制編碼分組并計算出對應的 Base32 編碼
上面的二進制編碼看起來很長，不友善記憶。為了壓縮編碼長度，geohash 采用了自己的 Base32 編碼，将二進制編碼轉換成友善識别的文本。Geohash 所用的編碼表由數字和字母組成，不過去掉了 a，i，l 和 o 四個字母：
有了編碼表後，我們将之前組合得到的二進制編碼，五個一組，計算出每一組的十進制值，然後查表得到最終的編碼
wm6n2j
：
Geohash 解碼
Geohash 的解碼實際上編碼的逆過程，先通過 Base32 編碼表找出每個字元的十進制值，然後将十進制轉為二進制，最後通過二進制計算出對應的區域範圍。
前面我們計算出天府廣場的 geohash 是
wm6n2j
，現在将其還原為經緯度：
最後一步将二進制還原為十進制，從左往右周遊二進制編碼，将目前區間對半劃分，若為 0，取左區間為下一步劃分用的區間，為 1 則将右區間作為下一步劃分用的區間。經度的初始區間為
[-180°, +180°]
，緯度的初始區間為
[-90°, +90°]
。
将二進制編碼的緯度
10101 01110 01101
還原，得到它表示的緯度範圍是
(30.657349, 30.662842)
：
0/1 最小值 最大值
1 0.000000 90.000000
0 0.000000 45.000000
1 22.500000 45.000000
0 22.500000 33.750000
1 28.125000 33.750000
0 28.125000 30.937500
1 29.531250 30.937500
1 30.234375 30.937500
1 30.585938 30.937500
0 30.585938 30.761719
0 30.585938 30.673828
1 30.629883 30.673828
1 30.651855 30.673828
0 30.651855 30.662842
1 30.657349 30.662842
将二進制編碼的經度
11001 01000 00000
還原，得到它表示的經度範圍是
(104.062500, 104.073486)
：
0/1 最小值 最大值
1 0.000000 180.000000
1 90.000000 180.000000
0 90.000000 135.000000
0 90.000000 112.500000
1 101.250000 112.500000
0 101.250000 106.875000
1 104.062500 106.875000
0 104.062500 105.468750
0 104.062500 104.765625
0 104.062500 104.414062
0 104.062500 104.238281
0 104.062500 104.150391
0 104.062500 104.106445
0 104.062500 104.084473
0 104.062500 104.073486
最終，我們得出
wm6n2j
表示的是經度在
(104.062500, 104.073486)
之間，緯度在
(30.657349, 30.662842)
之間的一個矩形區域。
對比天府廣場（latitude: 30.6599157, longitude: 104.0638546），它恰好在計算出來的範圍之内。這個例子很好地說明了 geohash 是如何表示一個區域範圍的。
Geohash 的長度與位置精度
Geohash 的長度對位置的精度有着非常直接的影響。從下面這個表格可以看出，當編碼長度為 1 時，精度高達 2500km，而當編碼長度為 8 時，精度降到了 19m。
| Geohash 長度 | 緯度位數 | 經度位數 | 緯度誤差 | 精度誤差 | 距離誤差 |
|---|---|---|---|---|---|
| 1 | 2 | 3 | ±23 | ±23 | ±2,500 km |
| 2 | 5 | 5 | ±2.8 | ±5.6 | ±630 km |
| 3 | 7 | 8 | ±0.70 | ±0.70 | ±78 km |
| 4 | 10 | 10 | ±0.087 | ±0.18 | ±20 km |
| 5 | 12 | 13 | ±0.022 | ±0.022 | ±2.4 km |
| 6 | 15 | 15 | ±0.0027 | ±0.0055 | ±0.61 km |
| 7 | 17 | 18 | ±0.00068 | ±0.00068 | ±0.076 km |
| 8 | 20 | 20 | ±0.000085 | ±0.00017 | ±0.019 km |
Geohash 的局限性
Geohash 非常好用，但它還是存在兩個問題：邊界問題和非線性問題。
邊界問題
Geohash 将鄰近搜尋（proximity search）轉換為了字元串字首比對，和基于經緯度的算法相比，極大地提高了計算效率。由于 geohash 是将地圖劃分為矩形網格，并單獨對每個矩形進行編碼，這就會帶來以下問題。比如下圖中有 A、B、C 三個點，要查找離 B 最近的點。可以發現，距離較遠的 A 和 B 有着相同的 geohash 編碼，而較近的 C 的 geohash 編碼卻有所不同。
這種問題一般出現在邊界上。解決思路很簡單，除了使用目标點的 geohash 進行比對外，還需要檢查相鄰 8 個格子的 geohash 編碼，這樣才能選出最符合要求的答案。
非線性問題
Geohash 是基于經緯度的，它能反映出兩個點在經緯度上面的距離，但是卻不能反映出實際距離。在不同的緯度下，機關經度所表示的距離是不一樣的。在赤道，機關經度對應的距離為 111.320km，而在 30°N 和 30°S，機關經度對應的距離為 110.852km。
這種非線性問題并不是 geohash 和經緯度系統的問題，而是在于将球體表面的坐标映射到二維平面的坐标的不均勻性。在不同的緯度下，指定長度的 geohash 所表示的矩形區域大小也是不一樣的。矩形用南北方向的高度（height）和東西方向的寬度（width）來衡量。例如在赤道：
| Geohash 長度 | 寬（Width） | 高（Height） |
|---|---|---|
| 1 | 4604.5 km | 5003.8 km |
| 2 | 1249.4 km | 625.5 km |
| 3 | 156.4 km | 156.4 km |
| 4 | 39.1 km | 19.5 km |
| 5 | 4.9 km | 4.9 km |
| 6 | 1.2 km | 610.8 m |
| 7 | 152.7 m | 152.7 m |
| 8 | 38.2 m | 19.1 m |
| 9 | 4.8 m | 4.8 m |
| 10 | 1.2 m | 596.5 mm |
| 11 | 149.1 mm | 149.1 mm |
| 12 | 37.3 mm | 18.6 mm |
Blake Haugen 在他的部落格 Geohash Size Variation by Latitude 中展示了不同緯度下不同長度的 geohash 所表示的矩形區域的大小。當 geohash 長度相同時，矩形的高度在不同緯度下是相同的，而矩形的寬度在不同緯度下并不相同。這一點從經緯度的劃分上很好了解，假設地球是一個完美的球體，經線圈的周長是相同的，而緯線圈的周長在赤道最大，越靠近兩極越小并不斷趨近于零。
參考資料
- Wikipedia: Geohash
- Chris Hewett’s GeoHash Explorer
- Geohash Size Variation by Latitude
- 基于快速GeoHash，如何實作海量商品與商圈的高效比對
- Notes on Geohashing
- The A-Z of Geohashing: What You Need to Know
- 百度地圖 geohash 可視化工具