文章已收錄Github精選，歡迎Star： https://github.com/yehongzhi
概念
布隆過濾器(BloomFilter)是由一個叫“布隆”的小夥子在1970年提出的，它是一個很長的二進制向量，主要用于判斷一個元素是否在一個集合中。
原理
在介紹原理之前，要先講一下Hash函數的概念。
我們在Java中的HashMap，HashSet其實也接觸過hashcode()這個函數，哈希函數是可以将任意大小的輸入資料轉換成特定大小的輸出資料的函數，轉換後的資料稱為哈希值。
哈希函數有以下特點：
- 如果根據同一個哈希函數得到的哈希值不同，那麼這兩個哈希值的原始輸入值肯定不同。
- 如果根據同一個哈希函數得到的兩個哈希值相等，兩個哈希值的原始輸入值有可能相等，有可能不相等。
布隆過濾器是由一個很長的二進制向量和一系列的哈希函數組成。那麼布隆過濾器是怎麼判斷一個元素是否在一個集合中的呢？
假設布隆過濾器的底層存儲結構是一個長度為16的位數組，初始狀态時，它的所有位置都設定為0。
當有變量添加到布隆過濾器中，通過K個映射函數将變量映射到位數組的K個點，并把這K個點的值設定為1(假設有三個映射函數)。
查詢某個變量是否存在的時候，我們隻需要通過同樣的K個映射函數，找到對應的K個點，判斷K個點上的值是否全都是1，如果全都是1則表示很可能存在，如果K個點上有任何一個是0則表示一定不存在。
特性
第一個問題，為什麼說全都是1的情況是很可能存在，而不是一定存在呢？
還記得前面說的哈希函數的特點，根據同一個哈希函數得到相同的哈希值，輸入值不一定相等。類似于Java中兩個對象的hashcode相等，但是不一定相等的道理。說白了，映射函數得到位數組上映射點全都是1，不一定是要查詢的這個變量之前存進來時設定的，也有可能是其他變量映射的點。
是以這裡引出了布隆過濾器的其中一個特點，存在一定的誤判。
第二個問題，布隆過濾器能不能删除元素呢？
答案是不能的。因為在位數組上的同一個點有可能有多個輸入值映射，如果删除了會影響布隆過濾器裡其他元素的判斷結果。
如上圖，如果删除obj1，把4,7,15置為0，那麼判斷obj2是否存在時就會導緻因為映射點7是0，結果判斷obj2是不存在的，結果出錯。
這是第二個特點，不能删除布隆過濾器裡的元素。
優缺點
優點：
- 在空間和時間方面，都有着巨大的優勢。因為不是存完整的資料，是一個二進制向量，能節省大量的記憶體空間，時間複雜度方面，是根據映射函數查詢，假設有K個映射函數，那麼時間複雜度就是O(K)。
- 因為存的不是元素本身，而是二進制向量，是以在一些對保密性要求嚴格的場景有一定優勢。
缺點：
- 存在一定的誤判。存進布隆過濾器裡的元素越多，誤判率越高。
- 不能删除布隆過濾器裡的元素。随着使用的時間越來越長，因為不能删除，存進裡面的元素越來越多，占用記憶體越來越多，誤判率越來越高，最後不得不重置。
應用于緩存穿透
用于緩解緩存穿透。緩存穿透的問題主要是因為傳進來的key在Redis中是不存在的，那麼就會直接打在DB上，造成DB壓力增大。
針對這種情況，可以在Redis前加上布隆過濾器，預先把資料庫中的資料加入到布隆過濾器中，因為布隆過濾器的底層資料結構是一個二進制向量，是以占用的空間并不是很大。在查詢Redis之前先通過布隆過濾器判斷是否存在，如果不存在就直接傳回，如果存在的話，按照原來的流程還是查詢Redis，Redis不存在則查詢DB。
這裡主要利用的是布隆過濾器判斷結果是不存在的話就一定不存在這一個特點，但是由于布隆過濾器有一定的誤判，是以并不能說完全解決緩存穿透，但是能很大程度緩解緩存穿透的問題。
布隆過濾器插件
我們知道布隆過濾器的底層原理之後，理論上是可以自己
在Redis4.0後，官方提供了布隆過濾器的插件功能，布隆過濾器可以作為一個插件加載到Redis伺服器直接使用。
首先安裝Redis，網上有很多安裝教程，這裡就不多贅述。這裡我用的是Redis6.0.10版本。安裝完Redis之後，下載下傳插件，使用git指令拉取：
git clone https://github.com/RedisBloom/RedisBloom.git 拉取下來之後會得到一個RedisBloom的項目。
然後cd到檔案夾/RedisBloom，使用make指令編譯。
編譯完成後生成一個redisbloom.so檔案。
在啟動Redis時，加載布隆過濾器子產品到伺服器中即可。
./src/redis-server --loadmodule /usr/local/RedisBloom/redisbloom.so 最後使用用戶端測試一下。
redis-6.0.10]$ ./src/redis-cli
127.0.0.1:6379> bf.add user sam
(integer) 1
127.0.0.1:6379> bf.add user jack
(integer) 1
127.0.0.1:6379> bf.exists user jack
(integer) 1
127.0.0.1:6379> bf.exists user tom
(integer) 0 布隆過濾器的基本指令如下：
- bf.add 添加元素到布隆過濾器
- bf.exists 判斷元素是否在布隆過濾器
- bf.madd 添加多個元素到布隆過濾器
- bf.mexists 判斷多個元素是否在布隆過濾器
127.0.0.1:6379> bf.madd user mike rose
1) (integer) 1
2) (integer) 1
127.0.0.1:6379> bf.mexists user blue mike
1) (integer) 0
2) (integer) 1 在實際開發中，一般都是使用Java程式操作Redis，不太可能直接使用指令行判斷，Java程式怎麼操作呢？
首先引入依賴，我使用的是SpringBoot2.0，是以引入依賴是3.15.0。
<dependency>
<groupId>org.redisson</groupId>
<artifactId>redisson-spring-boot-starter</artifactId>
<version>3.15.0</version>
</dependency> 接着寫個main方法示範一下。
public static void main(String[] args) throws Exception {
Config config = new Config();
config.useSingleServer().setAddress("redis://192.168.0.109:6379");
RedissonClient client = Redisson.create(config);
RBloomFilter<String> bloomFilter = client.getBloomFilter("user");
//嘗試初始化，預計元素55000000，期望誤判率0.03
bloomFilter.tryInit(55000000L, 0.03);
//添加元素到布隆過濾器中
bloomFilter.add("tom");
bloomFilter.add("mike");
bloomFilter.add("rose");
bloomFilter.add("blue");
System.out.println("布隆過濾器元素總數為：" + bloomFilter.count());//布隆過濾器元素總數為：4
System.out.println("是否包含tom：" + bloomFilter.contains("tom"));//是否包含tom：true
System.out.println("是否包含lei：" + bloomFilter.contains("lei"));//是否包含lei：false
client.shutdown();
} 總結
布隆過濾器有着明顯的優缺點，是以在使用的時候需要充分地考慮場景，還是那句話，沒有最好的技術，看菜下飯才是硬道理。除了在緩存穿透中使用之外，其實還可以使用于元素去重，web攔截器等等。
這篇文章就講到這裡，感謝大家的閱讀，希望看完之後能有所收獲。
覺得有用就點個贊吧，你的點贊是我創作的最大動力~
我是一個努力讓大家記住的程式員。我們下期再見！！！
能力有限，如果有什麼錯誤或者不當之處，請大家批評指正，一起學習交流！