滴滴打車如何找出方圓一千米內的乘客？揭開 GeoHash 的神祕面紗
背景
不知道大家是否思考過一個問題，在一些場景下（如大家在使用高德地圖打車的時候，鄰近的司機是如何知道你在他的附近並將你的打車通知推送給他去接單的？）是如何實現的？
一般來講，大家也許會想到，首先肯定需要知道每位乘客的經緯度 (lng,lat)，也即是二維座標（當然這是在絕對理想的情況，不考慮上下坡度）。
而在知道了經緯度之後，一個暴力簡單且容易想到的思路就是將經緯度這個 「二元組」 都存放在一個 「數組」 當中，然後當我們需要拿到離我們規定範圍內的用戶（如獲取當前位置方圓百米內正在打車的乘客），我們就可以去遍歷維護的那個數組，以此去判斷數組中的經緯度與自己所在經緯度的距離，然後判斷是否在範圍內。
顯然這種方法一定是能夠達到目的的，但是值得注意的點是，維護的數據量一般來講是海量的, 因此如果每次都需要遍歷所有數據去進行計算，那這計算量以及存儲量目前是無法滿足的。那如何在此基礎上去優化性能呢？？那麼這個內容就是本篇文章主要想探討的問題......
GeoHash 基本原理介紹
首先我想先介紹一下 GeoHash 這種算法 「基本原理」 ，再討論如何進行應用。
對於每一個座標都有它的 經緯度 (lng,lat) ，而 GeoHash 的原理就是將經緯度先通過一個二分的思路拿到一個二進制數組的字符串，然後再通過base32編碼去進行壓縮存儲。
舉一個例子，比如經緯度爲（116.3111126，40.085003），對其進行二分步驟如下：
經度步驟：
緯度步驟：
「其思路就是不斷二分，如果原本值大於 mid 那本 bit 位就是 1，以此往下遞歸，最終，我們遞歸二分得到緯度方向上的二進制字符串爲 101110010000001，長度爲 15 位」
那此時就拿到了 30bit 位的字符串，然後就開始進行拼接
結合經度字符串 110100101011010 和緯度字符串 101110010000001，我們遵循先經度後緯度的順序，逐一交錯排列，最終得到的一維字符串爲 11100 11101 00100 11000 10100 01001.
然後再進行 Base32 編碼，主要步驟就是首先會維護一個 「0-9A-Za-z」 中 32 個字符的數組，如：['a','b','1','2','3','4','5','6','7','A'...]，然後再將這 30 位的字符串每五個一組（正好覆蓋 0-31 的索引) 去索引到指定字符以此拿到 30/5=6 位的 base32 編碼去進行存儲。
「ps: 注意並不一定是必要將經緯度都二分得到 15 位長度，多少位都可以，只是精度越高結果也就越精確，但是算力就越大，只需在此做出權衡即可」
GeoHash 如何應用到這個問題當中？
上面講到了可以通過 GeoHash 將經緯度轉換成 bit 位的字符串，那麼怎麼進行應用呢，其實答案很明顯，其實如果經緯度越接近，他們的前綴匹配位數也就越長，比如
通過這個思路我們就比較容易得到我們想要的範圍內的乘客了。
遺留問題
但是其實僅僅如此是不夠的，因爲一個 base32 其實是覆蓋了一片區域的，它並不是說僅僅代表一個精確的 ip 地址，那這其實就衍生出了一些問題，就比如
用 geohash 那結果顯然是 AB 更近，但是實際上 A 與 B 的距離比 AE、AC、AD 都遠。這其實是一個邊緣性的問題........ 後續我會更新如何去避免這種問題的出現
作者：6r0wn_Jay
來源：https://juejin.cn/post/7270916734138908672
本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/cOkiVI7ZYCr4ntFTm0dNqg