亚洲免费在线-亚洲免费在线播放-亚洲免费在线观看-亚洲免费在线观看视频-亚洲免费在线看-亚洲免费在线视频

BloomFilter&python支持

系統 1730 0

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。

? BloomFilter&python支持_第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元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。

【本文對您有幫助就好】

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描上面二維碼支持博主2元、5元、10元、自定義金額等您想捐的金額吧,站長會非常 感謝您的哦?。?!

發表我的評論
最新評論 總共0條評論
主站蜘蛛池模板: 久艾草国产成人综合在线视频 | 有色视频在线观看 | 日本精品网站 | 精品人人 | 中文字幕一区二区三区免费视频 | 91伊人| 久久精品图片 | 天天爱天天爽 | 国产成人精品免费视频 | 97在线公开视频 | 色无极综合 | 夜夜狠狠 | 国产五月色婷婷六月丁香视频 | sihu国产精品永久免费 | 久久天堂成人影院 | 亚洲片在线 | 国产一区二区三区视频 | 一本一道 | 国产精品午夜高清在线观看 | 播放一级片 | 国产精品久久久久久久伊一 | 天天综合天天综合色在线 | 日本粉嫩毛片视频 | 国产九九在线观看播放 | 婷婷毛片 | 日本精品一区二区三区在线 | ww亚洲ww在线观看国产 | 福利在线观看 | 久久社区视频 | 亚洲国产精品自产拍在线播放 | 欧美综合一区二区三区 | 中文字幕在线激情日韩一区 | 国产精品777 | 精品国产高清a毛片无毒不卡 | 97精品久久天干天天蜜 | 久久精品国产一区二区三区不卡 | 亚洲一级生活片 | 999久久久国产 | 国产a自拍 | 国产亚洲精品sese在线播放 | 九九热最新网址 |