什么是布隆過(guò)濾器
布隆過(guò)濾器（Bloom Filter）是1970年由布隆提出來(lái)的印蔬。它實(shí)際上是由一個(gè)很長(zhǎng)的二進(jìn)制數(shù)組+一系列hash算法映射函數(shù)勋桶，用于判斷一個(gè)元素是否存在于集合中。
布隆過(guò)濾器可以用于檢索一個(gè)元素是否在一個(gè)集合中侥猬。它的優(yōu)點(diǎn)是空間效率和查詢(xún)時(shí)間都比一般的算法要好的多例驹，缺點(diǎn)是有一定的誤識(shí)別率和刪除困難。
場(chǎng)景
假設(shè)有10億條手機(jī)號(hào)退唠，然后判斷某條手機(jī)號(hào)是否在列表內(nèi)鹃锈？
mysql可以嗎？
正常情況下瞧预，如果數(shù)據(jù)量不大屎债，我們可以考慮使用mysql存儲(chǔ)。將所有數(shù)據(jù)存儲(chǔ)到數(shù)據(jù)庫(kù)垢油，然后每次去庫(kù)里查詢(xún)判斷是否存在盆驹。但是如果數(shù)據(jù)量太大，超過(guò)千萬(wàn)滩愁，mysql查詢(xún)效率是很低的躯喇，特別消耗性能。
HashSet可以嗎
我們可以把數(shù)據(jù)放入HashSet中硝枉，利用HashSet天然的去重性廉丽，查詢(xún)只需要調(diào)用contains方法即可，但是hashset是存放在內(nèi)存中的妻味，數(shù)據(jù)量過(guò)大內(nèi)存直接oom了正压。
布隆過(guò)濾器特點(diǎn)
插入和查詢(xún)效率高，占用空間少弧可，但是返回的結(jié)果是不確定的蔑匣。
一個(gè)元素如果判斷為存在的時(shí)候劣欢，它不一定真的存在。但是如果判斷一個(gè)元素不存在裁良，那么它一定是不存在的凿将。
布隆過(guò)濾器可以添加元素，但是一定不能刪除元素价脾，會(huì)導(dǎo)致誤判率增加牧抵。
布隆過(guò)濾器原理
布隆過(guò)濾器其實(shí)就是是一個(gè)BIT數(shù)組，通過(guò)一系列hash算法映射出對(duì)應(yīng)的hash,然后將hash對(duì)應(yīng)的數(shù)組下標(biāo)位置改為1侨把。查詢(xún)時(shí)就是對(duì)數(shù)據(jù)在進(jìn)行一系列hash算法得到下標(biāo)犀变，從BIT數(shù)組里取數(shù)據(jù)如如果是1 則說(shuō)明數(shù)據(jù)有可能存在，如果是0 說(shuō)明一定不存在
為什么會(huì)有誤差率
我們知道布隆過(guò)濾器其實(shí)是對(duì)數(shù)據(jù)做hash,那么不管用什么算法秋柄，都有可能兩條不同的數(shù)據(jù)生成的hash確是相同的获枝，也就是我們常說(shuō)的hash沖突。
首先插入一條數(shù)據(jù)： 好好學(xué)技術(shù)
在插入一條數(shù)據(jù)：
這是如果查詢(xún)一條數(shù)據(jù)骇笔，假設(shè)他的hash下標(biāo)已經(jīng)標(biāo)為1了省店，那么布隆過(guò)濾器就會(huì)認(rèn)為他存在
常見(jiàn)使用場(chǎng)景
緩存穿透
java實(shí)現(xiàn)布隆過(guò)濾器
package com.fandf.test.redis;
import java.util.BitSet;
/**
* java布隆過(guò)濾器
*
* @author fandongfeng
*/
public class MyBloomFilter {
? ? /**
? ? * 位數(shù)組大小
? ? */
? ? private static final int DEFAULT_SIZE = 2 << 24;
? ? /**
? ? * 通過(guò)這個(gè)數(shù)組創(chuàng)建多個(gè)Hash函數(shù)
? ? */
? ? private static final int[] SEEDS = new int[]{4, 8, 16, 32, 64, 128, 256};
? ? /**
? ? * 初始化位數(shù)組，數(shù)組中的元素只能是 0 或者 1
? ? */
? ? private final BitSet bits = new BitSet(DEFAULT_SIZE);
? ? /**
? ? * Hash函數(shù)數(shù)組
? ? */
? ? private final MyHash[] myHashes = new MyHash[SEEDS.length];
? ? /**
? ? * 初始化多個(gè)包含 Hash 函數(shù)的類(lèi)數(shù)組笨触，每個(gè)類(lèi)中的 Hash 函數(shù)都不一樣
? ? */
? ? public MyBloomFilter() {
? ? ? ? // 初始化多個(gè)不同的 Hash 函數(shù)
? ? ? ? for (int i = 0; i < SEEDS.length; i++) {
? ? ? ? ? ? myHashes[i] = new MyHash(DEFAULT_SIZE, SEEDS[i]);
? ? ? ? }
? ? }
? ? /**
? ? * 添加元素到位數(shù)組
? ? */
? ? public void add(Object value) {
? ? ? ? for (MyHash myHash : myHashes) {
? ? ? ? ? ? bits.set(myHash.hash(value), true);
? ? ? ? }
? ? }
? ? /**
? ? * 判斷指定元素是否存在于位數(shù)組
? ? */
? ? public boolean contains(Object value) {
? ? ? ? boolean result = true;
? ? ? ? for (MyHash myHash : myHashes) {
? ? ? ? ? ? result = result && bits.get(myHash.hash(value));
? ? ? ? }
? ? ? ? return result;
? ? }
? ? /**
? ? * 自定義 Hash 函數(shù)
? ? */
? ? private class MyHash {
? ? ? ? private int cap;
? ? ? ? private int seed;
? ? ? ? MyHash(int cap, int seed) {
? ? ? ? ? ? this.cap = cap;
? ? ? ? ? ? this.seed = seed;
? ? ? ? }
? ? ? ? /**
? ? ? ? * 計(jì)算 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 = "好好學(xué)技術(shù)";
? ? ? ? MyBloomFilter myBloomFilter = new MyBloomFilter();
? ? ? ? System.out.println("str是否存在：" + myBloomFilter.contains(str));
? ? ? ? myBloomFilter.add(str);
? ? ? ? System.out.println("str是否存在：" + myBloomFilter.contains(str));
? ? }
}
Guava實(shí)現(xiàn)布隆過(guò)濾器
引入依賴(lài)
<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("好好學(xué)技術(shù)");
? ? ? ? System.out.println(bloomFilter.mightContain("不好好學(xué)技術(shù)"));
? ? ? ? System.out.println(bloomFilter.mightContain("好好學(xué)技術(shù)"));
? ? }
}
hutool實(shí)現(xiàn)布隆過(guò)濾器
引入依賴(lài)
<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("好好學(xué)技術(shù)");
? ? ? ? System.out.println(bloomFilter.contains("不好好學(xué)技術(shù)"));
? ? ? ? System.out.println(bloomFilter.contains("好好學(xué)技術(shù)"));
? ? }
}
Redisson實(shí)現(xiàn)布隆過(guò)濾器
引入依賴(lài)
<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 實(shí)現(xiàn)布隆過(guò)濾器
* @author fandongfeng
*/
public class RedissonBloomFilter {
? ? public static void main(String[] args) {
? ? ? ? Config config = new Config();
? ? ? ? config.useSingleServer().setAddress("redis://127.0.0.1:6379");
? ? ? ? //構(gòu)造Redisson
? ? ? ? RedissonClient redisson = Redisson.create(config);
? ? ? ? RBloomFilter<String> bloomFilter = redisson.getBloomFilter("name");
? ? ? ? //初始化布隆過(guò)濾器：預(yù)計(jì)元素為100000000L,誤差率為1%
? ? ? ? bloomFilter.tryInit(100000000L,0.01);
? ? ? ? bloomFilter.add("好好學(xué)技術(shù)");
? ? ? ? System.out.println(bloomFilter.contains("不好好學(xué)技術(shù)"));
? ? ? ? System.out.println(bloomFilter.contains("好好學(xué)技術(shù)"));
? ? }
}
