一布隆過濾器簡介

布隆過濾器（Bloom Filter）是 1970 年由布隆提出的類似于Set的數據結構。它實際上是一個很長的二進制向量和一系列隨機映射函數。布隆過濾器可以用于檢索一個元素是否在一個集合中，但檢索的結果并不是很精確，數據量變大的就會產生誤判情形，但布隆過濾器的都是能過濾掉已經存在的內容，所以誤判的情況就是不在布隆過濾器中的數據有可能誤判為已經存在，這個功能在某些場景下很有用。

布隆過濾器使用場景

布隆過濾器最大的作用就是大數據量下的去重功能，所以經常使用在如下場景

• 推薦系統，比如商品，新聞推薦，去除已經推薦過的新聞或商品；
• 網頁爬蟲對 URL 去重，避免爬取相同的 URL 地址；
• 大數據情況下，從郵件中判定垃圾郵箱；

二布隆過濾器原理簡介

布隆過濾器是由一串很長的二進制向量組成，可以將其看成一個二進制數組；存放0或者1，默認都是0；

添加數據

向布隆過濾器中添加一個元素key時，通過多個hash函數計算多個hash值，并將對應位置的值置為1；由于不同的key就有不同1的位置，用于區分key；但是但數據量大的時候，就會出現相同key被幾個hash函數hash后的值一樣，所以會出現誤差；

布隆過濾器使用contain方法判斷元素是否在過濾器中達到去重效果；

三實現方式

3.1guava庫實現

添加guava依賴

<dependency><groupId>com.google.guava</groupId><artifactId>guava</artifactId><version>29.0-jre</version></dependency>

實現：

@Test public void contextLoads() {// 總數量1Wint total = 10000;// 設置過濾器BloomFilter<CharSequence> bf =BloomFilter.create(Funnels.stringFunnel(Charsets.UTF_8), total);// 初始化 1W條數據到過濾器中for (int i = 0; i < total; i++) {bf.put("知識追尋者" + i);}// 判斷值是否存在過濾器中int count = 0;// 插入2w 條數據進行去重校驗int addCount = 2*total;for (int i = 0; i < addCount; i++) {if (bf.mightContain("知識追尋者" + i)) {count++;}}System.out.println("匹配數量 " + count); }

控制臺輸出匹配數量大于1w，所以能起到過濾重復數據的作用；

匹配數量 10294

調節fpp誤判率可以實現比較精確的過濾

294/2w=0.0147

fpp默認是0.03d, 設置為0.0147d

BloomFilter<CharSequence> bf =BloomFilter.create(Funnels.stringFunnel(Charsets.UTF_8), total,0.0147d);

匹配結果如下

匹配數量 10143

3.2redis實現方式

redis 4.0 版本才支持布隆過濾器

redis實現方式使用指令 bf.add 添加元素，bf.exists 查詢元素是否存在；數據量小的時候看不出來具體差別

127.0.0.1:6379> bf.add codeding h1 (integer) 1 127.0.0.1:6379> bf.add codeding h2 (integer) 1 127.0.0.1:6379> bf.add codeding h3 (integer) 1 127.0.0.1:6379> bf.exists codeding h1 (integer) 1 127.0.0.1:6379> bf.exists codeding h2 (integer) 1 127.0.0.1:6379> bf.exists codeding h3 (integer) 1 127.0.0.1:6379> bf.exists codeding h4 (integer) 0

使用Redisson實現，版本 3.x以上

<dependency><groupId>org.redisson</groupId><artifactId>redisson</artifactId><version>3.11.4</version> </dependency>

如果是springboot

<dependency><groupId>org.redisson</groupId><artifactId>redisson-spring-boot-starter</artifactId><version>3.10.1</version></dependency>

實現代碼

@Testpublic void test2(){Config config = new Config();config.useSingleServer().setAddress("redis://ip:port");config.useSingleServer().setPassword("密碼");//構造RedissonRedissonClient redisson = Redisson.create(config);// 獲取布隆過濾器RBloomFilter<String> bloomFilter = redisson.getBloomFilter("userList");//初始化布隆過濾器：預計元素為1wL,誤差率為3%// 總數量100long total = 100L;bloomFilter.tryInit(total,0.03);// 初始化 1W條數據到過濾器中for (int i = 0; i < total; i++) {bloomFilter.add("zszxz" + i);}int count = 0;// 200 條數據進行去重校驗long addCount = 2*total;for (int i = 0; i < addCount; i++) {if (bloomFilter.contains("zszxz" + i)) {count++;}}// 匹配數量 108System.out.println("匹配數量 " + count);}

匹配數量為 108 ，比100多了8條；也可以通過調整誤差率實現較為精確的過濾；

關注公眾號知識追尋者，獲取2020版面試題一份

總結

以上是生活随笔為你收集整理的布隆过滤器 redis_redis布隆过滤器的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。