随着移動網際網路的發展，很多基于地理位置資訊的服務也越來越流行。比如說我們平常經常使用的查找附近的人，或者是附近的餐館，共享單車等等。
那麼，大家有沒有想過，這個查找功能是如何實作的嗎？作為受過高等教育的人，大家肯定立即就想到了可以通過經緯度進行計算。具體算法類似于這樣：
地球近似于一個球體，地球赤道周長約40075.04公裡，半徑約為6371公裡，是以，可以很容易地用立體幾何的方法求出其距離，例如說最常見的大圓距離（Great-Circle Distance）。
公式如下：
其中， R為地球半徑，Aj、Aw分别表示A點的經度、緯度；Bj、Bw分别表示B點的經度、緯度。這樣，通過簡單的立體幾何方法就可以很容易地求出其距離。
如果有人對于地理資訊學比較了解的話，還會知道半正矢公式（Haversine公式），因為大圓距離公式用到了大量的餘弦函數，是以在兩點距離過短的時候，會導緻比較大的舍入誤差。而半正矢公式則因為采用了正弦函數的方法，是以即使距離過小，也可以保留足夠的有效數字。半正矢公式的形式如下所示：
其中
這裡面的R為地球半徑，可取平均值 6371km；φ1, φ2 表示兩點的緯度；Δλ 表示兩點經度的內插補點。
有了這些算法，那麼理論上來查找附近的人就可以很友善地實作了。但是為什麼要說從理論上講呢？因為在工程實踐中，這樣查找的計算量太大了。對于幾個經緯度的資料而言還可以，但是對于大規模資料查詢而言，沒有實際可操作性。就比如想在一個一百萬條資料的資料庫裡查找附近5公裡之内的餐館有哪些，那麼要對一百萬條資料做各種三角函數操作，這顯然是不現實的事情，更别說在網際網路上應用的資料體量遠大于百萬條。而且這樣的資料也很難對其查詢效率進行優化。
那麼，要怎麼解決這個問題呢？這就是我們今天要介紹的神奇算法，Geohash算法了。通過Geohash算法，我們可以把兩個坐标的距離計算簡化為兩個字元串的比較，進而可以最大限度的應用速度更快的字元串相關函數，并且對其進行排序或索引。
下面我們就來看看Geohash算法具體是怎麼做到這一點的。
Geohash的本質就是将用到的整個地圖區域進行矩形分割，然後在各個矩形之中再次進行矩形分割，而每一次分割中所在的區域用一個字元代表，這樣一次次分割之後，就可以最大可能的逼近實際坐标所在地。而這個坐标也就可以用一串字元來代替了。常用的Geohash算法中，每個字元用5個比特來辨別，這樣就會有32個不同的組合（0-31），于是我們就可以将這個地圖區域劃分為32個區域。然後我們再對各個區域繼續進行劃分，就會得到類似于wx4eqzrx，這樣的一個字元串了。
而這時，我們就可以友善地使用類似于
Select * from world where geohash like 'wx4eqw%';
這樣的sql語句查詢到附近想要查詢的東西了。是不是很友善呢？通過這種方式，我們就把複雜的三角函數計算，轉化成了計算化處理效率非常高的字元串操作了。
那麼，想必大家一定要問了，坐标轉化成的字元串是怎麼生成的呢？其實也很簡單。
我們以緯度39.928167為例。
a. 首先我們以區間[-90,90]進行二分為[-90,0),[0,90]，稱為左右區間，可以确定39.928167屬于右區間[0,90]，标記為1
b. 接着将區間[0,90]進行二分為 [0,45),[45,90]，可以确定39.928167屬于左區間 [0,45)，标記為0
c. 遞歸上述過程39.928167總是屬于某個區間[a,b]。随着每次疊代區間[a,b]總在縮小，并越來越逼近39.928167，劃分次數越多，距離就越精确，字元串也就會越長，如下圖所示：
這樣我們就得到了緯度的二進制表示，同樣我們也可以對經度進行二進制表示。然後，我們把經度放到偶數位，緯度放到奇數位，把兩個二進制串合并到一起，最後将得到的二進制串編碼每5位進行base32編碼，最終就得到了我們想要的，對于每個小方格進行表示的Geohash字元串序列。
但是這樣做了之後，很多人會發現一個問題，那就是每個Geohash字元串事實上都是代表一個小方格的，那麼就會産生邊界跨越的問題。就像下圖中的紅點，和上面的綠點并不在一個方格裡，是以如果我們光查詢紅點所在的格子的話，就會查詢不到明明離它很近的上面的綠點，反而可以查詢到更遠一點的下面的綠點。
那麼怎麼解決這個問題呢？其實也很簡單，就是在查詢的時候，把周圍的8個格子也考慮進來一起查詢就行了。那麼具體是怎麼做的呢？我們可以看到，周圍的8個格子，本質上就是經度緯度的格子二進制數與中間的格子差1，是以我們隻需要對紅點的經緯度二進制數，進行加減1的操作就可以擷取到附近格子的字元串了。而這樣做本質上就是損失了一個格子的精度。而在經緯度位數足夠的情況下，這個誤差是可以忽略不計的。通過計數我們可以得出：
在緯度相等的情況下，經度每隔0.00001度，距離相差約1米；在經度相等的情況下，緯度每隔0.00001度，距離相差約1.1米；而在geohash的位數是9位數的時候，大概為附近2米；8位的話，大約為附近19米。對于大部分人來講，可以說是一個可以接受的誤差了哦。
喜歡本文的話，歡迎關注活在資訊時代哦：）