?隨著移動互聯網的發展，很多基于地理位置信息的服務也越來越流行。比如說我們平常經常使用的查找附近的人，或者是附近的餐館，共享單車等等。

那么，大家有沒有想過，這個查找功能是如何實現的嗎？作為受過高等教育的人，大家肯定立即就想到了可以通過經緯度進行計算。具體算法類似于這樣：

地球近似于一個球體，地球赤道周長約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米。對于大部分人來講，可以說是一個可以接受的誤差了哦。?