布隆过滤器原理解析_布隆过滤器是线程安全的吗

在撸码的时候，经常要判断一个元素是否已经存在。常用的做法是，把已经存在的元素全部存储到一个集合里，然后新的元素查一下看它是否在集合里来确定是否已经存在。这个集合的数据结构，一般我们会采用HashMap，它可以在O(1)的时间复杂度内返回结果，效率奇高。但是会带来一个问题，就是每条数据都完整地存储在集合里，量大的时候，占据的内存空间是个问题。

如果你刚好遇到这方面的问题，那么可以考虑一下布隆过滤器了。

一、布隆过滤器的原理和作用

1、原理

布隆过滤器实际上是一个很长的二进制向量和一系列随机映射函数。二进制向量，其实就是只能存储0和1的一个数组，每个位置的初始值是0。随机映射函数，用来计算元素得到一个哈希值，然后在数组中这个哈希值对应下标位置的值改为1。比如

定义一个长度为10的二进制向量

用三种映射函数计算字符"周"的哈希值，假如分别得到2、5、8，那么就把二进制向量（就是数组）对应下标位置的值都置为1

再搞一个字符"华"来试一下，假如用三种映射函数计算哈希值分别得到2、5、6，那么处理后数组就变成了这样

如果我需要判断字符"煌"是否存在，首先使用同样的3个映射函数分别计算得到哈希值，比如是3、4、5，然后判断数组中对应下标位置的值。只要有一个为0，那么说明这个字符一定不存在，但是如果全是1呢，只能说可能存在。为什么呢？

我们知道，哈希求值会有冲突的情况（参考HashMap中采用数组+链表的结构），随着存储的数据增加，不同的字符计算得到的哈希值就有可能相同，这个时候，就不能判断一个元素是否一定存在了。——这就是会存在误判。

很显然，二进制向量长度过小的布隆过滤器很快所有的bit位均为1，那么查询任何值都会返回“可能存在”，起不到过滤的目的了。布隆过滤器的长度会直接影响误报率，布隆过滤器越长其误报率越小。另外，映射函数的个数也需要权衡，个数越多则布隆过滤器bit位置位1的速度越快，且布隆过滤器的效率越低；但是如果太少的话，那我们的误报率会变高。

 

如何选择适合业务的 k 和 m 值呢，这里直接贴一个公式：

我们说了布隆过滤器的元素添加和判断是否存在，那么是否支持删除呢？

上面那种是不可以的，为什么呢？比如，你想删除字符"周"，就把数组的2、5、8位置的值置为0，但是，2和5这个位置字符"华"它也有份，假如你把这两个位置的值改成0了，下次判断字符"华"时就因为存在0而认为它不存在，实际上人家是存在的。

如何解决这个问题，答案是计数删除。但是计数删除需要存储一个数值，而不是原先的bit位，会增大占用的内存大小。这样的话，增加一个值就是将对应索引槽上存储的值加一，删除则是减一，判断是否存在则是看值是否大于0。 

2、用途

经过上面的原理剖析，至少知道了布隆过滤器的特点

• 优点：由于存放的不是完整的数据，所以占用的内存很少；而且新增、查询速度够快。
• 缺点：随着数据的增加，误判率随之增加；无法做到删除数据；只能判断数据是否一定不存在，而无法判断数据是否一定存在。

应用场景有哪些呢？

1)缓存穿透

我们经常会把一部分数据放在Redis等缓存，比如产品详情。这样有查询请求进来，我们可以根据产品Id直接去缓存中取数据，而不用读取数据库，这是提升性能最简单，最普遍，也是最有效的做法。一般的查询请求流程是这样的：先查缓存，有缓存的话直接返回，如果缓存中没有，再去数据库查询，然后再把数据库取出来的数据放入缓存，一切看起来很美好。但是如果现在有大量请求进来，而且都在请求一个不存在的产品Id，会发生什么？既然产品Id都不存在，那么肯定没有缓存，没有缓存，那么大量的请求都怼到数据库，数据库的压力一下子就上来了，还有可能把数据库打死。
虽然有很多办法都可以解决这问题，但是我们的主角是“布隆过滤器”，没错，“布隆过滤器”就可以解决（缓解）缓存穿透问题。至于为什么说是“缓解”，看下去你就明白了。

2)大量数据，判断给定的是否在其中

现在有大量的数据，而这些数据的大小已经远远超出了服务器的内存，现在再给你一个数据，如何判断给你的数据在不在其中。如果服务器的内存足够大，那么用HashMap是一个不错的解决方案，理论上的时间复杂度可以达到O(1)，但是现在数据的大小已经远远超出了服务器的内存，所以无法使用HashMap，这个时候就可以使用“布隆过滤器”来解决这个问题。但是还是同样的，会有一定的“误判率”。

二、布隆过滤器的Java实现

• 1）二进制向量，可以使用BitSet（存储的类型是boolean，所有位置默认值是false）取代。
• 2）多个映射函数：分别配合一组不同的质数求值。
• 3）哈希值不超过数组下标：对结果再进行 &(长度-1) 的操作。

直接上代码（线程安全且支持自定义长度和映射函数数量）

import java.util.BitSet;
import java.util.Objects;
import java.util.concurrent.locks.ReentrantReadWriteLock;
 
/**
 * 布隆过滤器
 *
 * @author Zhou Huanghua
 */
public class BloomFilter {
    private BitSet bits;
    private SimpleHash[] hashFuncs;
 
    private ReentrantReadWriteLock readWriteLock = new ReentrantReadWriteLock();
    private ReentrantReadWriteLock.ReadLock readLock = readWriteLock.readLock();
    private ReentrantReadWriteLock.WriteLock writeLock = readWriteLock.writeLock();
 
    public BloomFilter(int bitNum, int hashFuncNum) {
        if (bitNum < 1 || bitNum < 1) {
            throw new IllegalArgumentException("bitNum and hashFuncNum must greater than 0");
        }
        bits = new BitSet(bitNum);
        hashFuncs = new SimpleHash[hashFuncNum];
        int[] primes = getPrimes(hashFuncNum);
        for (int i = 0; i < hashFuncNum; i++) {
            hashFuncs[i] = new SimpleHash(bitNum, primes[i]);
        }
    }
 
    public void add(String value) {
        if (Objects.isNull(value)) {
            throw new NullPointerException("value can't be null");
        }
        writeLock.lock();
        try {
            for (SimpleHash f : hashFuncs) {
                bits.set(f.hash(value), true);
            }
        } finally {
            writeLock.unlock();
        }
    }
 
    public boolean contains(String value) {
        if (value == null) {
            return false;
        }
        readLock.lock();
        try {
            boolean ret = true;
            for (SimpleHash f : hashFuncs) {
                ret = ret && bits.get(f.hash(value));
            }
            return ret;
        } finally {
            readLock.unlock();
        }
    }
 
    private int[] getPrimes(int num) {
        int[] primes = new int[num];
        for (int i = 2, idx = 0; idx < num; ++i) {
            boolean isPrime = true;
            for (int j = 2, middle = i / 2; j <= middle; ++j) {
                if (i % j == 0) {
                    isPrime = false;
                    break;
                }
            }
            if (isPrime) {
                primes[idx++] = i;
            }
        }
        return primes;
    }
 
    private class SimpleHash {
        private int cap;
        private int seed;
 
        public SimpleHash(int cap, int seed) {
            this.cap = cap;
            this.seed = seed;
        }
 
        public int hash(String value) {
            int result = 0;
            for (int i = 0, len = value.length(); i < len; i++) {
                result = seed * result + value.charAt(i);
            }
            return (cap - 1) & result;
        }
    }
}

用法如下

public static void main(String[] args) {
        BloomFilter bloomFilter = new BloomFilter(2 << 24, 8);
 
        String value = "zhou";
        Assert.assertFalse(bloomFilter.contains(value));
        bloomFilter.add(value);
        Assert.assertTrue(bloomFilter.contains(value));
 
 
        Assert.assertFalse(bloomFilter.contains(null));
        // 抛异常
        bloomFilter.add(null);
    }

三、网上现有的开源工具

发明轮子只是为了理解其背后的实现原理，真正使用还得拥抱流行的开源-_-。

guava和elasticsearch的实现很相似。

1、Guava的BloomFilter

Funnel参数的作用就是，根据你传入的对象确定真正插入和用于判断的key。传入预期插入值和误报率之后，它会帮你自动设置向量长度和函数个数。

        // 创建实例，传入"转换器"、预期插入值、误报率
        BloomFilter bloomFilter = BloomFilter.create(new Funnel<String>() {
            @Override
            public void funnel(String s, PrimitiveSink primitiveSink) {
                primitiveSink.putString(s, Charset.defaultCharset());
            }
        }, 2 << 24, 0.0000001D);
 
        String value = "周";
        // 此时不存在
        Assert.assertFalse(bloomFilter.mightContain(value));
        // 添加值
        bloomFilter.put(value);
        // 现在存在了
        Assert.assertTrue(bloomFilter.mightContain(value));

2、Elasticsearch的BloomFilter

传入预期插入值和误报率之后，它会帮你自动设置向量长度和函数个数。

        // 创建实例，传入预期插入值、误报率
        BloomFilter bloomFilter = BloomFilter.create(2 << 24, 0.0000001D);
 
        BytesRef value = new BytesRef("周");
        // 此时不存在
        Assert.assertFalse(bloomFilter.mightContain(value));
        // 添加值
        bloomFilter.put(value);
        // 现在存在了
        Assert.assertTrue(bloomFilter.mightContain(value));

3、Redis的布隆过滤器

使用redis 4.0以上的版本可以通过加载module来使用redis中的布隆过滤器。但是这不是最简单的方式，使用docker可以直接在redis中体验布隆过滤器。
暂时没发现比较好的开源实现，不过你可以自己写一个。

总结一下：布隆过滤器可以确定一个元素一定不存在，只能判断一个元素可能存在，向量长度和随机函数数量决定其误报率。