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

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

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

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

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

為了減少沖突，我們可以多引入幾個Hash，如果通過其中的一個Hash值我們得出某元素不在集合中，那么該元素肯定不在集合中。只有在所有的Hash函數(shù)告訴我們該元素在集合中時，才能確定該元素存在亍集合中。

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

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

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

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

(4)給定m和n，可以確定最優(yōu)hash個數(shù)，即k = ln2 * (m/n)，此時錯誤率最??；

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

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

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

(8)不支持元素刪除操作，因為不能保證刪除的安全性。

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

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

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

2、Bloom-Filter加密算法的缺點

Bloom filter的缺點和優(yōu)點一樣顯著，首先就是錯誤率。隨著插入的元素數(shù)量增加，錯誤率也隨之增加。雖然可以通過增加位數(shù)組大小或hash函數(shù)個數(shù)來降低錯誤率，但同時也時影響空間效率和查找性能，而且這個錯誤率是無法從根本上消除的。這使得要求“零錯誤”的場合無法應(yīng)用Bloom filter加密算法。其次，一般情況下不能從Bloom filter加密算法中刪除元素。一方面是我們不能保證刪除的元素一定存在Bloom filter加密算法中，另一方面是不能保證安全地刪除元素，可能會對其他元素產(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ò)蜘蛛通常有一個URL列表，保存著將要下載和已經(jīng)下載的網(wǎng)頁的URL，網(wǎng)絡(luò)蜘蛛下載了一個網(wǎng)頁，從網(wǎng)頁中提取到新的URL后，需要判斷該URL是否已經(jīng)存在亍列表中。此時，Bloom-Filter加密算法是最好的選擇。

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

admin

收藏 海報分享