布隆过滤器

布隆过滤器

布隆过滤器主要用于判断一个元素是否在一个集合中，它可以使用一个位数组简洁的表示一个数组。它的空间效率和查询时间远远超过一般的算法，但是它存在一定的误判的概率，适用于容忍误判的场景。如果布隆过滤器判断元素存在于一个集合中，那么大概率是存在在集合中，如果它判断元素不存在一个集合中，那么一定不存在于集合中。常常被用于大数据去重

算法思想

利用内存中一个长度为M的位数组B并初始化里面的所有位都为0，如下面的表格所示：

然后我们根据H个不同的散列函数，对传进来的字符串进行散列，并且每次的散列结果都不能大于位数组的长度。布隆过滤器的误判率取决于你使用多少个不同的散列函数，下面给出的代码中，给出了一些参考的误判率（参考代码中的枚举类：MisjudgmentRate）。现在我们先假定有4个不同散列函数，传入一个字符串并进行一次插入操作，这时会进行4次散列，假设到了4个不同的下标，这个时候我们就会去数组中，将这些下标的位置置为1，数组变更为：

如果接下来我们再传入同一个字符串时，因为4次的散列结果都是跟上一次一样的，所以会得出跟上面一样的结果，所有应该置1的位都已经置1了，这个时候我们就可以认为这个字符串是已经存在的了。因此不难发现，这是会存在一定的误判率的，具体由你采用的散列函数质量，以及散列函数的数量确定

基于java实现布隆过滤器

package com.hl.springbootrunner.serializable;

import java.io.FileInputStream;
import java.io.FileOutputStream;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
import java.io.Serializable;
import java.util.BitSet;
import java.util.concurrent.atomic.AtomicInteger;
 
public class BloomFilter implements Serializable {
	private static final long serialVersionUID = -5221305273707291280L;
	private final int[] seeds;
	private final int size;
	private final BitSet notebook;
	private final MisjudgmentRate rate;
	private final AtomicInteger useCount = new AtomicInteger(0);
	private final Double autoClearRate;
 
	/**
	 * 默认中等程序的误判率：MisjudgmentRate.MIDDLE 以及不自动清空数据（性能会有少许提升）
	 * 
	 * @param dataCount
	 * 预期处理的数据规模，如预期用于处理1百万数据的查重，这里则填写1000000
	 */
	public BloomFilter(int dataCount) {
		this(MisjudgmentRate.MIDDLE, dataCount, null);
	}
 
	/**
	 * 
	 * @param rate
	 * 个枚举类型的误判率
	 * @param dataCount
	 * 预期处理的数据规模，如预期用于处理1百万数据的查重，这里则填写1000000
	 * @param autoClearRate
	 * 自动清空过滤器内部信息的使用比率，传null则表示不会自动清理，
	 * 当过滤器使用率达到100%时，则无论传入什么数据，都会认为在数据已经存在了
	 * 当希望过滤器使用率达到80%时自动清空重新使用，则传入0.8
	 */
	public BloomFilter(MisjudgmentRate rate, int dataCount, Double autoClearRate) {
		long bitSize = (long) rate.seeds.length * dataCount;
		if (bitSize < 0 || bitSize > Integer.MAX_VALUE) {
			throw new RuntimeException("位数太大溢出了，请降低误判率或者降低数据大小");
		}
		this.rate = rate;
		seeds = rate.seeds;
		size = (int) bitSize;
		notebook = new BitSet(size);
		this.autoClearRate = autoClearRate;
	}
 
	public void add(String data) {
		checkNeedClear();

		for (int seed : seeds) {
			int index = hash(data, seed);
			setTrue(index);
		}
	}
 
	public boolean check(String data) {
		for (int seed : seeds) {
			int index = hash(data, seed);
			if (!notebook.get(index)) {
				return false;
			}
		}
		return true;
	}
 
	/**
	 * 如果不存在就进行记录并返回false，如果存在了就返回true
	 * 
	 * @param data
	 * @return
	 */
	public boolean addIfNotExist(String data) {
		checkNeedClear();
 
		int[] indexs = new int[seeds.length];
		// 先假定存在
		boolean exist = true;
		int index;
 
		for (int i = 0; i < seeds.length; i++) {
			indexs[i] = index = hash(data, seeds[i]);
 
			if (exist) {
				if (!notebook.get(index)) {
					// 只要有一个不存在，就可以认为整个字符串都是第一次出现的
					exist = false;
					// 补充之前的信息
					for (int j = 0; j <= i; j++) {
						setTrue(indexs[j]);
					}
				}
			} else {
				setTrue(index);
			}
		}
 
		return exist;
 
	}
 
	private void checkNeedClear() {
		if (autoClearRate != null) {
			if (getUseRate() >= autoClearRate) {
				synchronized (this) {
					if (getUseRate() >= autoClearRate) {
						notebook.clear();
						useCount.set(0);
					}
				}
			}
		}
	}
 
	public void setTrue(int index) {
		useCount.incrementAndGet();
		notebook.set(index, true);
	}
 
	private int hash(String data, int seeds) {
		char[] value = data.toCharArray();
		int hash = 0;
		if (value.length > 0) {
 
			for (int i = 0; i < value.length; i++) {
				hash = i * hash + value[i];
			}
		}
	
		hash = hash * seeds % size;
		// 防止溢出变成负数
		return Math.abs(hash);
	}
 
	public double getUseRate() {
		return (double) useCount.intValue() / (double) size;
	}
 
	public void saveFilterToFile(String path) {
		try (ObjectOutputStream oos = new ObjectOutputStream(new FileOutputStream(path))) {
			oos.writeObject(this);
		} catch (Exception e) {
			throw new RuntimeException(e);
		}
 
	}
 
	public static BloomFilter readFilterFromFile(String path) {
		try (ObjectInputStream ois = new ObjectInputStream(new FileInputStream(path))) {
			return (BloomFilter) ois.readObject();
		} catch (Exception e) {
			throw new RuntimeException(e);
		}
	}
 
	/**
	 * 清空过滤器中的记录信息
	 */
	public void clear() {
		useCount.set(0);
		notebook.clear();
	}
 
	public MisjudgmentRate getRate() {
		return rate;
	}
 
	/**
	 * 分配的位数越多，误判率越低但是越占内存
	 * 
	 * 4个位误判率大概是0.14689159766308
	 * 
	 * 8个位误判率大概是0.02157714146322
	 * 
	 * 16个位误判率大概是0.00046557303372
	 * 
	 * 32个位误判率大概是0.00000021167340
	 * 
	 * @author lianghaohui
	 *
	 */
	public enum MisjudgmentRate {
		// 这里要选取质数，能很好的降低错误率
		/**
		 * 每个字符串分配4个位
		 */
		VERY_SMALL(new int[] { 2, 3, 5, 7 }),
		/**
		 * 每个字符串分配8个位
		 */
		SMALL(new int[] { 2, 3, 5, 7, 11, 13, 17, 19 }), //
		/**
		 * 每个字符串分配16个位
		 */
		MIDDLE(new int[] { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53 }), //
		/**
		 * 每个字符串分配32个位
		 */
		HIGH(new int[] { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97,
				101, 103, 107, 109, 113, 127, 131 });
 
		private int[] seeds;
 
		private MisjudgmentRate(int[] seeds) {
			this.seeds = seeds;
		}
 
		public int[] getSeeds() {
			return seeds;
		}
 
		public void setSeeds(int[] seeds) {
			this.seeds = seeds;
		}
 
	}

	public static void main(String[] args) {
		BloomFilter fileter = new BloomFilter(7);
		System.out.println(fileter.addIfNotExist("1111111111111"));
		System.out.println(fileter.addIfNotExist("2222222222222222"));
		System.out.println(fileter.addIfNotExist("3333333333333333"));
		System.out.println(fileter.addIfNotExist("444444444444444"));
		System.out.println(fileter.addIfNotExist("5555555555555"));
		System.out.println(fileter.addIfNotExist("6666666666666"));
		System.out.println(fileter.addIfNotExist("1111111111111"));
		fileter.saveFilterToFile("E:\\desktop\\11.txt");
		fileter = readFilterFromFile("E:\\desktop\\11.txt");
		System.out.println(fileter.getUseRate());
		System.out.println(fileter.addIfNotExist("1111111111111"));
	}
}

基于Redisson实现布隆过滤器

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

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("phoneList");
        //初始化布隆过滤器：预计元素为100000000L,误差率为3%
        bloomFilter.tryInit(100000000L,0.03);
        //将号码10086插入到布隆过滤器中
        bloomFilter.add("10086");

        //判断下面号码是否在布隆过滤器中
        System.out.println(bloomFilter.contains("123456"));//false
        System.out.println(bloomFilter.contains("10086"));//true
    }
}

这是单节点的Redis实现方式，如果数据量比较大，期望的误差率又很低，那单节点所提供的内存是无法满足的，这时候可以使用分布式布隆过滤器，同样也可以用 Redisson 来实现

基于guava工具实现布隆过滤器

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

public class GuavaBloomFilter {
    public static void main(String[] args) {
        
        BloomFilter<String> bloomFilter = BloomFilter.create(Funnels.stringFunnel(Charsets.UTF_8),100000,0.01);

        bloomFilter.put("10086");

        System.out.println(bloomFilter.mightContain("123456"));
        System.out.println(bloomFilter.mightContain("10086"));
    }
}