提到hash，相信大多數(shù)同學(xué)都不會(huì)陌生，之前很火現(xiàn)在也依舊很火的技術(shù)區(qū)塊鏈背后的底層原理之一就是hash，下面就從hash算法的原理和實(shí)際應(yīng)用等幾個(gè)角度，對(duì)hash算法進(jìn)行一個(gè)講解。

1、什么是Hash

Hash也稱散列、哈希，對(duì)應(yīng)的英文都是Hash?；驹砭褪前讶我忾L(zhǎng)度的輸入，通過Hash算法變成固定長(zhǎng)度的輸出。這個(gè)映射的規(guī)則就是對(duì)應(yīng)的Hash算法，而原始數(shù)據(jù)映射后的二進(jìn)制串就是哈希值?；顒?dòng)開發(fā)中經(jīng)常使用的MD5和SHA都是歷史悠久的Hash算法。

echomd5("這是一個(gè)測(cè)試文案"); //輸出結(jié)果：2124968af757ed51e71e6abeac04f98d

在這個(gè)例子里，這是一個(gè)測(cè)試文案是原始值，2124968af757ed51e71e6abeac04f98d 就是經(jīng)過hash算法得到的Hash值。整個(gè)Hash算法的過程就是把原始任意長(zhǎng)度的值空間，映射成固定長(zhǎng)度的值空間的過程。

2、Hash的特點(diǎn)

一個(gè)優(yōu)秀的hash算法，需要什么樣的要求呢？

a)、從hash值不可以反向推導(dǎo)出原始的數(shù)據(jù)
這個(gè)從上面MD5的例子里可以明確看到，經(jīng)過映射后的數(shù)據(jù)和原始數(shù)據(jù)沒有對(duì)應(yīng)關(guān)系

b)、輸入數(shù)據(jù)的微小變化會(huì)得到完全不同的hash值，相同的數(shù)據(jù)會(huì)得到相同的值

echomd5("這是一個(gè)測(cè)試文案"); //輸出結(jié)果：2124968af757ed51e71e6abeac04f98d echomd5("這是二個(gè)測(cè)試文案"); //輸出結(jié)果：bcc2a4bb4373076d494b2223aef9f702

可以看到我們只改了一個(gè)文字，但是整個(gè)得到的hash值產(chǎn)生了非常大的變化。

c)、哈希算法的執(zhí)行效率要高效，長(zhǎng)的文本也能快速地計(jì)算出哈希值

d)、hash算法的沖突概率要小

由于hash的原理是將輸入空間的值映射成hash空間內(nèi)，而hash值的空間遠(yuǎn)小于輸入的空間。根據(jù)抽屜原理，一定會(huì)存在不同的輸入被映射成相同輸出的情況。那么作為一個(gè)好的hash算法，就需要這種沖突的概率盡可能小。

桌上有十個(gè)蘋果，要把這十個(gè)蘋果放到九個(gè)抽屜里，無論怎樣放，我們會(huì)發(fā)現(xiàn)至少會(huì)有一個(gè)抽屜里面放不少于兩個(gè)蘋果。這一現(xiàn)象就是我們所說的“抽屜原理”。抽屜原理的一般含義為：“如果每個(gè)抽屜代表一個(gè)集合，每一個(gè)蘋果就可以代表一個(gè)元素，假如有n+1個(gè)元素放到n個(gè)集合中去，其中必定有一個(gè)集合里至少有兩個(gè)元素?！?抽屜原理有時(shí)也被稱為鴿巢原理。它是組合數(shù)學(xué)中一個(gè)重要的原理

3、Hash碰撞的解決方案

前面提到了hash算法是一定會(huì)有沖突的，那么如果我們?nèi)绻龅搅薶ash沖突需要解決的時(shí)候應(yīng)該怎么處理呢？比較常用的算法是鏈地址法和開放地址法。

3.1 鏈地址法

鏈表地址法是使用一個(gè)鏈表數(shù)組，來存儲(chǔ)相應(yīng)數(shù)據(jù)，當(dāng)hash遇到?jīng)_突的時(shí)候依次添加到鏈表的后面進(jìn)行處理。

鏈地址法示意圖

鏈地址在處理的流程如下：
添加一個(gè)元素的時(shí)候，首先計(jì)算元素key的hash值，確定插入數(shù)組中的位置。如果當(dāng)前位置下沒有重復(fù)數(shù)據(jù)，則直接添加到當(dāng)前位置。當(dāng)遇到?jīng)_突的時(shí)候，添加到同一個(gè)hash值的元素后面，行成一個(gè)鏈表。這個(gè)鏈表的特點(diǎn)是同一個(gè)鏈表上的Hash值相同。java的數(shù)據(jù)結(jié)構(gòu)HashMap使用的就是這種方法來處理沖突，JDK1.8中，針對(duì)鏈表上的數(shù)據(jù)超過8條的時(shí)候，使用了紅黑樹進(jìn)行優(yōu)化。由于篇幅原因，這里不深入討論相關(guān)數(shù)據(jù)結(jié)構(gòu)，有興趣的同學(xué)可以參考這篇文章：

《Java集合之一—HashMap》

3.2 開放地址法

開放地址法是指大小為 M 的數(shù)組保存 N 個(gè)鍵值對(duì)，其中 M > N。我們需要依靠數(shù)組中的空位解決碰撞沖突?；谶@種策略的所有方法被統(tǒng)稱為“開放地址”哈希表。線性探測(cè)法，就是比較常用的一種“開放地址”哈希表的一種實(shí)現(xiàn)方式。線性探測(cè)法的核心思想是當(dāng)沖突發(fā)生時(shí)，順序查看表中下一單元，直到找出一個(gè)空單元或查遍全表。簡(jiǎn)單來說就是：一旦發(fā)生沖突，就去尋找下 一個(gè)空的散列表地址，只要散列表足夠大，空的散列地址總能找到。

線性探測(cè)法的數(shù)學(xué)描述是：h(k, i) = (h(k, 0) + i) mod m，i表示當(dāng)前進(jìn)行的是第幾輪探查。i=1時(shí)，即是探查h(k, 0)的下一個(gè)；i=2，即是再下一個(gè)。這個(gè)方法是簡(jiǎn)單地向下探查。mod m表示：到達(dá)了表的底下之后，回到頂端從頭開始。

對(duì)于開放尋址沖突解決方法，除了線性探測(cè)方法之外，還有另外兩種比較經(jīng)典的探測(cè)方法，二次探測(cè)（Quadratic probing）和雙重散列（Double hashing）。但是不管采用哪種探測(cè)方法，當(dāng)散列表中空閑位置不多的時(shí)候，散列沖突的概率就會(huì)大大提高。為了盡可能保證散列表的操作效率，一般情況下，我們會(huì)盡可能保證散列表中有一定比例的空閑槽位。我們用裝載因子（load factor）來表示空位的多少。

散列表的裝載因子=填入表中的元素個(gè)數(shù)/散列表的長(zhǎng)度。裝載因子越大，說明沖突越多，性能越差。

3.3 兩種方案的demo示例

假設(shè)散列長(zhǎng)為8，散列函數(shù)H(K)=K mod 7，給定的關(guān)鍵字序列為{32,14,23,2, 20}
當(dāng)使用鏈表法時(shí)，相應(yīng)的數(shù)據(jù)結(jié)構(gòu)如下圖所示：

鏈表法demo

當(dāng)使用線性探測(cè)法時(shí)，相應(yīng)的數(shù)據(jù)結(jié)果如下圖所示：

開放地址-線性探測(cè)法

這里的兩種算法的區(qū)別是2這個(gè)元素，在鏈表法中還是在節(jié)點(diǎn)2的位置上，但是在線性探測(cè)法遇到?jīng)_突時(shí)會(huì)將沖突數(shù)據(jù)放到下一個(gè)空的位置下面。

4、hash算法在日?；顒?dòng)中的應(yīng)用

在日常運(yùn)營活動(dòng)中，我們活動(dòng)開發(fā)經(jīng)常遇到的應(yīng)用場(chǎng)景是信息加密、數(shù)據(jù)校驗(yàn)、負(fù)載均衡。下面分別對(duì)這三種應(yīng)用場(chǎng)景進(jìn)行講解。

4.1 信息加密

首先我們看一下信息加密的應(yīng)用。2011年CSDN脫庫事件，導(dǎo)致超過600W的用戶的密碼泄露，讓人失望的是，CSDN是明文存儲(chǔ)用戶的注冊(cè)郵箱和密碼的。作為用戶的非常隱私的信息，最簡(jiǎn)單的保護(hù)措施就是對(duì)密碼進(jìn)行hash加密。在客戶端對(duì)用戶輸入的密碼進(jìn)行hash運(yùn)算，然后在服務(wù)端的數(shù)據(jù)庫中保存用戶密碼的hash值。由于服務(wù)器端也沒有存儲(chǔ)密碼的明文，所以目前很多網(wǎng)站也就不再有找回密碼的功能了。

這里也友情提示一下大家：如果在使用中發(fā)現(xiàn)某網(wǎng)站還有提供找回密碼的功能，就要好好擔(dān)心下這個(gè)網(wǎng)站的安全性了。

看到這里有些同學(xué)會(huì)覺得那么我們是不是對(duì)用戶輸入的密碼進(jìn)行一次MD5加密就可以了呢，這樣就算惡意用戶知道了hash值，也沒有辦法拿到用戶的真實(shí)密碼。假設(shè)用戶的密碼是123456789，經(jīng)過一次md5以后得到的值是:

25f9e794323b453885f5181f1b624d0b

那么是不是使用了這個(gè)加密后的字符串來存密碼就萬無一失了呢，理想總是很豐滿，而現(xiàn)實(shí)總是很骨感的。

大家可以看一下這個(gè)網(wǎng)站：

https://www.cmd5.com/

這里是該網(wǎng)站的相關(guān)介紹：

本站針對(duì)md5、sha1等全球通用公開的加密算法進(jìn)行反向查詢，通過窮舉字符組合的方式，創(chuàng)建了明文密文對(duì)應(yīng)查詢數(shù)據(jù)庫，創(chuàng)建的記錄約90萬億條，占用硬盤超過500TB，查詢成功率95%以上，很多復(fù)雜密文只有本站才可查詢。已穩(wěn)定運(yùn)行十余年，國內(nèi)外享有盛譽(yù)

md5反查結(jié)果

那么一般針對(duì)這種問題，我們的解決之道就是引入salt(加鹽)，即利用特殊字符（鹽）和用戶的輸入合在一起組成新的字符串進(jìn)行加密。通過這樣的方式，增加了反向查詢的復(fù)雜度。但是這樣的方式也不是萬無一失，如果發(fā)生了鹽被泄露的問題，就需要所有用到的地方來重置密碼。

針對(duì)salt泄露的問題，其實(shí)還有一種解決辦法，即使用HMAC進(jìn)行加密（Hash-based Message Authentication Code）。這種算法的核心思路是加密使用的key是從服務(wù)器端獲取的，每一個(gè)用戶的是不一樣的。如果發(fā)生了泄露，那么也就是這一個(gè)用戶的會(huì)被泄露，不會(huì)影響到全局。

這里也留給大家一個(gè)思考點(diǎn)，如果惡意用戶直接抓取了你的活動(dòng)參與鏈接，也就是拿到了你計(jì)算后的hash值，那從技術(shù)的角度上說，我們還有沒有其他可以提升惡意用戶的違法成本呢？

4.2 數(shù)據(jù)校驗(yàn)

-git commit id
使用過git的同學(xué)都應(yīng)該清楚，每次git提交后都有一個(gè)commit id，比如:

19d02d2cc358e59b3d04f82677dbf3808ae4fc40

就是一次git commit的結(jié)果，那么這個(gè)id是如何生成出來的呢？查閱了相關(guān)資料，使用如下代碼可以進(jìn)行查看：

printf"commit%s"$(gitcat-filecommitHEAD|wc-c);gitcat-filecommitHEAD

git的commit id主要包括了以下幾部分內(nèi)容：Tree 哈希，parent哈希、作者信息和本次提交的備注。

單次git commit相關(guān)信息

針對(duì)這些信息進(jìn)行SHA-1 算法后得到值就是本次提交的commit id。簡(jiǎn)單來講，就是對(duì)于單次提交的頭信息的一個(gè)校驗(yàn)和。

Linux kernel開創(chuàng)者和Git的開發(fā)者——Linus說，Git使用了sha1并非是為了安全性，而是為了數(shù)據(jù)的完整性；它可以保證，在很多年后，你重新checkout某個(gè)commit時(shí)，一定是它多年前的當(dāng)時(shí)的狀態(tài)，完全一摸一樣，完全值得信任。

但最新研究表明，理論上對(duì)其進(jìn)行哈希碰撞（hash collision，不同的兩塊數(shù)據(jù)有相同的hash值）的攻擊可以在2^51（2的51次方）左右的次數(shù)內(nèi)實(shí)現(xiàn)。不過由于commit id 是針對(duì)單個(gè)倉庫里的，所以實(shí)際應(yīng)用中我們可以認(rèn)為如果兩個(gè)文件的SHA-1值是相同的，那么它們確是完全相同的內(nèi)容。

注：對(duì)于git里tree、parent等結(jié)構(gòu)感興趣的同學(xué)，可以參考下這篇文章《Git 內(nèi)部原理 - Git 對(duì)象》，這里由于篇幅原因就不進(jìn)行深入分析了。

版權(quán)校驗(yàn)
在數(shù)據(jù)校驗(yàn)方面的另一個(gè)應(yīng)用場(chǎng)景就是版權(quán)的保護(hù)或者違禁信息的打擊，比如某個(gè)小視頻，第一個(gè)用戶上傳的時(shí)候，我們認(rèn)為是版權(quán)所有者，計(jì)算一個(gè)hash值存下來。當(dāng)?shù)诙€(gè)用戶上傳的時(shí)候，同樣計(jì)算hash值，如果hash值一樣的話，就算同一個(gè)文件。這種方案其實(shí)也給用戶傳播違禁文件提高了一些門檻，不是簡(jiǎn)單的換一個(gè)名字或者改一下后綴名就可以躲避掉打擊了。（當(dāng)然這種方式也是可以繞過的，圖片的你隨便改一下顏色，視頻去掉一幀就又是完全不同的hash值了。注意：我沒有教你變壞，我只是和你在討論這個(gè)技術(shù)。。。）另外我們?cè)谏鐓^(qū)里，也會(huì)遇到玩家重復(fù)上傳同一張圖片或者視頻的情況，使用這種校驗(yàn)的方式，可以有效減少cos服務(wù)的存儲(chǔ)空間。

大文件分塊校驗(yàn)
使用過bt的同學(xué)都有經(jīng)驗(yàn)，在p2p網(wǎng)絡(luò)中會(huì)把一個(gè)大文件拆分成很多小的數(shù)據(jù)各自傳輸。這樣的好處是如果某個(gè)小的數(shù)據(jù)塊在傳輸過程中損壞了，只要重新下載這個(gè)塊就好。為了確保每一個(gè)小的數(shù)據(jù)塊都是發(fā)布者自己傳輸?shù)?，我們可以?duì)每一個(gè)小的數(shù)據(jù)塊都進(jìn)行一個(gè)hash的計(jì)算，維護(hù)一個(gè)hash List，在收到所有數(shù)據(jù)以后，我們對(duì)于這個(gè)hash List里的每一塊進(jìn)行遍歷比對(duì)。這里有一個(gè)優(yōu)化點(diǎn)是如果文件分塊特別多的時(shí)候，如果遍歷對(duì)比就會(huì)效率比較低。可以把所有分塊的hash值組合成一個(gè)大的字符串，對(duì)于這個(gè)字符串再做一次Hash運(yùn)算，得到最終的hash（Root hash）。在實(shí)際的校驗(yàn)中，我們只需要拿到了正確的Root hash，即可校驗(yàn)Hash List，也就可以校驗(yàn)每一個(gè)數(shù)據(jù)塊了。

大文件分塊示意圖

4.3 負(fù)載均衡

活動(dòng)開發(fā)同學(xué)在應(yīng)對(duì)高星級(jí)業(yè)務(wù)大用戶量參與時(shí)，都會(huì)使用分庫分表，針對(duì)用戶的openid進(jìn)行hashtime33取模，就可以得到對(duì)應(yīng)的用戶分庫分表的節(jié)點(diǎn)了。

活動(dòng)分庫分表示意圖

如上圖所示，這里其實(shí)是分了10張表，openid計(jì)算后的hash值取模10，得到對(duì)應(yīng)的分表，在進(jìn)行后續(xù)處理就好。對(duì)于一般的活動(dòng)或者系統(tǒng)，我們一般設(shè)置10張表或者100張表就好。

下面我們來看一點(diǎn)復(fù)雜的問題，假設(shè)我們活動(dòng)初始分表了10張，運(yùn)營一段時(shí)間以后發(fā)現(xiàn)需要10張不夠，需要改到100張。這個(gè)時(shí)候我們?nèi)绻苯訑U(kuò)容的話，那么所有的數(shù)據(jù)都需要重新計(jì)算Hash值，大量的數(shù)據(jù)都需要進(jìn)行遷移。如果更新的是緩存的邏輯，則會(huì)導(dǎo)致大量緩存失效，發(fā)生雪崩效應(yīng)，導(dǎo)致數(shù)據(jù)庫異常。造成這種問題的原因是hash算法本身的緣故，只要是取模算法進(jìn)行處理，則無法避免這種情況。針對(duì)這種問題，我們就需要利用一致性hash進(jìn)行相應(yīng)的處理了。

一致性hash的基本原理是將輸入的值hash后，對(duì)結(jié)果的hash值進(jìn)行2^32取模，這里和普通的hash取模算法不一樣的點(diǎn)是在一致性hash算法里將取模的結(jié)果映射到一個(gè)環(huán)上。將緩存服務(wù)器與被緩存對(duì)象都映射到hash環(huán)上以后，從被緩存對(duì)象的位置出發(fā)，沿順時(shí)針方向遇到的第一個(gè)服務(wù)器，就是當(dāng)前對(duì)象將要緩存于的服務(wù)器，由于被緩存對(duì)象與服務(wù)器hash后的值是固定的，所以，在服務(wù)器不變的情況下，一個(gè)openid必定會(huì)被緩存到固定的服務(wù)器上，那么，當(dāng)下次想要訪問這個(gè)用戶的數(shù)據(jù)時(shí)，只要再次使用相同的算法進(jìn)行計(jì)算，即可算出這個(gè)用戶的數(shù)據(jù)被緩存在哪個(gè)服務(wù)器上，直接去對(duì)應(yīng)的服務(wù)器查找對(duì)應(yīng)的數(shù)據(jù)即可。這里的邏輯其實(shí)和直接取模的是一樣的。如下圖所示：

初始3臺(tái)機(jī)器的情況

初始情況如下：用戶1的數(shù)據(jù)在服務(wù)器A里，用戶2、3的數(shù)據(jù)存在服務(wù)器C里，用戶4的數(shù)據(jù)存儲(chǔ)在服務(wù)器B里

下面我們來看一下當(dāng)服務(wù)器數(shù)量發(fā)生變化的時(shí)候，相應(yīng)影響的數(shù)據(jù)情況：

服務(wù)器縮容

服務(wù)器縮容

服務(wù)器B發(fā)生了故障，進(jìn)行剔除后，只有用戶4的數(shù)據(jù)發(fā)生了異常。這個(gè)時(shí)候我們需要繼續(xù)按照順時(shí)針的方案，把緩存的數(shù)據(jù)放在用戶A上面。

服務(wù)器擴(kuò)容
同樣的，我們進(jìn)行了服務(wù)器擴(kuò)容以后，新增了一臺(tái)服務(wù)器D，位置落在用戶2和3之間。按照順時(shí)針原則，用戶2依然訪問的是服務(wù)器C的數(shù)據(jù)，而用戶3順時(shí)針查詢后，發(fā)現(xiàn)最近的服務(wù)器是D，后續(xù)數(shù)據(jù)就會(huì)存儲(chǔ)到d上面。

服務(wù)器擴(kuò)容示意圖

虛擬節(jié)點(diǎn)
當(dāng)然這只是一種理想情況，實(shí)際使用中，由于服務(wù)器節(jié)點(diǎn)數(shù)量有限，有可能出現(xiàn)分布不均勻的情況。這個(gè)時(shí)候會(huì)出現(xiàn)大量數(shù)據(jù)都被映射到某一臺(tái)服務(wù)器的情況，如下圖左側(cè)所示。為了解決這個(gè)問題，我們采用了虛擬節(jié)點(diǎn)的方案。虛擬節(jié)點(diǎn)是實(shí)際節(jié)點(diǎn)（實(shí)際的物理服務(wù)器）在hash環(huán)上的復(fù)制品，一個(gè)實(shí)際節(jié)點(diǎn)可以對(duì)應(yīng)多個(gè)虛擬節(jié)點(diǎn)。虛擬節(jié)點(diǎn)越多，hash環(huán)上的節(jié)點(diǎn)就越多，數(shù)據(jù)被均勻分布的概率就越大。

虛擬節(jié)點(diǎn)示意圖

如右圖所示，B、C、D 是原始節(jié)點(diǎn)復(fù)制出來的虛擬節(jié)點(diǎn)，原本都要訪問機(jī)器D的用戶1、4，分別被映射到了B,D。通過這樣的方式，起到了一個(gè)服務(wù)器均勻分布的作用。

5、幾種hash算法的擴(kuò)展應(yīng)用

下面介紹幾種大家可能不經(jīng)常遇到的應(yīng)用，由于篇幅原因，不做深入介紹，只拋磚引玉。

5.1 SimHash

simHash是google用于海量文本去重的一種方法，它是一種局部敏感hash。那什么叫局部敏感呢，假定兩個(gè)字符串具有一定的相似性，在hash之后，仍然能保持這種相似性，就稱之為局部敏感hash。普通的hash是不具有這種屬性的。simhash被Google用來在海量文本中去重。

simHash算法的思路大致如下：

將Doc進(jìn)行關(guān)鍵詞抽取(其中包括分詞和計(jì)算權(quán)重)，抽取出n個(gè)(關(guān)鍵詞，權(quán)重)對(duì)， 即圖中的多個(gè)(feature, weight)。記為 feature_weight_pairs = [fw1, fw2 … fwn]，其中 fwn = (feature_n,weight_n)。

對(duì)每個(gè)feature_weight_pairs中的feature進(jìn)行hash。然后對(duì)hash_weight_pairs進(jìn)行位的縱向累加，如果該位是1，則+weight,如果是0，則-weight，最后生成bits_count個(gè)數(shù)字，大于0標(biāo)記1，小于0標(biāo)記0

最后轉(zhuǎn)換成一個(gè)64位的字節(jié)，判斷重復(fù)只需要判斷他們的特征字的距離是不是

SimHash計(jì)算流程

如下圖所示，當(dāng)兩個(gè)文本只有一個(gè)字變化時(shí)，如果使用普通Hash則會(huì)導(dǎo)致兩次的結(jié)果發(fā)生較大改變，而SimHash的局部敏感特性，會(huì)導(dǎo)致只有部分?jǐn)?shù)據(jù)發(fā)生變化。

SimHash結(jié)果

5.2 GeoHash

GeoHash將地球作為為一個(gè)二維平面進(jìn)行遞歸分解。每個(gè)分解后的子塊在一定經(jīng)緯度范圍內(nèi)擁有相同的編碼。以下圖為例，這個(gè)矩形區(qū)域內(nèi)所有的點(diǎn)（經(jīng)緯度坐標(biāo)）都共享相同的GeoHash字符串，這樣既可以保護(hù)隱私（只表示大概區(qū)域位置而不是具體的點(diǎn)），又比較容易做緩存。

GeoHash示意圖

下面以一個(gè)例子來理解下這個(gè)算法，我們對(duì)緯度39.3817進(jìn)行逼近編碼 ：

地球緯度區(qū)間是[-90,90]，對(duì)于這個(gè)區(qū)間進(jìn)行二分劃分左區(qū)間[-90,0), 右區(qū)間[0,90]。39.3817屬于右區(qū)間，標(biāo)記為1

將右區(qū)間[0,90]繼續(xù)進(jìn)行劃分，左區(qū)間[0,45) ,右區(qū)間[45,90]。39.3817屬于左區(qū)間，標(biāo)記為0

遞歸上面的過程，隨著每次迭代，區(qū)間[a，b]會(huì)不斷接近39.3817。遞歸的次數(shù)決定了生成的序列長(zhǎng)度。

對(duì)于經(jīng)度做同樣的處理。得到的字符串，偶數(shù)位放經(jīng)度，奇數(shù)位放緯度，把2串編碼組合生成新串。對(duì)于新串轉(zhuǎn)成對(duì)應(yīng)10進(jìn)制查出實(shí)際的base32編碼就是類似WX4ER的hash值。

整體遞歸過程如下表所示：

這里有一篇文章詳細(xì)介紹了GeoHash，有興趣的同學(xué)可以移步這里：

是什么能讓 APP 快速精準(zhǔn)定位到我們的位置？

5.3 布隆過濾器

布隆過濾器被廣泛用于黑名單過濾、垃圾郵件過濾、爬蟲判重系統(tǒng)以及緩存穿透問題。對(duì)于數(shù)量小，內(nèi)存足夠大的情況，我們可以直接用hashMap或者h(yuǎn)ashSet就可以滿足這個(gè)活動(dòng)需求了。但是如果數(shù)據(jù)量非常大，比如5TB的硬盤上放滿了用戶的參與數(shù)據(jù)，需要一個(gè)算法對(duì)這些數(shù)據(jù)進(jìn)行去重，取得活動(dòng)的去重參與用戶數(shù)。這種時(shí)候，布隆過濾器就是一種比較好的解決方案了。

布隆過濾器其實(shí)是基于bitmap的一種應(yīng)用，在1970年由布隆提出的。它實(shí)際上是一個(gè)很長(zhǎng)的二進(jìn)制向量和一系列隨機(jī)映射函數(shù)，用于檢索一個(gè)元素是否在一個(gè)集合中。它的優(yōu)點(diǎn)是空間效率和查詢時(shí)間都遠(yuǎn)遠(yuǎn)超過一般的算法，缺點(diǎn)是有一定的誤識(shí)別率和刪除困難，主要用于大數(shù)據(jù)去重、垃圾郵件過濾和爬蟲url記錄中。核心思路是使用一個(gè)bit來存儲(chǔ)多個(gè)元素，通過這樣的方式來減少內(nèi)存的消耗。通過多個(gè)hash函數(shù)，將每個(gè)數(shù)據(jù)都算出多個(gè)值，存放在bitmap中對(duì)應(yīng)的位置上。

布隆過濾器的原理見下圖所示：

布隆過濾器原理示意

上圖所示的例子中，數(shù)據(jù)a、b、c經(jīng)過三次hash映射后，對(duì)應(yīng)的bit位都是1，表示這三個(gè)數(shù)據(jù)已經(jīng)存在了。而d這份數(shù)據(jù)經(jīng)過映射后有一個(gè)結(jié)果是0，則表明d這個(gè)數(shù)據(jù)一定沒有出現(xiàn)過。布隆過濾器存在假陽率（判定存在的元素可能不存在）的問題，但是沒有假陰率（判斷不存在的原因可能存在）的問題。即對(duì)于數(shù)據(jù)e，三次映射的結(jié)果都是1，但是這份數(shù)據(jù)也可能沒有出現(xiàn)過。

誤判率的數(shù)據(jù)公式如下所示：

其中，p是誤判率，n是容納的元素，m是需要的存儲(chǔ)空間。由公示可以看出，布隆過濾器的長(zhǎng)度會(huì)直接影響誤報(bào)率，布隆過濾器越長(zhǎng)其誤報(bào)率越小。哈希函數(shù)的個(gè)數(shù)也需要權(quán)衡，個(gè)數(shù)越多則布隆過濾器 bit 位置位 1 的速度越快，且布隆過濾器的效率越低；但是如果太少的話，則會(huì)導(dǎo)致誤報(bào)率升高。

6、總結(jié)

Hash算法作為一種活動(dòng)開發(fā)經(jīng)常遇到的算法，我們?cè)谑褂弥胁粌H僅要知道這種算法背后真正的原理，才可以在使用上做到有的放矢。Hash的相關(guān)知識(shí)還有很多，有興趣的同學(xué)可以繼續(xù)深入研究。