布隆过滤器

布隆过滤器解决这样一个问题，假设有一个搜索引擎公司，在他公司的服务器上，有 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*\ln p}{(\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));
    }
}