go語言布隆過濾器,go 布隆過濾器

BloomFilter詳解（布隆過濾器）

從上式中可以看出，當(dāng)m增大或n減小時(shí)，都會使得誤判率減小，這也符合直覺。

創(chuàng)新新互聯(lián)，憑借10多年的成都做網(wǎng)站、網(wǎng)站制作、成都外貿(mào)網(wǎng)站建設(shè)經(jīng)驗(yàn)，本著真心·誠心服務(wù)的企業(yè)理念服務(wù)于成都中小企業(yè)設(shè)計(jì)網(wǎng)站有上千余家案例。做網(wǎng)站建設(shè)，選成都創(chuàng)新互聯(lián)。

現(xiàn)在計(jì)算對于給定的m和n，k為何值時(shí)可以使得誤判率最低。設(shè)誤判率為k的函數(shù)為：

這說明了若想保持某固定誤判率不變，布隆過濾器的bit數(shù)m與被add的元素?cái)?shù)n應(yīng)該是線性同步增加的。

三 如何設(shè)計(jì)bloomfilter

此概率為某bit位在插入n個(gè)元素后未被置位的概率。因此，想保持錯(cuò)誤率低，布隆過濾器的空間使用率需為50%。

bloomfilter的各個(gè)參數(shù)的錯(cuò)誤率

公式推完了，大家可以看看，里面的數(shù)學(xué)公式基本用到了指數(shù)函數(shù) 對數(shù)函數(shù) 微積分求導(dǎo)法則 概率論的知識，大家可以補(bǔ)充看下課本。

個(gè)人介紹：杜寶坤，京東聯(lián)邦學(xué)習(xí)從0到1構(gòu)建者，帶領(lǐng)團(tuán)隊(duì)構(gòu)建了京東的聯(lián)邦學(xué)習(xí)解決方案，實(shí)現(xiàn)了電商營銷領(lǐng)域支持超大規(guī)模的工業(yè)化聯(lián)邦學(xué)習(xí)解決方案，支持超大規(guī)模樣本PSI隱私對齊、安全的樹模型與神經(jīng)網(wǎng)絡(luò)模型等眾多模型支持，并且實(shí)現(xiàn)了廣告?zhèn)鹊葮I(yè)務(wù)領(lǐng)域的落地，開創(chuàng)了新的業(yè)務(wù)增長點(diǎn)，產(chǎn)生了顯著的業(yè)務(wù)經(jīng)濟(jì)效益。

個(gè)人喜歡研究技術(shù)?；趶娜溌匪伎寂c決策技術(shù)規(guī)劃的考量，研究的領(lǐng)域比較多，從架構(gòu)、數(shù)據(jù)到算法與算法框架均有涉及。歡迎喜歡技術(shù)的同學(xué)和我交流，郵箱： baokun06@163.com

【golang】海量數(shù)據(jù)去重-布隆過濾器

在做域名爆破中，遇到了把一個(gè)300G的子域名json文件進(jìn)行去重，一開始是考慮使用字典進(jìn)行去重，但是數(shù)據(jù)量大了，會造成內(nèi)存泄露?？淳W(wǎng)上資料介紹了一種方案，就是使用布隆過濾器。

布隆過濾器是一種數(shù)據(jù)結(jié)構(gòu)，概率型數(shù)據(jù)結(jié)構(gòu)，特定是高效插入和查詢，可以用來告訴你“某一值一定不存在或者kennel存在”。

相比于傳統(tǒng)的map、set等數(shù)據(jù)結(jié)構(gòu)，占用空間更少，但其返回結(jié)果是概率型的，不確定。

布隆過濾器內(nèi)部維護(hù)一個(gè)bitArray(位數(shù)組)，開始所有數(shù)據(jù)為0，當(dāng)一個(gè)元素過來時(shí)，能過多個(gè)哈希函數(shù)（hash1、hash2、hash3）計(jì)算不同的hash值，并通過hash值找到bitArray的下標(biāo)，將里面的值改為由0變?yōu)?。布隆過濾器有一個(gè)誤判率，誤判率越低，數(shù)組越長，所在空間越大，誤判率越高，數(shù)組越小，所占空間越小。

這里貼上一個(gè)技術(shù)大牛的博客地址，里面對布隆過濾器用法以及在redis里面處理緩存穿透問題的詳細(xì)介紹。

布隆過濾器

布隆過濾器 （英語：Bloom Filter）是 1970 年由布隆提出的。它實(shí)際上是一個(gè)很長的二進(jìn)制向量和一系列隨機(jī)映射函數(shù)。主要用于判斷一個(gè)元素是否在一個(gè)集合中。

通常我們會遇到很多要判斷一個(gè)元素是否在某個(gè)集合中的業(yè)務(wù)場景，一般想到的是將集合中所有元素保存起來，然后通過比較確定。鏈表、樹、散列表（又叫哈希表，Hash table）等等數(shù)據(jù)結(jié)構(gòu)都是這種思路。但是隨著集合中元素的增加，我們需要的存儲空間也會呈現(xiàn)線性增長，最終達(dá)到瓶頸。同時(shí)檢索速度也越來越慢，上述三種結(jié)構(gòu)的檢索時(shí)間復(fù)雜度分別為，，。

這個(gè)時(shí)候，布隆過濾器（Bloom Filter）就應(yīng)運(yùn)而生。

了解布隆過濾器原理之前，先回顧下 Hash 函數(shù)原理。

哈希函數(shù)的概念是：將任意大小的輸入數(shù)據(jù)轉(zhuǎn)換成特定大小的輸出數(shù)據(jù)的函數(shù)，轉(zhuǎn)換后的數(shù)據(jù)稱為哈希值或哈希編碼，也叫散列值。下面是一幅示意圖：

所有散列函數(shù)都有如下基本特性：

但是用 hash表存儲大數(shù)據(jù)量時(shí)，空間效率還是很低，當(dāng)只有一個(gè) hash 函數(shù)時(shí)，還很容易發(fā)生哈希碰撞。

BloomFilter 是由一個(gè)固定大小的二進(jìn)制向量或者位圖（bitmap）和一系列映射函數(shù)組成的。

在初始狀態(tài)時(shí)，對于長度為 m 的位數(shù)組，它的所有位都被置為0，如下圖所示：

[圖片上傳失敗...(image-303c04-1595324887187)]

當(dāng)有變量被加入集合時(shí)，通過 K 個(gè)映射函數(shù)將這個(gè)變量映射成位圖中的 K 個(gè)點(diǎn)，把它們置為 1（假定有兩個(gè)變量都通過 3 個(gè)映射函數(shù)）。

查詢某個(gè)變量的時(shí)候我們只要看看這些點(diǎn)是不是都是 1 就可以大概率知道集合中有沒有它了

為什么說是可能存在，而不是一定存在呢？那是因?yàn)橛成浜瘮?shù)本身就是散列函數(shù)，散列函數(shù)是會有碰撞的。

布隆過濾器的誤判是指多個(gè)輸入經(jīng)過哈希之后在相同的bit位置1了，這樣就無法判斷究竟是哪個(gè)輸入產(chǎn)生的，因此誤判的根源在于相同的 bit 位被多次映射且置 1。

這種情況也造成了布隆過濾器的刪除問題，因?yàn)椴悸∵^濾器的每一個(gè) bit 并不是獨(dú)占的，很有可能多個(gè)元素共享了某一位。如果我們直接刪除這一位的話，會影響其他的元素。(比如上圖中的第 3 位)

相比于其它的數(shù)據(jù)結(jié)構(gòu)，布隆過濾器在空間和時(shí)間方面都有巨大的優(yōu)勢。布隆過濾器存儲空間和插入/查詢時(shí)間都是常數(shù) ，另外，散列函數(shù)相互之間沒有關(guān)系，方便由硬件并行實(shí)現(xiàn)。布隆過濾器不需要存儲元素本身，在某些對保密要求非常嚴(yán)格的場合有優(yōu)勢。

布隆過濾器可以表示全集，其它任何數(shù)據(jù)結(jié)構(gòu)都不能；

但是布隆過濾器的缺點(diǎn)和優(yōu)點(diǎn)一樣明顯。誤算率是其中之一。隨著存入的元素?cái)?shù)量增加，誤算率隨之增加。但是如果元素?cái)?shù)量太少，則使用散列表足矣。

另外，一般情況下不能從布隆過濾器中刪除元素。我們很容易想到把位數(shù)組變成整數(shù)數(shù)組，每插入一個(gè)元素相應(yīng)的計(jì)數(shù)器加 1, 這樣刪除元素時(shí)將計(jì)數(shù)器減掉就可以了。然而要保證安全地刪除元素并非如此簡單。首先我們必須保證刪除的元素的確在布隆過濾器里面。這一點(diǎn)單憑這個(gè)過濾器是無法保證的。另外計(jì)數(shù)器回繞也會造成問題。

在降低誤算率方面，有不少工作，使得出現(xiàn)了很多布隆過濾器的變種。

在程序的世界中，布隆過濾器是程序員的一把利器，利用它可以快速地解決項(xiàng)目中一些比較棘手的問題。

如網(wǎng)頁 URL 去重、垃圾郵件識別、大集合中重復(fù)元素的判斷和緩存穿透等問題。

布隆過濾器的典型應(yīng)用有：

知道了布隆過濾器的原理和使用場景，我們可以自己實(shí)現(xiàn)一個(gè)簡單的布隆過濾器

分布式環(huán)境中，布隆過濾器肯定還需要考慮是可以共享的資源，這時(shí)候我們會想到 Redis，是的，Redis 也實(shí)現(xiàn)了布隆過濾器。

當(dāng)然我們也可以把布隆過濾器通過 bloomFilter.writeTo() 寫入一個(gè)文件，放入OSS、S3這類對象存儲中。

Redis 提供的 bitMap 可以實(shí)現(xiàn)布隆過濾器，但是需要自己設(shè)計(jì)映射函數(shù)和一些細(xì)節(jié)，這和我們自定義沒啥區(qū)別。

Redis 官方提供的布隆過濾器到了 Redis 4.0 提供了插件功能之后才正式登場。布隆過濾器作為一個(gè)插件加載到 Redis Server 中，給 Redis 提供了強(qiáng)大的布隆去重功能。

在已安裝 Redis 的前提下，安裝 RedisBloom，有兩種方式

直接編譯進(jìn)行安裝

使用Docker進(jìn)行安裝

使用

布隆過濾器基本指令：

我們只有這幾個(gè)參數(shù)，肯定不會有誤判，當(dāng)元素逐漸增多時(shí)，就會有一定的誤判了，這里就不做這個(gè)實(shí)驗(yàn)了。

上面使用的布隆過濾器只是默認(rèn)參數(shù)的布隆過濾器，它在我們第一次 add 的時(shí)候自動(dòng)創(chuàng)建。

Redis 還提供了自定義參數(shù)的布隆過濾器，bf.reserve 過濾器名 error_rate initial_size

但是這個(gè)操作需要在 add 之前顯式創(chuàng)建。如果對應(yīng)的 key 已經(jīng)存在，bf.reserve 會報(bào)錯(cuò)

我是一名 Javaer，肯定還要用 Java 來實(shí)現(xiàn)的，Java 的 Redis 客戶端比較多，有些還沒有提供指令擴(kuò)展機(jī)制，筆者已知的 Redisson 和 lettuce 是可以使用布隆過濾器的，我們這里用 Redisson

為了解決布隆過濾器不能刪除元素的問題，布谷鳥過濾器橫空出世。論文《Cuckoo Filter：Better Than Bloom》作者將布谷鳥過濾器和布隆過濾器進(jìn)行了深入的對比。相比布谷鳥過濾器而言布隆過濾器有以下不足：查詢性能弱、空間利用效率低、不支持反向操作（刪除）以及不支持計(jì)數(shù)。

文章題目：go語言布隆過濾器,go 布隆過濾器
網(wǎng)站路徑：http://www.muchs.cn/article26/hcphcg.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供品牌網(wǎng)站建設(shè)、網(wǎng)站策劃、外貿(mào)建站、網(wǎng)站改版、響應(yīng)式網(wǎng)站、網(wǎng)站導(dǎo)航

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)