[TOC] > **RedisBloom** 為 Redis 添加了四種概率數據結構：可擴展的**布隆過濾器**、**布谷鳥過濾器**、**count-min sketch**和**top-k**。 > **布隆過濾器**和**布谷鳥過濾器**用于高度確定地確定一個元素是否是集合的成員。 > 官網 https://redis.io/docs/stack/bloom ## 安裝 RedisBloom 模塊 ~~~sh git clone --recursive https://github.com/RedisBloom/RedisBloom.git cd RedisBloom make setup make ~~~ ## **布隆過濾器** * 由一個初值都為零的 bit 數組和多個哈希函數構成，用來快速判斷某個數據是否存在 * 本質就是判斷具體數據存不存在一個大的集合中 * 布隆過濾器類似 `set` 的數據結構，只是統計結構不太準確 ### 應用場景 * 垃圾郵件過濾 * 文字處理中的錯誤單詞檢測 * 網絡爬蟲重復URL檢測 * 會員抽獎 * 判斷一個元素在億級數據中是否存在 * 緩存穿透 ### 原理 布隆過濾器(Bloom Filter) 是一種專門用來解決去重問題的高級數據結構。?實質就是一個大型**位數組和幾個不同的無偏hash函數 **(無偏表示分布均勻)。**由一個初值都為零的bit數組和多個個哈希函數構成**，用來快速判斷某個數據是否存在 。但是跟 HyperLogLog 一樣，它也一樣有那么一點點不精確，也存在一定的誤判概率。 ### **添加key** 使用多個 hash 函數對 key 進行 hash 運算得到一個整數索引值，對位數組長度進行取模運算得到一個位置，每個hash 函數都會得到一個不同的位置，將這幾個位置都置 1 就完成了 add 操作。 ### **查詢key** 先把這個 key 通過相同的多個 hash 函數進行運算，查看對應位置不都為 1 如果這些點，**有任何一個為 0 則被查詢變量一定不在，如果都是 1，則被查詢變量很 可能存在** **為什么說是可能存在，而不是一定存在呢？**`那是因為映射函數本身就是散列函數，散列函數是會有碰撞的。`  ### 誤判率，為什么不能刪除元素 誤判是指多個輸入經過 hash 之后在相同 bit 位置為1 了，這樣就無法判斷究竟是哪個輸入所產生的，**誤判的根源在于相同的 bit 位被多次映射且置 1。 ** **布隆過濾器的每一個 bit 并不是獨占的，很有可能多個元素共享了某一位**如果刪除一位，或影響其他元素。 ### 基本命令 ~~~sh 127.0.0.1:6379> bf.reserve bf 0.1 10 # 創建一個空的布隆過濾器 錯誤率0.1 容量10（超出10以后性能下降)。錯誤率越小，需要的空間越大 OK 127.0.0.1:6379> bf.add bf a # 添加項 (integer) 1 127.0.0.1:6379> bf.add bf a (integer) 0 127.0.0.1:6379> bf.madd bf b c d e # 添加多個項 1) (integer) 1 2) (integer) 1 3) (integer) 1 4) (integer) 1 127.0.0.1:6379> bf.madd bf e f g h i j 1) (integer) 0 2) (integer) 1 3) (integer) 1 4) (integer) 1 5) (integer) 1 6) (integer) 1 127.0.0.1:6379> bf.exists bf c # 項是否存在 1：可能存在、0：一定不存在 (integer) 1 127.0.0.1:6379> bf.exists bf q (integer) 0 127.0.0.1:6379> bf.mexists bf a d h l 1) (integer) 1 2) (integer) 1 3) (integer) 1 4) (integer) 0 ~~~ 更多命令：https://redis.io/commands/?name=bf. ### 優缺點 #### **優點：** * 高效得插入和查詢，占用空間少 #### **缺點：** * 不能刪除元素 * 存在誤判，不同的數據可能出來相同的hash值 ## 杜鵑過濾器 **解決了布隆過濾器不能刪除元素的問題** ~~~sh 127.0.0.1:6379> cf.reserve cf 10 # 創建一個具有初始容量（10個項目）的空杜鵑過濾器 OK 127.0.0.1:6379> cf.add cf a (integer) 1 127.0.0.1:6379> cf.exists cf a (integer) 1 127.0.0.1:6379> cf.add cf b (integer) 1 127.0.0.1:6379> cf.add cf c (integer) 1 127.0.0.1:6379> cf.del cf a # 刪除過濾器中項目 (integer) 1 ~~~ 更多命令：https://redis.io/commands/?name=cf.