BloomFilter&python支持
?
?
BloomFilter
布隆過濾器是一種概率空間高效的數(shù)據(jù)結(jié)構(gòu)。它與hashmap非常相似，用于檢索一個元素是否在一個集合中。
它在檢索元素是否存在時，能很好地取舍空間使用率與誤報比例。即Bloom Filter是會誤判的，它只會把不存在于集合中的元素誤判成存在于集合中，而不會把存在于集合中的元素誤判成不存在集合中。
正是由于這個特性，它被稱作概率性數(shù)據(jù)結(jié)構(gòu)（probabilistic data structure）。
?
?
BloomFilter原理
布隆過濾器維護(hù)一個N位的位數(shù)組，其中N是位數(shù)組的大小。它還有另一個參數(shù)k，表示使用哈希函數(shù)的個數(shù)。這些哈希函數(shù)用來設(shè)置位數(shù)組的值。當(dāng)往過濾器中插入元素x時，h1(x), h2(x), ..., hk(x)所對應(yīng)索引位置的值被置“1”，索引值由各個哈希函數(shù)計算得到。注意，如果我們增加哈希函數(shù)的數(shù)量，誤報的概率會趨近于0.但是，插入和查找的時間開銷更大，布隆過濾器的容量也會減小。
為了用布隆過濾器檢驗元素是否存在，我們需要校驗是否所有的位置都被置“1”，與我們插入元素的過程非常相似。如果所有位置都被置“1”，那也就意味著該元素很有可能存在于布隆過濾器中。若有位置未被置“1”，那該元素一定不存在。
?
記錄元素
下面我們看一下向Bloom Filter插入字符串的具體過，就是把這個字符串str經(jīng)過K個不同的hash函數(shù)計算得到的結(jié)果h1、h2、、、hK。然后在BitArrray的第h1、h2、、、hK的位置上置1。
?
判斷元素
?那么如何判斷一個字符串是否存在呢
?把這個字符串經(jīng)過K個hash函數(shù)計算得到h1、h2、、、hK，然后逐個判斷BitArray的第h1、h2、、、hK個位置是否是1
?
?
應(yīng)用場景
Google著名的分布式數(shù)據(jù)庫Bigtable以及Hbase使用了布隆過濾器來查找不存在的行或列，以及減少磁盤查找的IO次數(shù)
文檔存儲檢查系統(tǒng)也采用布隆過濾器來檢測先前存儲的數(shù)據(jù)
Goole Chrome瀏覽器使用了布隆過濾器加速安全瀏覽服務(wù)
垃圾郵件地址過濾
爬蟲URL地址去重
解決緩存穿透問題
?
?python支持庫BloomFilter
from
bloom_filter
import
BloomFilter
bloombloom = BloomFilter(max_elements=10000, error_rate=0.1
)
#
max_elements是布隆過濾器的容積，最多可以記錄多少元素
#
error_rate是錯判率
#
向bloom添加元素
bloombloom.add(
'
https://www.tianyancha.com/company/23402373
'
)
bloombloom.add(
'
https://www.tianyancha.com/company/23402372
'
)
bloombloom.add(
'
https://www.tianyancha.com/company/2340231
'
)
bloombloom.add(
'
https://www.tianyancha.com/company/23402
'
)
bloombloom.add(
'
https://www.tianyancha.com/company/234
'
)
bloombloom.add(
'
https://www.tianyancha.com/company/234023
'
)
#
判斷URL是否在bloombloom.__contains__('https://www.tianyancha.com/company/23402373')
print
(bloombloom.
__contains__
(
'
https://www.tianyancha.com/company/23402373
'
))
s1
=
'
https://www.tianyancha.com/company/23402373
'
s2
=
"
1111
"
print
(s1
in
bloombloom)
print
(s2
in
bloombloom)
結(jié)果：
True
True
False
?
?
優(yōu)點：
1.全量存儲但是不存儲元素本身，在某些對保密要求非常嚴(yán)格的場合有優(yōu)勢
2.空間高效率
3.插入/查詢時間都是常數(shù)O(k),遠(yuǎn)遠(yuǎn)超過一般的算法
缺點：
1.存在誤算率(False Positive)，隨著存入的元素數(shù)量增加，誤算率隨之增加
布隆過濾器能確保某個元素“肯定不存在”，但是對于一些元素的判斷會是“可能存在”
2.一般情況下不能從布隆過濾器中刪除元素
3.數(shù)組長度以及hash函數(shù)個數(shù)確定過程復(fù)雜
4.無法得到元素本身
布隆過濾器并不會保存插入元素的內(nèi)容，只能檢索某個元素是否存在
?
更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯(lián)系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機(jī)微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
