BloomFilter
定义：空间效率高的概率型数据结构，用来检查一个元素是否在一个集合中
原理：当一个元素被加入集合时，通过K个散列函数将这个元素映射成一个位数组中的K个点，把它们置为1。检索时，我们只要看看这些点是不是都是1就（大约）知道集合中有没有它了
如果这些点有任何一个0，则被检元素一定不在；如果都是1，则被检元素很可能在。
使用场景：可用于解决网页 URL 去重、垃圾邮件识别、大集合中重复元素的判断和缓存穿透等问题
布隆过滤器存储空间和插入/查询时间都是常数O(k)
BloomFilter算法
布隆过滤器（Bloom Filter）的核心实现是一个超大的位数组和几个哈希函数。
假设位数组的长度为m，哈希函数的个数为k，保存数据只需要将哈希函数的结果值都置为1
BloomFilter算法推导见Bloom Filters - the math，Bloom_filter-wikipedia哈希函数数量最优化见Building a Better Bloom Filter
BloomFilter缺点
bloom filter之所以能做到在时间和空间上的效率比较高，是因为牺牲了判断的准确率、删除的便利性
存在误判。可能要查到的元素并没有在容器中，但是hash之后得到的k个位置上值都是1。如果bloom filter中存储的是黑名单，那么可以通过建立一个白名单来存储可能会误判的元素。删除困难。一个放入容器的元素映射到bit数组的k个位置上是1，删除的时候不能简单的直接置为0，可能会影响其他元素的判断。可以采用Counting Bloom Filter
为了解决布隆过滤器中不能删除，且存在误判的缺点，新的哈希算法——cuckoo filter出现了。它既可以确保该元素存在的必然性，又可以在不违背此前提下删除任意元素，仅仅比bitmap牺牲了微量空间效率。Cuckoo filter
BloomFilter实现
对于一个确定的场景，我们预估要存的数据量为n，期望的误判率为fpp，然后需要计算我们需要的Bit数组的大小m，以及hash函数的个数k，并选择hash函数。下面是Guava Bloom Filter的实现
Bit数组大小选择
m=m=m=−nlnfpp(ln2)2-\frac{nlnfpp}{(ln2)^2}−(ln2)2nlnfpp
哈希函数个数选择
k=k=k=mnln2\frac{m}{n}ln2nmln2
哈希函数的选择对性能的影响应该是很大的，一个好的哈希函数要能近似等概率的将字符串映射到各个Bit。选择k个不同的哈希函数比较麻烦，一种简单的方法是选择一个哈希函数，然后送入k个不同的参数
BloomFilter应用
Guava BloomFilter
<dependency><groupId>com.google.guava</groupId><artifactId>guava</artifactId><version>23.0</version></dependency>
源码
public static <T> BloomFilter<T> create(Funnel<? super T> funnel, int expectedInsertions) {return create(funnel, (long) expectedInsertions);} public static <T> BloomFilter<T> create(Funnel<? super T> funnel, long expectedInsertions) {return create(funnel, expectedInsertions, 0.03); // FYI, for 3%, we always get 5 hash functions}public static <T> BloomFilter<T> create(Funnel<? super T> funnel, long expectedInsertions, double fpp) {return create(funnel, expectedInsertions, fpp, BloomFilterStrategies.MURMUR128_MITZ_64);}static <T> BloomFilter<T> create(Funnel<? super T> funnel, long expectedInsertions, double fpp, Strategy strategy) {......}
调用
public class BloomFilterTest {private static int total = 1000000;private static BloomFilter<Integer> bf = BloomFilter.<Integer>create(Funnels.integerFunnel(), total);public static void main(String[] args) {bf.put(1);bf.mightContain(1);}}
redis插件
Redis 4.0 的时候官方提供了插件机制，集成了布隆过滤器的模块
参考资料：
BloomFilter wikiBloomFilter原理，实现及优化BloomFilter算法CuckooFilter wikiCuckooFilter论文
