Geohash的原理、算法和具體應(yīng)用探究
Geohash 是一種地址編碼，它能把二維的經(jīng)緯度編碼成一維的字符串。比如，北海公園的編碼是wx4g0ec1。
Geohash 的原理、算法
下面以(39.92324, 116.3906)為例，介紹一下geohash的編碼算法。
首先將緯度范圍(-90, 90)平分成兩個區(qū)間(-90, 0)、(0, 90)， 如果目標緯度位于前一個區(qū)間，則編碼為0，否則編碼為1。由于39.92324屬于(0, 90)，所以取編碼為1。然后再將(0, 90)分成 (0, 45), (45, 90)兩個區(qū)間，而39.92324位于(0, 45)，所以編碼為0。以此類推，直到精度符合要求為止，得到緯度編碼為1011 1000 1100 0111 1001。
| 緯度范圍 | 劃分區(qū)間0 | 劃分區(qū)間1 | 39.92324所屬區(qū)間 |
| (-90, 90) | (-90, 0.0) | (0.0, 90) | 1 |
| (0.0, 90) | (0.0, 45.0) | (45.0, 90) | 0 |
| (0.0, 45.0) | (0.0, 22.5) | (22.5, 45.0) | 1 |
| (22.5, 45.0) | (22.5, 33.75) | (33.75, 45.0) | 1 |
| (33.75, 45.0) | (33.75, 39.375) | (39.375, 45.0) | 1 |
| (39.375, 45.0) | (39.375, 42.1875) | (42.1875, 45.0) | 0 |
| (39.375, 42.1875) | (39.375, 40.7812) | (40.7812, 42.1875) | 0 |
| (39.375, 40.7812) | (39.375, 40.0781) | (40.0781, 40.7812) | 0 |
| (39.375, 40.0781) | (39.375, 39.7265) | (39.7265, 40.0781) | 1 |
| (39.7265, 40.0781) | (39.7265, 39.9023) | (39.9023, 40.0781) | 1 |
| (39.9023, 40.0781) | (39.9023, 39.9902) | (39.9902, 40.0781) | 0 |
| (39.9023, 39.9902) | (39.9023, 39.9462) | (39.9462, 39.9902) | 0 |
| (39.9023, 39.9462) | (39.9023, 39.9243) | (39.9243, 39.9462) | 0 |
| (39.9023, 39.9243) | (39.9023, 39.9133) | (39.9133, 39.9243) | 1 |
| (39.9133, 39.9243) | (39.9133, 39.9188) | (39.9188, 39.9243) | 1 |
| (39.9188, 39.9243) | (39.9188, 39.9215) | (39.9215, 39.9243) | 1 |
經(jīng)度也用同樣的算法，對(-180, 180)依次細分，得到116.3906的編碼為1101 0010 1100 0100 0100。
| 經(jīng)度范圍 | 劃分區(qū)間0 | 劃分區(qū)間1 | 116.3906所屬區(qū)間 |
| (-180, 180) | (-180, 0.0) | (0.0, 180) | 1 |
| (0.0, 180) | (0.0, 90.0) | (90.0, 180) | 1 |
| (90.0, 180) | (90.0, 135.0) | (135.0, 180) | 0 |
| (90.0, 135.0) | (90.0, 112.5) | (112.5, 135.0) | 1 |
| (112.5, 135.0) | (112.5, 123.75) | (123.75, 135.0) | 0 |
| (112.5, 123.75) | (112.5, 118.125) | (118.125, 123.75) | 0 |
| (112.5, 118.125) | (112.5, 115.312) | (115.312, 118.125) | 1 |
| (115.312, 118.125) | (115.312, 116.718) | (116.718, 118.125) | 0 |
| (115.312, 116.718) | (115.312, 116.015) | (116.015, 116.718) | 1 |
| (116.015, 116.718) | (116.015, 116.367) | (116.367, 116.718) | 1 |
| (116.367, 116.718) | (116.367, 116.542) | (116.542, 116.718) | 0 |
| (116.367, 116.542) | (116.367, 116.455) | (116.455, 116.542) | 0 |
| (116.367, 116.455) | (116.367, 116.411) | (116.411, 116.455) | 0 |
| (116.367, 116.411) | (116.367, 116.389) | (116.389, 116.411) | 1 |
| (116.389, 116.411) | (116.389, 116.400) | (116.400, 116.411) | 0 |
| (116.389, 116.400) | (116.389, 116.394) | (116.394, 116.400) | 0 |
接下來將經(jīng)度和緯度的編碼合并，奇數(shù)位是緯度，偶數(shù)位是經(jīng)度，得到編碼 11100 11101 00100 01111 00000 01101 01011 00001。
最后，用0-9、b-z（去掉a, i, l, o）這32個字母進行base32編碼，得到(39.92324, 116.3906)的編碼為wx4g0ec1。
| 十進制 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
| base32 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | b | c | d | e | f | g |
| 十進制 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 |
| base32 | h | j | k | m | n | p | q | r | s | t | u | v | w | x | y | z |
解碼算法與編碼算法相反，先進行base32解碼，然后分離出經(jīng)緯度，最后根據(jù)二進制編碼對經(jīng)緯度范圍進行細分即可，這里不再贅述。 不過由于geohash表示的是區(qū)間，編碼越長越精確，但不可能解碼出完全一致的地址。
Geohash的應(yīng)用：附近地址搜索
geohash的最大用途就是附近地址搜索了。不過，從geohash的編碼算法中可以看出它的一個缺點：位于格子邊界兩側(cè)的兩點， 雖然十分接近，但編碼會完全不同。實際應(yīng)用中，可以同時搜索當(dāng)前格子周圍的8個格子，即可解決這個問題。
最后，我們來看看本文開頭提出的兩個問題：速度慢，緩存命中率低。使用geohash查詢附近地點，用的是字符串前綴匹配：
而前綴匹配可以利用geohash列上的索引，因此查詢速度不會太慢。另外，即使用戶坐標發(fā)生微小的變化， 也能編碼成相同的geohash，這就保證了每次執(zhí)行相同的SQL語句，使得緩存命中率大大提高。
相關(guān)文章
這篇文章主要介紹了利用git提交代碼的方法步驟，文中通過示例代碼介紹的非常詳細，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-08-08
本文介紹了三種使用Git操作代碼倉庫的方法：首先是克隆整個倉庫后切換至指定分支,其次是在克隆時直接指定分支,最后是在本地空倉庫中拉取指定分支的代碼,每種方法適用于不同的場景,幫助用戶靈活高效地管理代碼2024-10-10
本系列教程將會講解郵件的基本常識與概念，郵件的協(xié)議以及郵件服務(wù)器的工作原理，然后用JavaMail發(fā)送郵件的基本實現(xiàn)過程，郵件內(nèi)嵌圖片等高級郵件技巧。相信大家看完后，一定會有所收獲2022-05-05
前些天不小心刪除了原來的博客系統(tǒng)，問過godaddy的客服，恢復(fù)數(shù)據(jù)需要150美元，另外還需要提供不少信息，我于是放棄，注冊了這個nunumick.me，打算從頭再來。2011-09-09
Fiddler?Everywhere?4.0.1的破解及禁止更新的方法(最新推薦)
Fiddler?Everywhere是個好東西,無論抓包還是調(diào)試接口都很好用,只是現(xiàn)在收費了,為了白嫖就決定折騰一下,如果一開始通過設(shè)置文件夾權(quán)限禁止更新,也會導(dǎo)致進不了使用界面而無法使用,下面說一下具體的解決過程2023-11-11
這篇文章主要介紹了Vscode中快速創(chuàng)建自定義代碼模板的方法，文中通過示例代碼介紹的非常詳細，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-08-08
VsCode中ctrl+s后會在當(dāng)前目錄下自動生成dist目錄的方法
這篇文章主要介紹了VsCode中ctrl+s后會在當(dāng)前目錄下自動生成dist目錄,本文給大家介紹的非常詳細，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值，需要的朋友可以參考下2020-09-09
先談?wù)勈裁聪肫疝D(zhuǎn)載一篇這樣的文章。由于寫java已經(jīng)有一段時間了，在使用api上基本上沒有障礙，但是對有些基礎(chǔ)知識老是容易忘記，如二進制和十進制的一些轉(zhuǎn)換問題。在此記錄一下，再次復(fù)習(xí)一下2013-02-02
怎樣寫好commit?message提高業(yè)務(wù)效率
這篇文章主要為大家介紹了如何寫好commit?message幫助業(yè)務(wù)團隊提高效率方法詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪2023-05-05
這篇文章主要介紹了搭建一個開源項目兩種方式安裝git，本文給大家介紹的非常詳細，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值,需要的朋友可以參考下2020-08-08