小夥伴們大家好，今天介紹BloomFilter布隆過濾器。相信大家對BloomFilter一定不陌生，但是可能隻是知道名字，并不知道原理而且沒有動手去放到自己的項目中。
今天帶大家一套打通BloomFilter，如有補充，歡迎評論或者私信！！
1. 案例
現在有50億個使用者id，給你10萬個使用者id，如何判斷這10萬個使用者id是否存在于這50億個中。
此時，或許你有兩種解決方案
- 資料庫查詢：用資料庫查詢要想實作這麼多資料快速查詢有點困難
- 資料預存放到記憶體中：50億*8位元組大約40G，記憶體占用太大了
那咋實作呢？
2. 什麼是BloomFilter
布隆過濾器（英語：Bloom Filter）是 1970 年由布隆提出的。
它實際上是一個很長的二進制數組+一系列随機hash算法映射函數，主要用于判斷一個元素是否在集合中。
通常我們會遇到很多要判斷一個元素是否在某個集合中的業務場景，一般想到的是将集合中所有元素儲存起來，然後通過比較确定。 連結清單、樹、散清單（又叫哈希表，Hash table）等等資料結構都是這種思路。
但是随着集合中元素的增加，我們需要的存儲空間也會呈現線性增長，最終達到瓶頸。同時檢索速度也越來越慢，上述三種結構的檢索時間複雜度分别為O(n),O(logn),O(1)。這個時候，布隆過濾器（Bloom Filter）就應運而生。
一句話就是由一個初值都為0的bit數組和多個哈希函數構成，用來快速判斷某一個資料是否存在。本質就是判斷具體資料存不存在一個大的集合中。
布隆過濾器是一種類似set的資料結構，隻是統計結果不太準确。
3. 在centos7下布隆過濾器2種安裝方式
3.1 采用docker安裝RedisBloom，推薦
Redis 在 4.0 之後有了插件功能（Module），可以使用外部的擴充功能， 可以使用 RedisBloom 作為 Redis 布隆過濾器插件。
docker run -p 6379:6379 --name=redis6379bloom -d redislabs/rebloom
docker exec -it redis6379bloom /bin/bash
redis-cli
3.2 編譯安裝
3.3 布隆過濾器常用操作指令
bf.reserve filter 0.01 100
bf.add filter v11
bf.exists filter v11
bf.exists filter v12
複制代碼 - bf.reserve key error_rate的值 initial_size 的值
error_rate：誤判率
initial_size：數組初始大小
- bf.add key 值
- bf.exists key 值
- bf.madd 一次添加多個元素
- bf.mexists 一次查詢多個元素是否存在
4. BloomFilter特點
- 高效的插入和查詢，占用空間少，傳回的結果是不确定性的
- 一個元素如果判斷結果為存在的時候元素不一定存在，但是判斷結果為不存在的時候則一定不存在
- 布隆過濾器可以添加元素，但是不能删除元素。因為删掉元素會導緻誤判率增加
- 誤判隻會發生在過濾器沒有添加過的元素，對于添加過的元素不會發生誤判
有，可能有
無，一定無，可以保證的是，如果布隆過濾器判斷一個元素不在一個集合中，那這個元素一定不會在集合中
5. BloomFilter原理
5.1 Java中的傳統hash
哈希函數的概念是：将任意大小的輸入資料轉換成特定大小的輸出資料的函數，轉換後的資料稱為哈希值或哈希編碼，也叫散列值
如果兩個散列值是不相同的（根據同一函數）那麼這兩個散列值的原始輸入也是不相同的。 這個特性是散列函數具有确定性的結果，具有這種性質的散列函數稱為單向散列函數。
散列函數的輸入和輸出不是唯一對應關系的，如果兩個散列值相同，兩個輸入值很可能是相同的，但也可能不同， 這種情況稱為“散列碰撞（collision）”。
用 hash表存儲大資料量時，空間效率還是很低，當隻有一個 hash 函數時，還很容易發生哈希碰撞。
5.2 Java中的哈希碰撞執行個體
案例一：
案例二：
5.3 初探布隆過濾器實作原理和資料結構
布隆過濾器(Bloom Filter) 是一種專門用來解決去重問題的進階資料結構。
實質就是一個大型位數組和幾個不同的無偏hash函數(無偏表示分布均勻)。由一個初值都為零的bit數組和多個個哈希函數構成，用來快速判斷某個資料是否存在。
但是跟 HyperLogLog(juejin.cn/post/719106…) 一樣，它也一樣有那麼一點點不精确，也存在一定的誤判機率。
添加key時
使用多個hash函數對key進行hash運算得到一個整數索引值，對位數組長度進行取模運算得到一個位置， 每個hash函數都會得到一個不同的位置，将這幾個位置都置1就完成了add操作。
查詢key時
隻要有其中一位是零就表示這個key不存在，但如果都是1，則不一定存在對應的key。
結論：
有，是可能有
無，是肯定無
5.4 進一步探索
當有變量被加入集合時，通過N個映射函數将這個變量映射成位圖中的N個點， 把它們置為 1（假定有兩個變量都通過 3 個映射函數）。
查詢某個變量的時候我們隻要看看這些點是不是都是 1， 就可以大機率知道集合中有沒有它了。
如果這些點，有任何一個為零則被查詢變量一定不在，
如果都是 1，則被查詢變量很可能存在，
為什麼說是可能存在，而不是一定存在呢？那是因為映射函數本身就是散列函數，散列函數是會有碰撞的。
5.5 布隆過濾器三步驟
- 初始化
布隆過濾器本質上是由長度為 m 的位向量或位清單（僅包含 0 或 1 位值的清單）組成，最初所有的值均設定為 0。
- 添加
當我們向布隆過濾器中添加資料時，為了盡量位址不沖突，會使用多個 hash 函數對 key 進行運算，算得一個下标索引值，然後對位數組長度進行取模運算得到一個位置，每個 hash 函數都會算得一個不同的位置。
再把位數組的這幾個位置都置為 1 就完成了 add 操作。
例如，我們添加一個字元串wmyskxz
- 判斷是否存在
向布隆過濾器查詢某個key是否存在時，先把這個 key 通過相同的多個 hash 函數進行運算，檢視對應的位置是否都為 1，
隻要有一個位為 0，那麼說明布隆過濾器中這個 key 不存在；
如果這幾個位置全都是 1，那麼說明極有可能存在；
因為這些位置的 1 可能是因為其他的 key 存在導緻的，也就是前面說過的hash沖突。
就比如我們在 add 了字元串wmyskxz資料之後，很明顯下面1/3/5 這幾個位置的 1 是因為第一次添加的 wmyskxz 而導緻的； 此時我們查詢一個沒添加過的不存在的字元串inexistent-key，它有可能計算後坑位也是1/3/5 ，這就是誤判了......
5.6 關于BloomFilter的誤判率，為什麼不要删除？
布隆過濾器的誤判是指多個輸入經過哈希之後在相同的bit位置1了，這樣就無法判斷究竟是哪個輸入産生的， 是以誤判的根源在于相同的 bit 位被多次映射且置 1。
這種情況也造成了布隆過濾器的删除問題，因為布隆過濾器的每一個 bit 并不是獨占的，很有可能多個元素共享了某一位。
如果我們直接删除這一位的話，會影響其他的元素。
5.7 BloomFilter小總結
- 存在則很可能存在，不存在則一定不存在。
- 使用時最好不要讓實際元素數量遠大于初始化數量
- 當實際元素數量超過初始化數量時，應該對布隆過濾器進行重建， 重新配置設定一個 size 更大的過濾器，再将所有的曆史元素批量 add 進行
6. BloomFilter優缺點
優點：高效的插入和删除，占用空間很少
缺點：
- 不能删除元素，因為删除元素會導緻誤判率增大，因為hash沖突，bit數組中同一個位置存放的資料可能是多個key進行hash計算後共有的
- 存在誤判：不同的資料可能出來相同的值
7. 布谷鳥過濾器
為了解決布隆過濾器不能删除元素的問題，布谷鳥過濾器橫空出世。論文《Cuckoo Filter：Better Than Bloom》
作者将布谷鳥過濾器和布隆過濾器進行了深入的對比。相比布谷鳥過濾器而言布隆過濾器有以下不足： 查詢性能弱、空間利用效率低、不支援反向操作（删除）以及不支援計數。
8. 實戰
- 資料庫防止穿庫。 Google Bigtable，HBase 和 Cassandra 以及 Postgresql 使用BloomFilter來減少不存在的行或列的磁盤查找。避免代價高昂的磁盤查找會大大提高資料庫查詢操作的性能。
- 業務場景中判斷使用者是否閱讀過某視訊或文章，比如抖音或頭條，當然會導緻一定的誤判，但不會讓使用者看到重複的内容。
- 緩存當機、緩存擊穿場景，一般判斷使用者是否在緩存中，如果在則直接傳回結果，不在則查詢db，如果來一波冷資料，會導緻緩存大量擊穿，造成雪崩效應，這時候可以用布隆過濾器當緩存的索引，隻有在布隆過濾器中，才去查詢緩存，如果沒查詢到，則穿透到db。如果不在布隆器中，則直接傳回。
- WEB攔截器，如果相同請求則攔截，防止重複被攻擊。使用者第一次請求，将請求參數放入布隆過濾器中，當第二次請求時，先判斷請求參數是否被布隆過濾器命中。可以提高緩存命中率。Squid 網頁代理緩存伺服器在 cache digests 中就使用了布隆過濾器。Google Chrome浏覽器使用了布隆過濾器加速安全浏覽服務
- Venti 文檔存儲系統也采用布隆過濾器來檢測先前存儲的資料。
- SPIN 模型檢測器也使用布隆過濾器在大規模驗證問題時跟蹤可達狀态空間。
由于BloomFilter最常用的地方适用于解決緩存穿透，是以實戰内容放到緩存穿透篇講述。
以上就是BloomFilter的内容啦，感謝小夥伴的觀看，有任何建議都可以聯系我！！
作者：JavaLyHn
連結：https://juejin.cn/post/7191378085894160442