本文作者：smallyang，騰訊 IEG 開(kāi)發(fā)工程師

什么是geohash？它的原理是什么？它幫助我們解決了哪些痛點(diǎn)，本文為你娓娓道來(lái)。

本文包含以下內(nèi)容，閱讀完需要約10分鐘：

• 我們?nèi)粘Ｉ钪杏龅侥男┒ㄎ坏膱?chǎng)景

• 簡(jiǎn)單復(fù)習(xí)一下經(jīng)緯度

• geohash原理解析

• geohash存在的邊界問(wèn)題

• 如何解決邊界問(wèn)題

• 計(jì)算兩點(diǎn)距離的計(jì)算

• geohash 在redis中的實(shí)現(xiàn)

我們?nèi)粘Ｉ钪杏龅侥男┒ㄎ坏膱?chǎng)景

我們上下班經(jīng)常會(huì)用APP打車(chē)和共享單車(chē)，下面2張圖，應(yīng)該都很熟悉，打開(kāi)定位，查找我附近的車(chē)，那么，這個(gè)是怎么實(shí)現(xiàn)的呢？

我腦海中第一個(gè)實(shí)現(xiàn)方式是：實(shí)時(shí)上報(bào)經(jīng)緯度。在數(shù)據(jù)庫(kù)里，把經(jīng)緯度都標(biāo)記為索引，通過(guò)查找對(duì)比經(jīng)緯度的值，來(lái)找到附近1km的車(chē)子，但是這種做法第一是索引比較多，數(shù)值比較大，二是需要循環(huán)遍歷經(jīng)緯度，查詢會(huì)很慢，效率很低。

那么，這些APP是怎么做到，既能精準(zhǔn)定位，又能快速查找呢？答案就是 geohash

geohash通過(guò)算法將1個(gè)定位的經(jīng)度和緯度2個(gè)數(shù)值，轉(zhuǎn)換成1個(gè)hash字符串。如果2個(gè)地方距離越近，那么他們的hash值的前綴越相同。然后通過(guò)數(shù)據(jù)庫(kù)中l(wèi)ike操作符 “ like wtw366%” 快速查找到附近的車(chē)。

比如上海騰訊大廈的經(jīng)緯度是：（31.1688749, 121.3975184），那么轉(zhuǎn)換成geohash就是 wtw366ngz5qt，我們想找附近的車(chē)子，可以用：

select?*?from?cart?where?geohash?like?'wtw366%'?;select?*?from?cart?where?LEFT(geohash,?6)?=?'wtw366';

簡(jiǎn)單復(fù)習(xí)一下經(jīng)緯度

在大致了解什么是geohash之后，我們先來(lái)復(fù)習(xí)一下什么是經(jīng)緯度（高中學(xué)的，可能已經(jīng)忘記光了（逃）），這對(duì)于理解geohash有很大的幫助。

我們將地球鋪平開(kāi)來(lái)，會(huì)得到下面這個(gè)平面圖。

地球鋪平面圖

以赤道和本初子午線為界，將地球分為經(jīng)度和緯度。赤道是在0度，本初子午線也在0度。以赤道作為經(jīng)度X橫坐標(biāo)，以本初子午線作為緯度 Y 豎坐標(biāo)。

經(jīng)緯度圖
經(jīng)度（longitude）`和`緯度（latitude）`簡(jiǎn)稱?`lng`?和?`lat

其中，從本初子午線向東劃分180度稱為東經(jīng)，用”E”表示：（0, 180]；向西劃分180度為西經(jīng),用“W”表示：[-180, 0）

以赤道為0度,向南北各分出90度，南北極的讀數(shù)均是90度，北緯用“N”表示 :（0, 90] ，南緯用“S”表示: [-90, 0）

緯線和緯線是角度數(shù)值，并不是米。

所以，我們常用十字坐標(biāo)法來(lái)表示經(jīng)緯度坐標(biāo)圖：

十字坐標(biāo)法

我們一般讀“經(jīng)緯度”，其實(shí)，表示一個(gè)定位的書(shū)面經(jīng)緯度是 “（緯度，經(jīng)度）”。

比如上海騰訊大廈的定位就是：(31.1688749, 121.3975184）表示的是：緯度=31.1688749，經(jīng)度=121.3975184

上海騰訊大廈經(jīng)緯度圖

geohash原理解析

在了解什么是經(jīng)緯度之后，現(xiàn)在我們就可以開(kāi)始來(lái)說(shuō)下geohash的原理了，geohash通過(guò)以下步驟，實(shí)現(xiàn)了將一個(gè)經(jīng)緯度數(shù)子串，轉(zhuǎn)換成1個(gè)hash字符串。

指定一個(gè)位置的經(jīng)緯度坐標(biāo)值。

根據(jù)十字坐標(biāo)圖和二分法，將緯度和經(jīng)度劃分成1和0的二進(jìn)制數(shù)字串。

按照“偶數(shù)位放經(jīng)度，奇數(shù)位放緯度”算法，合并經(jīng)度和緯度這2個(gè)二進(jìn)制數(shù)字串。

合并后的二進(jìn)制數(shù)字串，按照從前往后，每隔5位，換算成十進(jìn)制數(shù)字，最后不足5位的用0補(bǔ)齊。

十進(jìn)制數(shù)字，對(duì)應(yīng)base32字符串算法的所在位置，一一匹配，得到了最后的字符串結(jié)果。

按照進(jìn)度劃分截取，得到最終的geohash值。

我們按照這個(gè)順序，結(jié)合實(shí)際的例子，依次計(jì)算操作一下。

1. 找出一個(gè)位置的經(jīng)緯度

我們可以用各種地圖和定位工具，比如依靠Google地圖，通過(guò)定位或者搜索一個(gè)地點(diǎn)，就容易找出經(jīng)緯度。

騰訊大廈的經(jīng)緯度

這樣，我們就找出了上海騰訊大廈的經(jīng)緯度是 （31.1688749, 121.3975184）

2. 將經(jīng)緯度按照二分算法變成01二進(jìn)制

上海騰訊大廈的經(jīng)緯度是 （31.1688749, 121.3975184）

將緯度范圍(-90, 90)平分成兩個(gè)區(qū)間(-90, 0)、(0, 90)， 如果目標(biāo)緯度位于前一個(gè)區(qū)間，則編碼為0，否則編碼為1。

由于31.1688749屬于(0, 90)，所以取編碼為1。

然后再將(0, 90)分成 (0, 45), (45, 90)兩個(gè)區(qū)間，而31.1688749位于(0, 45)，所以編碼為0。

然后再將(0, 45)分成 (0, 22.5), (22.5, 45)兩個(gè)區(qū)間，而31.1688749位于(22.5, 45)，所以編碼為1。

依次類推可得上海騰訊大廈緯度編碼為：

101011000101010000111101101101

經(jīng)度也用同樣的算法，對(duì)(-180, 180)依次細(xì)分，(-180，0)、(0,180) ，得出編碼為：

110101100101001110111110011010

我們用php代碼來(lái)具體實(shí)現(xiàn)一下這個(gè)算法：

//緯度 $minLat?=?-90; $maxLat?=?90;//經(jīng)度 $minLng?=?-180; $maxLng?=?180;//2分查找計(jì)算，將經(jīng)緯度轉(zhuǎn)換成二進(jìn)制數(shù)字串 $latLength?=?$lngLength?=?0; $latList?=?$lngList?=?[];//$precision?精度最大是12,代表12個(gè)字符，1個(gè)字符由5個(gè)二進(jìn)制組成，也就是?12?*?5?=?60 //精度和緯度對(duì)半開(kāi)，得除以2，也就是最大長(zhǎng)度為30個(gè)二進(jìn)制。$originPrecision?=?30;//緯度 while?($latLength?<?$originPrecision)?{//大于中間值，則為右區(qū)間，值為1?，反之，則為0if?($lat?>=?$middle?=?($minLat?+?$maxLat)?/?2)?{$latList[]?=?1;$minLat?=?$middle;}?else?{$latList[]?=?0;$maxLat?=?$middle;}$latLength++; }//經(jīng)度 while?($lngLength?<?$originPrecision)?{//大于中間值，則為右區(qū)間，值為1?，反之，則為0if?($lng?>=?$middle?=?($minLng?+?$maxLng)?/?2)?{$lngList[]?=?1;$minLng?=?$middle;}?else?{$lngList[]?=?0;$maxLng?=?$middle;}$lngLength++; }var_dump(implode("",?$latList),?implode("",?$lngList));die;

3. 偶數(shù)位放經(jīng)度，奇數(shù)位放緯度

通過(guò)二分算法，我們得到了騰訊大廈的緯度和經(jīng)度的二級(jí)制串為：

string(30)?"101011000101010000111101101101" string(30)?"110101100101001110111110011010"

現(xiàn)在需要按照”偶數(shù)位放經(jīng)度，奇數(shù)位放緯度”，將這2個(gè)數(shù)字串，合二為一。那么這個(gè)到底怎么理解呢？我剛開(kāi)始不理解到底怎么操作，后來(lái)經(jīng)過(guò)一系列的思考，可以如下操作：

偶數(shù)位放經(jīng)度，奇數(shù)位放緯度

由于無(wú)法用文字表述，我截了個(gè)操作圖，如圖上的箭頭操作順序所示，就是把緯度往右移動(dòng)一個(gè)位置，然后依次串起來(lái)。

用php代碼實(shí)現(xiàn)，或許看起來(lái)更好理解：

//偶數(shù)位放經(jīng)度，奇數(shù)位放緯度 $stringList?=?'';for?($i?=?0;?$i?<?30;?$i++)?{$stringList?.=?$lngList[$i];$stringList?.=?$latList[$i]; } var_dump($stringList);die;

這樣，合并之后，我們得了一個(gè)60個(gè)字符長(zhǎng)度的的二進(jìn)制數(shù)字串：

string(60)?"111001100111100000110011000110101000111111111001011011011001"

4. 二進(jìn)制轉(zhuǎn)換成十進(jìn)制

我們把這個(gè)60位的二進(jìn)制，按照從左往右，每5位劃分成1個(gè)組，最后一組如果不足5位就用0補(bǔ)齊到5位。劃分后如下所示：

11100?11001?11100?00011?00110?00110?10100?01111?11111?00101?10110?11001

然后，把分好的二進(jìn)制，轉(zhuǎn)換成十進(jìn)制：

?28?25?28?3?6?6?20?15?31?5?22?25

用php實(shí)現(xiàn)也很簡(jiǎn)單：

$stringList?=?"111001100111100000110011000110101000111111111001011011011001";//二進(jìn)制轉(zhuǎn)成十進(jìn)制,5個(gè)一組 $stringListLen?=?strlen($stringList)?/?5; $code?=?[]; for?($i?=?0;?$i?<?$stringListLen;?$i++)?{$code[]?=?bindec(substr($stringList,?5?*?$i,?5)); }var_dump(implode("?",$code));die;

5. 匹配對(duì)應(yīng)base32表算法的所在位置

base32表是用0-9、b-z（去掉a, i, l, o）這32個(gè)字母進(jìn)行組合的編碼集合，base-32如下所示：

0123456789bcdefghjkmnpqrstuvwxyz

為了更好理解和一一對(duì)應(yīng)，我們把base32各個(gè)字符的位置信息和它的字符串用表對(duì)應(yīng)起來(lái)：

所以， 28 25 28 3 6 6 20 15 31 5 22 25 對(duì)應(yīng)上面的表的位置就得到了，是：

wtw366ngz5qt

同樣，我們也用php算法來(lái)實(shí)現(xiàn)一下：

//base32?映射 $base32Code?=?"0123456789bcdefghjkmnpqrstuvwxyz"; $encodeString?=?''; foreach?($code?as?$value)?{$encodeString?.=?$base32Code{$value}; }var_dump($encodeString);die;

這樣，最后我們得到了，上海騰訊大廈的經(jīng)緯度（31.1688749, 121.3975184） 對(duì)應(yīng)的 geohash 為 wtw366ngz5qt

geohash 的精度問(wèn)題

geohash其實(shí)表示的是一個(gè)矩形的塊狀區(qū)間，它總共分成最大12個(gè)字符串，也就是表示從 1-12 級(jí)。字符數(shù)越大，塊區(qū)間就越小，那么定位就越精準(zhǔn)。

我們剛才計(jì)算上海騰訊大廈的geohash采用的是12級(jí)，基本計(jì)算出來(lái)的位置就是毫秒級(jí)別了，可以說(shuō)是非常的精準(zhǔn)了。

上面是geohash字符串長(zhǎng)度對(duì)應(yīng)的區(qū)間精度，我們可以看到，當(dāng)geohash為12位時(shí)，表示是37毫米范圍的區(qū)間，已經(jīng)是非常的精準(zhǔn)了。當(dāng)geohash為6位時(shí)，表示為1.2k米范圍內(nèi)的矩形位置。

所以，當(dāng)2個(gè)定位的geohash 前7位是一樣的時(shí)，表示他們?cè)诟浇?.2km的范圍內(nèi)。

那我們還是用騰訊大廈的geohash值，分別截取經(jīng)度為前7，6，5位看看，在地圖上是怎么樣的：

精度為7，153m范圍內(nèi)
精度為6，1.22km范圍內(nèi)
精度為5， 4.89km范圍內(nèi)

所以，根據(jù)上面的圖，隨著字符越來(lái)越少，精度越來(lái)越小，這個(gè)矩形也越來(lái)越大，這一整塊區(qū)間都共用一個(gè)geohash來(lái)表示。在實(shí)際應(yīng)用中，我們就可以動(dòng)態(tài)的調(diào)整精度，實(shí)現(xiàn)更大或者更小范圍內(nèi)的搜索，既能精準(zhǔn)定位，又可以隱藏住一個(gè)地點(diǎn)的具區(qū)位信息。

geohash存在的邊界問(wèn)題

由于geohash表示的是一個(gè)區(qū)塊信息，在同一個(gè)區(qū)塊里的2個(gè)位置，它會(huì)認(rèn)為是最近的，然而，其實(shí)更近的位置可能剛好在另一個(gè)區(qū)間，這樣就造成了不匹配的問(wèn)題。這就存在一個(gè)邊界問(wèn)題。

我們用實(shí)際例子來(lái)看。我們想找騰大附近1.5km范圍內(nèi)的便利店，我們選取geohash精度為6。園區(qū)有2家 A 和 B。B距離我們更近一點(diǎn)，但是，由于A 和騰大在一個(gè)hash區(qū)塊內(nèi)，所以，就得出了A是最佳的選擇。這就是邊界的問(wèn)題。

邊界問(wèn)題

如何解決邊界問(wèn)題

那么如何解決這個(gè)邊界問(wèn)題，給出最近最優(yōu)的算法方案呢？答案就是：把定位附近的8個(gè)方向的geohash都算出來(lái)。最后分別計(jì)算這些點(diǎn)和自己的距離（由于范圍很小，點(diǎn)的數(shù)量就也很少，計(jì)算量就很少）過(guò)濾掉不滿足條件的點(diǎn)就ok了。

8個(gè)geohash都算出來(lái)

計(jì)算兩點(diǎn)距離的計(jì)算

通過(guò)余弦定理以及弧度計(jì)算方法，最終推導(dǎo)出來(lái)的算式A為：

$s?=?acos(cos($radLat1)?*?cos($radLat2)?*?cos($radLng1?-?$radLng2)?+?sin($radLat1)?*?sin($radLat2))?*?$R;

目前大多使用的是Google公開(kāi)的距離計(jì)算公司，推導(dǎo)算式B為：

$s?=?2*asin(sqrt(pow(sin(($radLat1-$radLat2)/2),2)+cos($radLat1)*cos($radLat2)*pow(sin(($radLng1-$radLng2)/2),2)))*$R;

其中 :?

• $radLat1、$radLng1，$radLat2，$``radLng2 為弧度

• $R為地球半徑

用PHP實(shí)現(xiàn)一下：

function?getDistance($lat1,?$lng1,?$lat2,?$lng2)?{//地球半徑$R?=?6378137;//將角度轉(zhuǎn)為狐度$radLat1?=?deg2rad($lat1);$radLat2?=?deg2rad($lat2);$radLng1?=?deg2rad($lng1);$radLng2?=?deg2rad($lng2);//結(jié)果$s?=?acos(cos($radLat1)*cos($radLat2)*cos($radLng1-$radLng2)+sin($radLat1)*sin($radLat2))*$R;//精度$s?=?round($s*?10000)/10000;return??round($s); }/**求兩個(gè)已知經(jīng)緯度之間的距離,單位為米*?@param?lat1,lat2?緯度*?@param?lng1,lng2?經(jīng)度*?@return?float?距離，單位米 */ function?getDistanceByGoogle($lat1,?$lng1,?$lat2,?$lng2) {//地球半徑$R?=?6378137;//deg2rad()函數(shù)將角度轉(zhuǎn)換為弧度$radLat1?=?deg2rad($lat1);$radLat2?=?deg2rad($lat2);$radLng1?=?deg2rad($lng1);$radLng2?=?deg2rad($lng2);$a?=?$radLat1?-?$radLat2;$b?=?$radLng1?-?$radLng2;$s?=?2?*?asin(sqrt(pow(sin($a?/?2),?2)?+?cos($radLat1)?*?cos($radLat2)?*?pow(sin($b?/?2),?2)))?*?$R;return?$s; }

geohash 在redis中的實(shí)現(xiàn)

redis在 3.2.0中加入了geo相關(guān)的命令，對(duì)geohash的支持。

redis中經(jīng)緯度使用52位的整數(shù)進(jìn)行編碼，放進(jìn)zset中，zset的value元素是key，score是GeoHash的52位整數(shù)值。在使用redis進(jìn)行Geo查詢時(shí)，其內(nèi)部對(duì)應(yīng)的操作其實(shí)只是zset(skiplist)的操作。通過(guò)zset的score進(jìn)行排序就可以得到坐標(biāo)附近的其它元素，通過(guò)將score還原成坐標(biāo)值就可以得到元素的原始坐標(biāo)

redis中處理這些地理位置坐標(biāo)點(diǎn)的思想是: 二維平面坐標(biāo)點(diǎn) —> 一維整數(shù)編碼值 —> zset(score為編碼值) —> zrangebyrank(獲取score相近的元素)、zrangebyscore —> 通過(guò)score(整數(shù)編碼值)反解坐標(biāo)點(diǎn) —> 附近點(diǎn)的地理位置坐標(biāo)。

redis 中有6個(gè)命令，對(duì)地理位置的算法支持，可以去redis官網(wǎng)具體查看其用法 : https://redis.io/commands#geo

GEOADD

其他資料

• geohash在線換算: http://geohash.co/

• 換算+地圖定位: https://www.movable-type.co.uk/scripts/geohash.html

更多內(nèi)容可以戳我們的「騰訊技術(shù)」知乎專欄：

?

總結(jié)

以上是生活随笔為你收集整理的是什么能让 APP 快速精准定位到我们的位置？的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。