什麼是布隆過濾器
布隆過濾器（Bloom Filter）是1970年由布隆提出來的。它實際上是由一個很長的二進制數組 一系列hash演算法映射函數，用於判斷一個元素是否存在於集合中。
布隆過濾器可以用來檢索一個元素是否在一個集合中。它的優點是空間效率和查詢時間都比一般的演算法要好的多，缺點是有一定的誤識別率和刪除困難。
場景
假設有10億個手機號，然後判斷某條手機號碼是否在清單內？
mysql可以嗎？
正常情況下，如果資料量不大，我們可以考慮使用mysql儲存。將所有資料儲存到資料庫，然後每次去庫裡查詢判斷是否存在。但如果資料量太大，超過千萬，mysql查詢效率是很低的，特別消耗效能。
HashSet可以嗎？
我們可以把資料放入HashSet中，利用HashSet天然的去重性，查詢只需要呼叫contains方法即可，但是hashset是存放在記憶體中的，資料量過大記憶體直接oom了。
布隆過濾器特點
插入和查詢效率高，佔用空間少，但是傳回的結果是不確定的。
一個元素如果判斷為存在的時候，它不一定真的存在。但是如果判斷一個元素不存在，那麼它一定是不存在的。
布隆過濾器可以加入元素，但一定無法刪除元素，會導致誤判率增加。
布隆過濾器原理
布隆過濾器其實就是一個BIT數組，透過一系列hash演算法映射出對應的hash,然後將hash對應的數組下標位置改為1。查詢時就是對資料在進行一系列hash演算法得到下標，從BIT數組取資料如如果是1 則表示資料有可能存在，如果是0 說明一定不存在
為什麼會有誤差率
我們知道布隆過濾器其實是對數據做hash,那麼不管用什麼演算法，都有可能兩條不同的數據生成的hash確是相同的，也就是我們常說的hash衝突。
先插入一條資料： 好好學技術
在插入一資料：
這是如果查詢一條數據，假設他的hash下標已經標為1了，那麼布隆過濾器就會認為他存在
常見使用場景
快取穿透
java實作布林過濾器
package com.fandf.test.redis;
import java.util.BitSet;
/**
* java布隆过滤器
*
* @author fandongfeng
*/
public class MyBloomFilter {
/**
* 位数组大小
*/
private static final int DEFAULT_SIZE = 2 << 24;
/**
* 通过这个数组创建多个Hash函数
*/
private static final int[] SEEDS = new int[]{4, 8, 16, 32, 64, 128, 256};
/**
* 初始化位数组，数组中的元素只能是 0 或者 1
*/
private final BitSet bits = new BitSet(DEFAULT_SIZE);
/**
* Hash函数数组
*/
private final MyHash[] myHashes = new MyHash[SEEDS.length];
/**
* 初始化多个包含 Hash 函数的类数组，每个类中的 Hash 函数都不一样
*/
public MyBloomFilter() {
// 初始化多个不同的 Hash 函数
for (int i = 0; i < SEEDS.length; i++) {
myHashes[i] = new MyHash(DEFAULT_SIZE, SEEDS[i]);
}
}
/**
* 添加元素到位数组
*/
public void add(Object value) {
for (MyHash myHash : myHashes) {
bits.set(myHash.hash(value), true);
}
}
/**
* 判断指定元素是否存在于位数组
*/
public boolean contains(Object value) {
boolean result = true;
for (MyHash myHash : myHashes) {
result = result && bits.get(myHash.hash(value));
}
return result;
}
/**
* 自定义 Hash 函数
*/
private class MyHash {
private int cap;
private int seed;
MyHash(int cap, int seed) {
this.cap = cap;
this.seed = seed;
}
/**
* 计算 Hash 值
*/
int hash(Object obj) {
return (obj == null) ? 0 : Math.abs(seed * (cap - 1) & (obj.hashCode() ^ (obj.hashCode() >>> 16)));
}
}
public static void main(String[] args) {
String str = "好好学技术";
MyBloomFilter myBloomFilter = new MyBloomFilter();
System.out.println("str是否存在：" + myBloomFilter.contains(str));
myBloomFilter.add(str);
System.out.println("str是否存在：" + myBloomFilter.contains(str));
}
}登入後複製
Guava實作布林過濾器
引入依賴
<dependency>
<groupId>com.google.guava</groupId>
<artifactId>guava</artifactId>
<version>31.1-jre</version>
</dependency>登入後複製
package com.fandf.test.redis;
import com.google.common.base.Charsets;
import com.google.common.hash.BloomFilter;
import com.google.common.hash.Funnels;
/**
* @author fandongfeng
*/
public class GuavaBloomFilter {
public static void main(String[] args) {
BloomFilter<String> bloomFilter = BloomFilter.create(Funnels.stringFunnel(Charsets.UTF_8),100000,0.01);
bloomFilter.put("好好学技术");
System.out.println(bloomFilter.mightContain("不好好学技术"));
System.out.println(bloomFilter.mightContain("好好学技术"));
}
}登入後複製
hutool實作布林過濾器
引入依賴
<dependency>
<groupId>cn.hutool</groupId>
<artifactId>hutool-all</artifactId>
<version>5.8.3</version>
</dependency>登入後複製
package com.fandf.test.redis;
import cn.hutool.bloomfilter.BitMapBloomFilter;
import cn.hutool.bloomfilter.BloomFilterUtil;
/**
* @author fandongfeng
*/
public class HutoolBloomFilter {
public static void main(String[] args) {
BitMapBloomFilter bloomFilter = BloomFilterUtil.createBitMap(1000);
bloomFilter.add("好好学技术");
System.out.println(bloomFilter.contains("不好好学技术"));
System.out.println(bloomFilter.contains("好好学技术"));
}
}登入後複製
Redisson實作布林過濾器
引入依賴
<dependency>
<groupId>org.redisson</groupId>
<artifactId>redisson</artifactId>
<version>3.20.0</version>
</dependency>登入後複製
package com.fandf.test.redis;
import org.redisson.Redisson;
import org.redisson.api.RBloomFilter;
import org.redisson.api.RedissonClient;
import org.redisson.config.Config;
/**
* Redisson 实现布隆过滤器
* @author fandongfeng
*/
public class RedissonBloomFilter {
public static void main(String[] args) {
Config config = new Config();
config.useSingleServer().setAddress("redis://127.0.0.1:6379");
//构造Redisson
RedissonClient redisson = Redisson.create(config);
RBloomFilter<String> bloomFilter = redisson.getBloomFilter("name");
//初始化布隆过滤器：预计元素为100000000L,误差率为1%
bloomFilter.tryInit(100000000L,0.01);
bloomFilter.add("好好学技术");
System.out.println(bloomFilter.contains("不好好学技术"));
System.out.println(bloomFilter.contains("好好学技术"));
}
}登入後複製
以上是如何在Java中實作布隆過濾器？的詳細內容。更多資訊請關注PHP中文網其他相關文章！
