BloomFilter&python支持
?
?
BloomFilter
布隆過濾器是一種概率空間高效的數據結構。它與hashmap非常相似,用于檢索一個元素是否在一個集合中。
它在檢索元素是否存在時,能很好地取舍空間使用率與誤報比例。即Bloom Filter是會誤判的,它只會把不存在于集合中的元素誤判成存在于集合中,而不會把存在于集合中的元素誤判成不存在集合中。
正是由于這個特性,它被稱作概率性數據結構(probabilistic data structure)。
?
?
BloomFilter原理
布隆過濾器維護一個N位的位數組,其中N是位數組的大小。它還有另一個參數k,表示使用哈希函數的個數。這些哈希函數用來設置位數組的值。當往過濾器中插入元素x時,h1(x), h2(x), ..., hk(x)所對應索引位置的值被置“1”,索引值由各個哈希函數計算得到。注意,如果我們增加哈希函數的數量,誤報的概率會趨近于0.但是,插入和查找的時間開銷更大,布隆過濾器的容量也會減小。
為了用布隆過濾器檢驗元素是否存在,我們需要校驗是否所有的位置都被置“1”,與我們插入元素的過程非常相似。如果所有位置都被置“1”,那也就意味著該元素很有可能存在于布隆過濾器中。若有位置未被置“1”,那該元素一定不存在。
?
記錄元素
下面我們看一下向Bloom Filter插入字符串的具體過,就是把這個字符串str經過K個不同的hash函數計算得到的結果h1、h2、、、hK。然后在BitArrray的第h1、h2、、、hK的位置上置1。
判斷元素
?那么如何判斷一個字符串是否存在呢
?把這個字符串經過K個hash函數計算得到h1、h2、、、hK,然后逐個判斷BitArray的第h1、h2、、、hK個位置是否是1
?
?
應用場景
Google著名的分布式數據庫Bigtable以及Hbase使用了布隆過濾器來查找不存在的行或列,以及減少磁盤查找的IO次數
文檔存儲檢查系統也采用布隆過濾器來檢測先前存儲的數據
Goole Chrome瀏覽器使用了布隆過濾器加速安全瀏覽服務
垃圾郵件地址過濾
爬蟲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)
結果:
True
True
False
?
?
優點:
1.全量存儲但是不存儲元素本身,在某些對保密要求非常嚴格的場合有優勢
2.空間高效率
3.插入/查詢時間都是常數O(k),遠遠超過一般的算法
缺點:
1.存在誤算率(False Positive),隨著存入的元素數量增加,誤算率隨之增加
布隆過濾器能確保某個元素“肯定不存在”,但是對于一些元素的判斷會是“可能存在”
2.一般情況下不能從布隆過濾器中刪除元素
3.數組長度以及hash函數個數確定過程復雜
4.無法得到元素本身
布隆過濾器并不會保存插入元素的內容,只能檢索某個元素是否存在
?
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索:z360901061

微信掃一掃加我為好友
QQ號聯系: 360901061
您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。
【本文對您有幫助就好】元
