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