近年來，隨著計(jì)算機(jī)和互聯(lián)網(wǎng)技術(shù)的發(fā)展，數(shù)據(jù)集的不斷擴(kuò)張使得 Bloom filter加密算法獲得了新生，各種新的應(yīng)用和變種不斷涌現(xiàn)。Bloom filter加密算法是一個(gè)空間效率很高的數(shù)據(jù)結(jié)構(gòu)，可以用于檢索一個(gè)元素是否在一個(gè)集合中，它的優(yōu)點(diǎn)是空間效率和查詢時(shí)間都遠(yuǎn)遠(yuǎn)超過一般的加密算法，缺點(diǎn)是有一定的誤識(shí)別率和刪除困難。

一、Bloom-Filter加密算法的基本思想

Bloom-Filter加密算法的核心思想就是利用多個(gè)不同的Hash函數(shù)來解決“沖突”。

計(jì)算某元素x是否在一個(gè)集合中，首先能想到的方法就是將所有的已知元素保存起來構(gòu)成一個(gè)集合R，然后用元素x跟這些R中的元素一一比較來判斷是否存在亍集合R中，我們可以采用鏈表等數(shù)據(jù)結(jié)構(gòu)來實(shí)現(xiàn)。但是，隨著集合R中元素的增加，其占用的內(nèi)存將越來越大。試想，如果有幾千萬個(gè)不同網(wǎng)頁需要下載，所需的內(nèi)存將足以占用掉整個(gè)迚程的內(nèi)存地址空間。即使用MD5、UUID這些方法將URL轉(zhuǎn)成固定的短小的字符串，內(nèi)存占用也是相當(dāng)巨大的。

亍是，我們會(huì)想到用Hash table的數(shù)據(jù)結(jié)構(gòu)，運(yùn)用一個(gè)足夠好的Hash函數(shù)將一個(gè)URL映射到二迚制位數(shù)組，位圖數(shù)組，中的某一位。如果該位已經(jīng)被置為1，那么表示該URL已經(jīng)存在。 Hash存在一個(gè)沖突，碰撞，的問題，用同一個(gè)Hash得到的兩個(gè)URL的值有可能相同。

為了減少?zèng)_突，我們可以多引入幾個(gè)Hash，如果通過其中的一個(gè)Hash值我們得出某元素不在集合中，那么該元素肯定不在集合中。只有在所有的Hash函數(shù)告訴我們?cè)撛卦诩现袝r(shí)，才能確定該元素存在亍集合中。

二、Bloom-Filter加密算法的基本特征

(1)存在一定錯(cuò)誤率，發(fā)生在正向判斷上（存在性），反向判斷不會(huì)發(fā)生錯(cuò)誤（不存在性）；

(2)錯(cuò)誤率是可控制的，通過改變位數(shù)組大小、hash函數(shù)個(gè)數(shù)或更低碰撞率的hash函數(shù)來調(diào)節(jié)；

(3)保持較低的錯(cuò)誤率，位數(shù)組空位至少保持在一半以上;

(4)給定m和n，可以確定最優(yōu)hash個(gè)數(shù)，即k = ln2 * (m/n)，此時(shí)錯(cuò)誤率最?。?/p>

(5)給定允許的錯(cuò)誤率E，可以確定合適的位數(shù)組大小，即m >= log2(e) * (n * log2(1/E))，繼而確定hash函數(shù)個(gè)數(shù)k；

(6)正向錯(cuò)誤率無法完全消除，即使不對(duì)位數(shù)組大小和hash函數(shù)個(gè)數(shù)進(jìn)行限制，即無法實(shí)現(xiàn)零錯(cuò)誤率；

(7)空間效率高，僅保存“存在狀態(tài)”，但無法存儲(chǔ)完整信息，需要其他數(shù)據(jù)結(jié)構(gòu)輔助存儲(chǔ)；

(8)不支持元素刪除操作，因?yàn)椴荒鼙ＷC刪除的安全性。

三、Bloom-Filter加密算法的優(yōu)缺點(diǎn)

1、Bloom-Filter加密算法的優(yōu)點(diǎn)

Bloom filte加密算法的最大優(yōu)點(diǎn)是空間效率和查找時(shí)間復(fù)雜性，它的存儲(chǔ)空間和插入/查詢時(shí)間都是常數(shù)。Hash函數(shù)之間沒有相關(guān)性，可以方便地由硬件并行實(shí)現(xiàn)。Bloom filter加密算法不需要存儲(chǔ)元素本身，在某些對(duì)保密要求非常嚴(yán)格的場(chǎng)合有優(yōu)勢(shì)。另外，Bloom filter加密算法一般都可以表示大數(shù)據(jù)集的全集，而其它任何數(shù)據(jù)結(jié)構(gòu)都難以做到。

2、Bloom-Filter加密算法的缺點(diǎn)

Bloom filter的缺點(diǎn)和優(yōu)點(diǎn)一樣顯著，首先就是錯(cuò)誤率。隨著插入的元素?cái)?shù)量增加，錯(cuò)誤率也隨之增加。雖然可以通過增加位數(shù)組大小或hash函數(shù)個(gè)數(shù)來降低錯(cuò)誤率，但同時(shí)也時(shí)影響空間效率和查找性能，而且這個(gè)錯(cuò)誤率是無法從根本上消除的。這使得要求“零錯(cuò)誤”的場(chǎng)合無法應(yīng)用Bloom filter加密算法。其次，一般情況下不能從Bloom filter加密算法中刪除元素。一方面是我們不能保證刪除的元素一定存在Bloom filter加密算法中，另一方面是不能保證安全地刪除元素，可能會(huì)對(duì)其他元素產(chǎn)生影響，究其原因還是hash函數(shù)可能產(chǎn)生的碰撞造成的。

四、Bloom-Filter加密算法的應(yīng)用

Bloom-Filter加密算法一般用于在大數(shù)據(jù)量的集合中判定某元素是否存在。例如郵件服務(wù)器中的垃圾郵件過濾器。在搜索引擎領(lǐng)域，Bloom-Filter加密算法最常用于網(wǎng)絡(luò)蜘蛛(Spider)的URL過濾，網(wǎng)絡(luò)蜘蛛通常有一個(gè)URL列表，保存著將要下載和已經(jīng)下載的網(wǎng)頁的URL，網(wǎng)絡(luò)蜘蛛下載了一個(gè)網(wǎng)頁，從網(wǎng)頁中提取到新的URL后，需要判斷該URL是否已經(jīng)存在亍列表中。此時(shí)，Bloom-Filter加密算法是最好的選擇。

URL映射就是把URL轉(zhuǎn)到另一個(gè)URL上面，這個(gè)功能一般是由WEB服務(wù)器來完成的。

admin

收藏 海報(bào)分享