布隆過濾器 （英語：Bloom Filter）是 1970 年由布隆提出的。它實際上是一個很長的二進制向量和一系列隨機映射函數(shù)。主要用于判斷一個元素是否在一個集合中。
創(chuàng)新互聯(lián)公司為企業(yè)級客戶提高一站式互聯(lián)網(wǎng)+設計服務，主要包括成都網(wǎng)站設計、成都做網(wǎng)站、app軟件開發(fā)、小程序開發(fā)、宣傳片制作、LOGO設計等，幫助客戶快速提升營銷能力和企業(yè)形象，創(chuàng)新互聯(lián)各部門都有經(jīng)驗豐富的經(jīng)驗，可以確保每一個作品的質量和創(chuàng)作周期，同時每年都有很多新員工加入，為我們帶來大量新的創(chuàng)意。
通常我們會遇到很多要判斷一個元素是否在某個集合中的業(yè)務場景，一般想到的是將集合中所有元素保存起來，然后通過比較確定。鏈表、樹源迅、散列表（又叫哈希表，Hash table）等等數(shù)據(jù)結構都是這種思路。但是隨著集合中元素的增加，我們需要的存儲空間也會呈現(xiàn)線性增長，最終達到瓶頸。同時檢索速度也越來越慢，上述三種結構的檢索時間復雜度分別為 ， ， 。
這個時候，布隆過濾器（Bloom Filter）就應運而生。
了解布隆過濾器原理之前，先回顧下 Hash 函數(shù)原理。
哈希函數(shù)的概念是：將任意大小的輸入數(shù)據(jù)轉換成特定大小的輸出數(shù)據(jù)的函數(shù)，轉換后的數(shù)據(jù)稱為哈希值或哈希編碼，也叫散列值。下面是一幅示意圖：
所有散列函數(shù)都有如下基本特性：
但是用 hash表存儲大數(shù)據(jù)量時，空間效率還是很低，當只有一個 hash 函數(shù)時，還很容易發(fā)生哈希碰撞。
BloomFilter 是由一個固定大小的二進制向量或者位圖（bitmap）和一系列映射函數(shù)組成的。
在初始狀態(tài)時，對于長度為 m 的位數(shù)組，它的所有位都被置為0，如下圖所示：
當有變量被加入集合時，通過 K 個映射函數(shù)將這個變量映射成位圖中的 K 個點，把它們置為 1（假定有兩個變量都通過 3 個映射函數(shù)）。
查詢某個變量的時候我們只要看看這些點是不是都是 1 就可以大概率知道集合中有沒有它了
為什么說是可能存在，而不是一定存在呢？那是因為映射函數(shù)本身就是散列函數(shù)，散列函數(shù)是會有碰撞的。
布隆頃凳過濾器的誤判是指多個輸入經(jīng)過哈希之后在相同的bit位置1了，這樣就無法判斷究竟是哪個輸入產(chǎn)生的，因此誤判的根源在于相同的 bit 位被多次映射且置 1。
這種情況也造成了布隆過濾器的刪除問題，因為布隆過濾器的每一個 bit 并不是獨占的，很有可能多個元素共享了某一位。如果我們直接刪除這一位的話，會影響其他的元素。(比如上圖中的第 3 位)
相比于其它的數(shù)據(jù)結構，布隆過濾器在空間和時間方面都有巨大的優(yōu)勢。布隆過濾器存儲空間和插入/查詢時間都是常數(shù) ，另外，散列函數(shù)相互之間沒有關系，方便由硬件并行實現(xiàn)。布隆過濾器不需要存儲元素本身，在某些對保密要求非常嚴格的場合有優(yōu)勢。
布隆過濾器可以表示全集，其它任何數(shù)據(jù)結構都不能；
但是布隆過濾器的缺點和優(yōu)點一樣明顯。誤算率是其中之一。隨著存入的元素數(shù)量增加，誤算率隨之增加。但是如果元素數(shù)量太少，則使用散列表足矣。
另外，一般情況下不能從布隆過濾器中刪除元素。我們很容易想到把位數(shù)組變成整數(shù)數(shù)組，每插入一個元素相應的計數(shù)器雹乎此加 1, 這樣刪除元素時將計數(shù)器減掉就可以了。然而要保證安全地刪除元素并非如此簡單。首先我們必須保證刪除的元素的確在布隆過濾器里面。這一點單憑這個過濾器是無法保證的。另外計數(shù)器回繞也會造成問題。
在降低誤算率方面，有不少工作，使得出現(xiàn)了很多布隆過濾器的變種。
在程序的世界中，布隆過濾器是程序員的一把利器，利用它可以快速地解決項目中一些比較棘手的問題。
如網(wǎng)頁 URL 去重、垃圾郵件識別、大集合中重復元素的判斷和緩存穿透等問題。
布隆過濾器的典型應用有：
知道了布隆過濾去的原理和使用場景，我們可以自己實現(xiàn)一個簡單的布隆過濾器
分布式環(huán)境中，布隆過濾器肯定還需要考慮是可以共享的資源，這時候我們會想到 Redis，是的，Redis 也實現(xiàn)了布隆過濾器。
當然我們也可以把布隆過濾器通過 bloomFilter.writeTo() 寫入一個文件，放入OSS、S3這類對象存儲中。
Redis 提供的 bitMap 可以實現(xiàn)布隆過濾器，但是需要自己設計映射函數(shù)和一些細節(jié)，這和我們自定義沒啥區(qū)別。
Redis 官方提供的布隆過濾器到了 Redis 4.0 提供了插件功能之后才正式登場。布隆過濾器作為一個插件加載到 Redis Server 中，給 Redis 提供了強大的布隆去重功能。
在已安裝 Redis 的前提下，安裝 RedisBloom，有兩種方式
直接編譯進行安裝
使用Docker進行安裝
使用
布隆過濾器基本指令：
我們只有這幾個參數(shù)，肯定不會有誤判，當元素逐漸增多時，就會有一定的誤判了，這里就不做這個實驗了。
上面使用的布隆過濾器只是默認參數(shù)的布隆過濾器，它在我們第一次 add 的時候自動創(chuàng)建。
Redis 還提供了自定義參數(shù)的布隆過濾器， bf.reserve 過濾器名 error_rate initial_size
但是這個操作需要在 add 之前顯式創(chuàng)建。如果對應的 key 已經(jīng)存在，bf.reserve 會報錯
我是一名 Javaer，肯定還要用 Java 來實現(xiàn)的，Java 的 Redis 客戶端比較多，有些還沒有提供指令擴展機制，筆者已知的 Redisson 和 lettuce 是可以使用布隆過濾器的，我們這里用 Redisson
為了解決布隆過濾器不能刪除元素的問題，布谷鳥過濾器橫空出世。論文《Cuckoo Filter：Better Than Bloom》作者將布谷鳥過濾器和布隆過濾器進行了深入的對比。相比布谷鳥過濾器而言布隆過濾器有以下不足：查詢性能弱、空間利用效率低、不支持反向操作（刪除）以及不支持計數(shù)。
由于使用較少，暫不深入。
在上篇【鏈接】中，我們借助 Java 的 BitSet 源碼嘗試著理解了下 BitMap 算法，但是有一個很致命的劣勢沒有解決，那就是很尷尬的 數(shù)據(jù)碰撞問題 。
啥意思呢，再次解釋一下下，BitMap 中我們只是很簡單地初始化了一個 Long 數(shù)組，然后使用一個個小小的 bit 位來表示一個數(shù)據(jù)的存在與否，但是其中必然會面對 哈希碰撞 問題。
我們畫張簡圖來回顧下 BitMap 算法。
如上圖所示，hash function 均為 f1，數(shù)據(jù) A 和 D 指向的位是 1 ，所以肯定是存在的，而 B 和 C 指向的都是同一個位，所以哈希碰撞就是這樣很容易地產(chǎn)生了。
即：位上無元素則表示該數(shù)據(jù)肯定不存在，位上有元素則只能表示該數(shù)據(jù) 可能存在 。
有弊端總有解決之道，此處正好引入本文主要介紹的一種算法： 布隆過濾器 ，英文名為 Bloom Filter ，下文簡稱 BF 算法。
同樣，我們還是先畫一張簡圖來直觀地認識下 BF 算法。
由上圖我們可以看出，此時的 A、B、C、D 四個數(shù)據(jù)各自經(jīng)過 f1 和禪隱 f2 方法進行兩次 hash 算法，然后分別指向位上面，只有當 f1 和 f2 指向的位上面都為 1 時，才會標記為存在。
小結：BF 算法雖然在一定程度上減少了 BitMap 算法中的哈希碰撞，但是終言之，只是減少而已，沒法完全避免，就像上文舉的案例2一樣。
通過上面的圖，其實很容易看出，上圖中 hash function 的數(shù)量是 2，假如我們計算 3 次呢？或者 4 次甚至更多呢？誠然昌念這可以更進一步避免數(shù)據(jù)的碰撞問題，但是太多的話卻適得其反。
所以介紹優(yōu)化之前我們先小結下 BF 算法的劣勢，因為優(yōu)化都是基于某些劣勢來進行的：
所以，針對上面的兩個點，我們逐個來突破下：
1、關于誤判率
BF 算法優(yōu)劣的影響因素，其實很容易就可以聯(lián)想到，一個是根據(jù)插入的數(shù)據(jù)總量（n）來計算出最合適的位數(shù)組的大小（m）和 hash 函數(shù)的個數(shù)（k），還有一個便是最優(yōu)的 誤判率 （使用 P(error) 表示）的選擇問題。
比如：我們假設 P 為 0.01，此時最優(yōu)的 m 應大概是 n 的 13 倍，而 k，應大概為 8。
詳細的證明過程見下文。
2、關于元素刪除的需求
因為數(shù)據(jù)對應的位會牽動其它的數(shù)據(jù)，所以 BF 是不可以刪除位數(shù)據(jù)的，那么如果有這樣的需求呢？可以使用 couting Bloom Filter 來解決，大致思路就是使用一個 counter 數(shù)組來代替位數(shù)組。
什么意思呢？簡言之就是在原來的 BF 算法的位上面，不再是用簡單的 0 或 1 來表示了，而是存儲該位上面的數(shù)據(jù)總量，比如有兩個數(shù)據(jù)經(jīng)過 hash function 計算都有指向同一個位，則將該位標記為2，代表有兩個數(shù)據(jù)，當刪除其中一個數(shù)據(jù)時，只需要將該位上面的 2 調整為 1 即可，如此便不再影響其它數(shù)據(jù)的正確性。
BF 算法雖然有著一定的缺點（主要是誤判率），但是它的優(yōu)點更為突出，所以應用場景也是很廣的。
比如我們在爬蟲業(yè)務下，有很多的 URL，我們可以通過 BF 算法來判斷每個 URL 是否已經(jīng)被我們的爬蟲程序處理過。
再比如郵箱服務中垃圾郵件的過濾策略，由于垃圾郵件是海量的，我們不可能使用一個很完整的散列映射來標記每一個垃圾郵箱的地址，此處可以使用 BF 算法來標記，從而節(jié)約了容量。
另外，BF 算法在很多開源框架中也都有相應的實現(xiàn)，例如：
1、誤判概率的證明和計算
假設布隆過濾器中的hash function滿足simple uniform hashing假設：每個元素都等概率地hash到m個slot中的任何一個，與其它元素被hash到哪個slot無關。若m為bit數(shù)，則對某一特定bit位在一個元素由某特定hash function插入時沒有被置位為1的概率為：
現(xiàn)在考慮query階段，若對應某個待query元素的k bits全部置位為1，則可判定其在集合中。因此將某元素誤判的概率為：
從上式中可以看出，當m增大或n減小時，都會使得誤判率減小，這也符合直覺。 現(xiàn)在計算對于給定的m和n，k為何值時可以使得賀迅廳誤判率最低。設誤判率為k的函數(shù)為：
下面求最值：
這說明了若想保持某固定誤判率不變，則布隆過濾器的 位數(shù) m 與添加的元素數(shù) n 應該是線性同步增加的。
2、設計和應用布隆過濾器的方法
應用時首先要先由用戶決定添加的元素數(shù) n 和期望的誤差率 P。這也是一個設計完整的布隆過濾器需要用戶輸入的僅有的兩個參數(shù)，之后的所有參數(shù)將由系統(tǒng)計算，并由此建立布隆過濾器。
系統(tǒng)首先要計算需要的內存大小 m bits:
這里需要特別注意的是，9.6 bits/element 不僅包含了被置為1的 k 位，還把包含了沒有被置為1的一些位數(shù)。此時的
此概率為某 bit 位在插入 n 個元素后未被置位的概率。因此，想保持錯誤率低，布隆過濾器的空間使用率需為 50%。
代碼比較長，文章中暫不完整展示，更完整的代碼 demo 詳見【鏈接】。
下面列出了一小部分代碼塊，作用是根據(jù)插入的元素數(shù)量和過濾器容器的大小來計算實際的誤報率：
[TOC]
通過解決方案：
Java中如將數(shù)據(jù)存儲在內存中，最簡單的算法結構是HashMap。通過HashMap判斷key是否存在，來判斷數(shù)據(jù)是否存在。通過hash算法查找元素，時間復雜度基本是 O(1) （可能存在hash沖突后轉換成鏈表或紅黑樹的情況，時間復雜度的影響可以忽略）。
使用HashMap速度很快，存儲簡單，絕大部分場景可以使用。但是HashMap 占用的空間比較大 ：
為什么出現(xiàn)布隆過濾器：
舉例：
如1000萬個Integer存儲在內存中，占用空間為：4x32x10000000位，即1220兆。如布隆過濾器通過4字節(jié)存儲（布隆過濾器通過多次hash對數(shù)據(jù)計算后--幾次hash根據(jù)數(shù)據(jù)量指定，得到多個數(shù)據(jù)， 占用多個位 ），則占用空間為610M。比原有空間少一半。
個人覺得，此比較在字符等的比較中尤為有效銀嫌。
一個字符串多個字符，根據(jù)編碼方式，一個字符兩個或三個字節(jié)，如10個字符，字符串存儲占用20個字節(jié)，還有相關字符串相關的類信息的內存占用。
位存儲，根據(jù)數(shù)據(jù)量的大小，hash的位數(shù)，靈活計算。如4個字節(jié)，則是原h(huán)ashMap占用空間的五分之一。
（1）定義字節(jié)向量
先定義一個指定長度的字節(jié)數(shù)組（字節(jié)數(shù)組，數(shù)組內每個元素的值）。
如長度為8（一個字節(jié)大?。J所有元素值均為0，如下：
（2）計算哈希值
將要寫入過濾器的數(shù)據(jù)，根據(jù)一定數(shù)量的哈希函數(shù)，得到多個哈希值，再依次判斷每個哈希值對應的索引。
如使用3個哈希函數(shù)，計算得到3個哈希值，判定哈希值對應的字節(jié)向量為為1，3，7。
（3）更新字節(jié)向量
將計算出的字節(jié)向量的索引， 對應的字節(jié)向量中的元素值更高為1 （無論之前為0或者為1，均更改為1）。如下：
（1）計算哈希值
將要判斷過濾器中是否存在的數(shù)據(jù)，根據(jù)一定數(shù)量的哈希函數(shù)，得到多個哈希值，再依次判斷每個哈希值對應的索引。
如使用3個哈希函數(shù)，計算得到3個哈希值，判定哈希值對應的字節(jié)向量為為1，3，7。
注意：哈希函數(shù)的判斷方式和計算索引的方式，需和寫入數(shù)據(jù)時完全一致。
（2）判斷是否存在
如原字節(jié)數(shù)組中，對應1，3，7中存在的元素的值都為1。則判定為此元素 可能存在 ，但凡有一個元素的值不為1，則判定此元素 一定不存在 。
布隆過濾器，主要需實現(xiàn)的目標是， 在指定的數(shù)據(jù)個數(shù)范圍內，滿足誤判率在設定的范圍內 ，誤判率太高的話，無法起到過濾數(shù)據(jù)的情況，誤判率不能為0。
因此需要計算兩個數(shù)據(jù)來滿足 存儲數(shù)據(jù)的個數(shù) 和 誤判率 ：
使用布隆過濾器的決定性因素之一，就是此算法插入數(shù)據(jù)和查詢數(shù)據(jù)的速度必須非?？?。因此在對數(shù)據(jù)進行哈希運算的時候， 需選擇計算快的哈希算法 。
而且， 寫入數(shù)據(jù)以及查詢數(shù)據(jù)的哈希算法，順序和算法都需完全一致 。
待完善。。。。。
可以通過google的 guava ，在內存中輕松實現(xiàn)布隆過濾器。
無需手動計算滿足字節(jié)數(shù)組的長度和哈希個數(shù)，只需要輸入 擬輸入數(shù)據(jù)的個數(shù) 和 期望誤判率 即可。
不輸入期望誤判率的情況下，誤判率為0.03，即100個非范圍內的數(shù)據(jù)進行校驗時，約三個數(shù)據(jù)會判定茄搏芹為存在。
多次執(zhí)行，結果一致，根據(jù)結果判定：
內存的存儲存在局限性，可以使用redis中的bitMap來實現(xiàn)字節(jié)數(shù)組的存儲。
使用redis實現(xiàn)布隆過濾器。需要根據(jù)公式，手動計算字節(jié)數(shù)組的長度和哈希的個數(shù)。
實現(xiàn)過程，待完善。。。顫畢。。。
重慶分公司
重慶分公司
