大数据排重算法：布隆过滤器

发表于 | 分类于

什么是布隆过滤器(Bloom Filter)

布隆过滤器是布隆在1970年提出的。它实际是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。他的优点是空间效率和查询时间都有远远超过一般算法，确定是一定的误识别率和删除困难。

基本概念

一般判断一个元素是否在一个集合里，使用一个集合把所有的元素保存起来，再通过比较的方式判断。我们可能会想到使用下面的方式判断一个元素是否在集合中存在：

  1. 在数据库中创建字段的UNIQUE属性
  2. 在数据库中创建一个唯一的索引，在插入数据之前检查待插入的数据是否存在
  3. 使用Set或HashSet保存数据，确保唯一
  4. 使用Map或是一个定长数组记录某一个URL是否被访问过
    但是，随着数据量不断增加，当数据达到几百G的时候。上面的方法就变的不在方便。上面的方法会占用巨大的存储空间以及随着数据增多效率降低。
    布隆过滤器利用哈希函数将一个元素映射成一个阵列（Big array）中的一个点。这样我们只需要判断这个点是不是存在（值为1）就可以知道该元素是否存在于这个集合中。这就是布隆过滤器的思想。
    通常布隆过滤器会使用多个hash函数计算出多个点，如果某个元素计算出的点其中有一个不再集合中我们就认为该元素肯定不再集合中。

布隆过滤器原理图解

布隆过滤器（Bloom Filter）的核心实现是一个超大的位数组和几个哈希函数。假设位数组的长度为m，哈希函数的个数为k
布隆过滤器原理图
以上图为例，具体的操作流程：假设集合里面有3个元素{x, y, z}，哈希函数的个数为3。首先将位数组进行初始化，将里面每个位都设置位0。对于集合里面的每一个元素，将元素依次通过3个哈希函数进行映射，每次映射都会产生一个哈希值，这个值对应位数组上面的一个点，然后将位数组对应的位置标记为1。查询W元素是否存在集合中的时候，同样的方法将W通过哈希映射到位数组上的3个点。如果3个点的其中有一个点不为1，则可以判断该元素一定不存在集合中。反之，如果3个点都为1，则该元素可能存在集合中。注意：此处不能判断该元素是否一定存在集合中，可能存在一定的误判率。可以从图中可以看到：假设某个元素通过映射对应下标为4，5，6这3个点。虽然这3个点都为1，但是很明显这3个点是不同元素经过哈希得到的位置，因此这种情况说明元素虽然不在集合中，也可能对应的都是1，这是误判率存在的原因。

优点

与其他的判断方法相比，布隆过滤器在空间和时间上都有巨大的优势，布隆过滤器存储空间和插入、查询时间都是常数。布隆过滤器不存储元素本身，对信息安全要求较高的场合非常有利。

缺点

但是，布隆过滤器的确定也很明显。布隆过滤器室友误算率的。随着存入的数据增加，误算率也随之增加。如果数据量少。hash表就可以表示了。另外就是，布隆过滤器一般情况下都是不能删除元素的。

参考：布隆过滤器的空间、插入/询时间及误判率的数学证明

布隆过滤器的java实现

布隆过滤器的空间复杂度是S(n)=O(n)。下面是一个简单的布隆过滤器Java代码展示。而在查重过程也很有效率，时间复杂度是T(n)=O(1)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
import java.util.BitSet;  
  
public class BloomFilter {  
      
    /* BitSet初始分配2^24个bit */  
    private static final int DEFAULT_SIZE = 1 << 25;  
      
    /* 不同哈希函数的种子，一般应取质数 */  
    private static final int[] seeds = new int[] { 5, 7, 11, 13, 31, 37, 61 };  
      
    private BitSet bits = new BitSet(DEFAULT_SIZE);  
      
    /* 哈希函数对象 */  
    private SimpleHash[] func = new SimpleHash[seeds.length];  
  
    public BloomFilter() {  
        for (int i = 0; i < seeds.length; i++) {  
            func[i] = new SimpleHash(DEFAULT_SIZE, seeds[i]);  
        }  
    }  
  
    // 将字符串标记到bits中  
    public void add(String value) {  
        for (SimpleHash f : func) {  
            bits.set(f.hash(value), true);  
        }  
    }  
  
    // 判断字符串是否已经被bits标记  
    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;  
    }  
  
    /* 哈希函数类，可以采用成熟的hash函数 */  
    public static class SimpleHash {  
        private int cap;  
        private int seed;  
  
        public SimpleHash(int cap, int seed) {  
            this.cap = cap;  
            this.seed = seed;  
        }  
  
        // hash函数，采用简单的加权和hash  
        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;  
        }  
    }  
}

应用场景

  1. 假定我们存储一亿个电子邮件地址，我们先建立一个十六亿二进制（比特），即两亿字节的向量，然后将这十六亿个二进制全部设置为零。对于每一个电子邮件地址 X，我们用八个不同的随机数产生器（F1,F2, …,F8） 产生八个信息指纹（f1, f2, …, f8）。再用一个随机数产生器 G 把这八个信息指纹映射到 1 到十六亿中的八个自然数 g1, g2, …,g8。现在我们把这八个位置的二进制全部设置为一。当我们对这一亿个 email 地址都进行这样的处理后。一个针对这些 email 地址的布隆过滤器就建成了。
  2. 网络爬虫：URL去重