布隆过滤器

布隆过滤器概述

布隆过滤器解决这样一个问题，假设有一个搜索引擎公司，在他公司的服务器上，有100亿条URL黑名单，当你搜索某个URL的时候，服务器就会检测这些URL在不在黑名单，如果在，就不显示，如果不在，就显示

首先算一下这个100亿的URL占多大存储空间，假设一个URL是64字节，算下来总共大概640GB

要求：

1. 该系统允许有万分之一以下的失误率
2. 使用的额外空间不能超过30GB

哈希函数

在了解布隆过滤实现之前先认识哈希函数

哈希函数的性质：

1. 经典哈希函数的输入域无穷大
2. 输出域有穷
3. 哈希函数没有随机值。★即输入一样，输出也一样★
4. 因为输入域无穷大，输出域有穷，所以必定存在多个输入对应一个输出
5. 由于哈希函数的离散性，所有的输入总是“均匀的”分布在所有的输出中。例如：有0~98个输入，输出 0~2。在0位置有33个左右的输入，其他也相同
6. 离散性的推论：当所有的输入对应的输出都模一个数m，那么在输出0~m-1上也是“均匀分布的”

布隆过滤器

如果把黑名单中所有的URL通过数据库或哈希表保存下来，就可以对每条URL进行查询，但是至少需要640GB的空间，不满足要求

如果遇到网页黑名单系统、垃圾邮件过滤系统、爬虫的网址判重系统等问题，又看到系统容忍一定程度的失误率，但是对空间要求比较严格，那么很可能就需要用到布隆过滤器。一个布隆过滤器精确地代表一个集合，并可以精确判断一个元素是否在集合中。注意，只是精确代表和精确判断，到底有多少精确呢？则完全在于你具体的设计，但想做到完全正确是不可能的。布隆过滤器的优势在于使用很少的空间就可以将准确率做到很高的程度。

假设有一个长度为m的bit类型的数组，即数组中的每一个位置只占一个bit，每一个bit只有0和1两种状态。再假设有k个哈希函数，这些函数的输出域S都大于或等于m，并且这些哈希函数都足够优秀，彼此之间也完全独立。那么对同一个输入对象（假设是一个字符串记为URL），经过k个哈希函数算出来的结果也是独立的，可能相同，也可能不相同，但彼此独立。对算出来的每一个结果都对m取余（%m），然后在bit数组上把相应的位置设置为1（涂黑）

把bit类型的数组记为bitMap。至此，一个输入对象对bitMap的影响过程就结束了，也就是bitMap中的一些未知会被涂黑。接下来按照该方法处理所有的输入对象，每个对象都可能把bitMap中的一些白位置涂黑，也可能遇到已经涂黑的位置，遇到已经涂黑的位置让其继续为黑即可。处理完所有的输入对象后，可能bitMap中已经有相当多的位置被涂黑。至此，一个布隆过滤器生成完毕，这个布隆过滤器代表之前所有输入对象组成的集合

如何检查某一个对象是否是之前的某一个输入对象呢？假设一个对象为a，想检查它是否是之前的输入对象，就把a通过k个哈希函数算出k个值，然后把k个值取余（%m），就得到在[0,m-1]范围上的k个值。接下来在bitMap上看这些位置是不是都为黑。如果有一个不为黑，说明a一定不在这个集合里。如果都为黑，说明a在这个集合里，但可能有误判。具体一点，如果a的确是输入对象，那么在生成布隆过滤器时，bitMap中相应的k个位置一定已经涂黑了，所以在检查阶段，a一定不会被漏过，这个不会产生误判。会产生误判的是，a明明不是输入对象，但如果在生成布隆过滤器的阶段因为输入对象太多，而bitMap过小，则会导致bitMap绝大多数的位置都已经变黑。那么在检查a时，可能a对应的k个位置都是黑的，从而错误地认为a是输入对象。通俗地说，布隆过滤器的失误类型是“宁可错杀三千，绝不放过一个”。使用布隆过滤器的另一个好处是不用顾忌单个样本的大小，它丝毫不会影响布隆过滤器的大小

如果bitMap的大小m相对于输入对象的个数n过小，失误率会变大。根据n的大小和想要达到的失误率p，如何确定布隆过滤器的大小m和哈希函数的个数k，最后是布隆过滤器的失误率分析

布隆过滤器失误率分析

黑名单中样本的个数为100亿个，记为$n$；失误率不能超过0.01%，记为$p$；每个样本的大小为64B,这个信息不会影响布隆过滤器的大小，只和选择哈希函数有关，一般的哈希函数都可以接收64B的输入对象

所以$n=100亿$，$p=0.01%$,布隆过滤器的大小m由以下公式确定：

$$

m = -\frac{n*lnp}{(ln2)^2}

$$

根据公式计算出$m = 19.19n$，向上取整为$20n$，即需要2000亿个bit，也就是25GB

哈希函数的个数$k$由以下公式确定：

$$

k = ln2*\frac{m}{n} = 0.7*\frac{m}{n}

$$

计算出哈希函数的个数为$k = 14$个

用25GB的bitMap再加上单独实现的14个哈希函数，根据如上描述生成布隆过滤器即可。因为我们在确定布隆过滤器大小的过程中选择了向上取整，所以还要用如下公式确定布隆过滤器真实的失误率为：

$$

p = (1 - e^{-\frac{nk}{m}})^k

$$

根据这个公式算出真实的失误率为$0.006%$，这是比$0.01%$更低的失误率，哈希函数本身不占用什么空间，所以使用空间就是bitMap的大小（即25GB），服务器的内存都可以达到这个级别，所有要求达标。

代码

/**
 * 布隆过滤器
 */
public class SimpleBloomFilter {
    private static final int DEFAULT_SIZE = 2 << 24;
    private static final int[] seeds = new int[]{7, 11, 13, 31, 37, 61};
 
    private BitSet bits = new BitSet(DEFAULT_SIZE);
    private SimpleHash[] func = new SimpleHash[seeds.length];
 
    public SimpleBloomFilter() {
        for (int i = 0; i < seeds.length; i++) {
            func[i] = new SimpleHash(DEFAULT_SIZE, seeds[i]);
        }
    }
 
    public void add(String value) {
        for (SimpleHash f : func) {
            bits.set(f.hash(value), true);
        }
    }
 
    public boolean contains(String value) {
        if (value == null) {
            return false;
        }
        boolean ret = true;
        for (SimpleHash f : func) {
            ret = ret && bits.get(f.hash(value));
        }
        return ret;
    }
 
    public static 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;
            int len = value.length();
            for (int i = 0; i < len; i++) {
                result = seed * result + value.charAt(i);
            }
            return (cap - 1) & result;
        }
    }
 
    public static void main(String[] args) {
        String value = "stone1234@125.com";
        SimpleBloomFilter filter = new SimpleBloomFilter();
        System.out.println(filter.contains(value));
        filter.add(value);
        System.out.println(filter.contains(value));
    }
}