文檔資料: wenku.itilzj.com

• 背景

• GeoHash基本原理介紹

• GeoHash如何應(yīng)用到這個問題當中？

• 遺留問題

不知道大家是否思考過一個問題，在一些場景下（如大家在使用高德地圖打車的時候，鄰近的司機是如何知道你在他的附近并將你的打車通知推送給他去接單的？）是如何實現(xiàn)的？

一般來講，大家也許會想到，首先肯定需要知道每位乘客的經(jīng)緯度(lng,lat)，也即是二維坐標（當然這是在絕對理想的情況，不考慮上下坡度）。

而在知道了經(jīng)緯度之后，一個暴力簡單且容易想到的思路就是將經(jīng)緯度這個「二元組」都存放在一個「數(shù)組」當中，然后當我們需要拿到離我們規(guī)定范圍內(nèi)的用戶（如獲取當前位置方圓百米內(nèi)正在打車的乘客），我們就可以去遍歷維護的那個數(shù)組，以此去判斷數(shù)組中的經(jīng)緯度與自己所在經(jīng)緯度的距離，然后判斷是否在范圍內(nèi)。

顯然這種方法一定是能夠達到目的的，但是值得注意的點是，維護的數(shù)據(jù)量一般來講是海量的,因此如果每次都需要遍歷所有數(shù)據(jù)去進行計算，那這計算量以及存儲量目前是無法滿足的。那如何在此基礎(chǔ)上去優(yōu)化性能呢？？那么這個內(nèi)容就是本篇文章主要想探討的問題......

GeoHash基本原理介紹

首先我想先介紹一下GeoHash這種算法「基本原理」，再討論如何進行應(yīng)用。

對于每一個坐標都有它的經(jīng)緯度(lng,lat)，而GeoHash的原理就是將經(jīng)緯度先通過一個二分的思路拿到一個二進制數(shù)組的字符串，然后再通過base32編碼去進行壓縮存儲。

舉一個例子，比如經(jīng)緯度為（116.3111126，40.085003），對其進行二分步驟如下：

經(jīng)度步驟：

bitleftmidright1 -180 0 180 1 0 90 180 0 90 135 180 1 90 112.5 135 0 112.5 123.75 135 0 112.5 118.125 123.75 1 112.5 115.3125 118.125 0 115.3125 116.71875 118.125 1 115.3125 116.015625 116.71875 0 116.015625 116.3671875 116.71875 1 116.015625 116.19140625 116.3671875 1 116.19140625 116.279296875 116.3671875 0 116.279296875 116.323242188 116.3671875 1 116.279296875 116.301269532 116.323242188 0 116.301269532 116.31225586 116.323242188

緯度步驟：

bitleftmidright1 -90 0 90 0 0 45 90 1 0 22.5 45 1 22.5 33.75 45 1 33.75 39.375 45 0 39.375 42.1876 45 0 39.375 40.78125 42.1876 1 39.375 40.078125 40.78125 0 40.078125 40.4296875 40.78125 0 40.078125 40.25390625 40.4296875 0 40.078125 40.166015625 40.25390625 0 40.078125 40.1220703125 40.166015625 0 40.078125 40.1000976563 40.1220703125 0 40.078125 40.0891113282 40.1000976563 1 40.078125 40.0836181641 40.0891113282

「其思路就是不斷二分，如果原本值大于mid那本bit位就是1，以此往下遞歸，最終，我們遞歸二分得到緯度方向上的二進制字符串為 101110010000001，長度為 15 位」

那此時就拿到了30bit位的字符串，然后就開始進行拼接

結(jié)合經(jīng)度字符串110100101011010和緯度字符串101110010000001，我們遵循先經(jīng)度后緯度的順序，逐一交錯排列，最終得到的一維字符串為11100 11101 00100 11000 10100 01001.

然后再進行Base32編碼，主要步驟就是首先會維護一個「0-9A-Za-z」中32個字符的數(shù)組，如：['a','b','1','2','3','4','5','6','7','A'...]，然后再將這30位的字符串每五個一組（正好覆蓋0-31的索引)去索引到指定字符以此拿到30/5=6位的base32編碼去進行存儲。

「ps:注意并不一定是必要將經(jīng)緯度都二分得到15位長度，多少位都可以，只是精度越高結(jié)果也就越精確，但是算力就越大，只需在此做出權(quán)衡即可」

GeoHash如何應(yīng)用到這個問題當中？

上面講到了可以通過GeoHash將經(jīng)緯度轉(zhuǎn)換成bit位的字符串，那么怎么進行應(yīng)用呢，其實答案很明顯，其實如果經(jīng)緯度越接近，他們的前綴匹配位數(shù)也就越長，比如

通過這個思路我們就比較容易得到我們想要的范圍內(nèi)的乘客了。

遺留問題

但是其實僅僅如此是不夠的，因為一個base32其實是覆蓋了一片區(qū)域的，它并不是說僅僅代表一個精確的ip地址，那這其實就衍生出了一些問題，就比如

用geohash那結(jié)果顯然是AB更近，但是實際上A與B的距離比AE、AC、AD都遠。這其實是一個邊緣性的問題........后續(xù)我會更新如何去避免這種問題的出現(xiàn)

IT架構(gòu)師/技術(shù)大咖的交流圈子,為您提供架構(gòu)體系知識、技術(shù)文章、流行實踐案例、解決方案等，行業(yè)大咖分享交流/同行經(jīng)驗分享互動,期待你的加入!掃碼即可加入哦，隨著材料不斷增多社群會不定期漲價早加入更優(yōu)惠

免責聲明：

本公眾號部分分享的資料來自網(wǎng)絡(luò)收集和整理，所有文字和圖片版權(quán)歸屬于原作者所有，且僅代表作者個人觀點，與本公眾號無關(guān)，文章僅供讀者學習交流使用，并請自行核實相關(guān)內(nèi)容，如文章內(nèi)容涉及侵權(quán)，請聯(lián)系后臺管理員刪除。