看到了這篇文章有種相見恨晚的感覺~之前上cloud computing糾結(jié)consistent hashing觉既，做地圖搜索也用到了geohash的知識，有時間再把consistent hashing復(fù)習(xí)一下絮记。
1. 一致性哈希
一致性哈希算法是在1997年由麻省理工學(xué)院提出，設(shè)計的目標(biāo)是為了解決因特網(wǎng)的熱點問題紧憾。一致性哈希算法解決了在P2P環(huán)境中最為關(guān)鍵的問題到千，即如何在動態(tài)的網(wǎng)絡(luò)拓?fù)渲蟹植即鎯吐酚伞Ｔ诜植际较到y(tǒng)中用得比較廣泛赴穗，當(dāng)集群需要添加機器或者減少一臺機器時憔四，一致性哈希只影響一臺機器，將數(shù)據(jù)受影響的機器數(shù)量降到最低般眉。
在這里講述了一致性哈希的原理了赵，并且在最后有各種語言版本的實現(xiàn)。在Github上也有一個不錯的實現(xiàn)版本甸赃。
2. 局部敏感哈希
局部敏感哈希是一種高維數(shù)據(jù)索引技術(shù)柿汛。英文名為Locality-Sensitive Hashing，簡記為LSH埠对，應(yīng)用于計算機很多領(lǐng)域络断。想象在一個高維數(shù)據(jù)檢索系統(tǒng)中，檢索庫中數(shù)據(jù)量很大项玛，每條數(shù)據(jù)的維度也很高貌笨。常規(guī)的做法就是針對每一次檢索，都從數(shù)據(jù)庫中進行一一匹配襟沮，這樣將花費大量的時間和空間锥惋，顯然不可取。
然后开伏，我們就可以從兩個方面考慮：
（1）通過一些算法對原始高維數(shù)據(jù)進行降維
（2）在檢索初始階段排除一些數(shù)據(jù)膀跌，減少檢索時的比較次數(shù)
針對（2）有局部敏感Hash恰好滿足了我們的要求。它的原理也容易理解固灵。局部敏感哈希的實現(xiàn)有多種方式捅伤。需要注意的是上述方法并不能夠一定保證查找到查詢點的最鄰近的數(shù)據(jù)，而是減少需要匹配的數(shù)據(jù)點個數(shù)的同時保證查找到最近鄰的數(shù)據(jù)點的概率很大巫玻。為了解決這個問題暑认，又提出了增強LSH。
關(guān)于p-stableLSH算法可以參考這里大审。最后附上Java實現(xiàn)的局部敏感哈希工具蘸际。
3. Geohash
想象這樣一個場景，你在北京西二旗附近想找附近的餐館徒扶，只需要在手機上打開手機地圖粮彤，然后搜索附近的餐館就可以進一步找到你所滿意的一家。那么問題來了，地圖后臺是如何根據(jù)自己的位置來搜索附近的餐館呢导坟？接下來的Geohash算法就是用來解決這個問題的屿良，它將二維的經(jīng)緯度轉(zhuǎn)化為一個字符串。參見其原理詳細(xì)介紹惫周。
在github上有一個geohash的C語言實現(xiàn)代碼尘惧，并且附上了使用方法。Google有一個開源的Geohash代碼递递，詳
見鏈接：http://Python-geohash.googlecode.com/svn/trunk/喷橙，包括Python和C++實現(xiàn)。
