布隆过滤器的原理及使用

一、BloomFilter简介

BloomFilter是大数据领域中经常使用到的算法，主要用于在海量的数据中判断一个数据是否已经存在，但

如果不存在，判断结果一定是正确的。如果存在判断结果可能出现错误；这种数据结构的速度是非常快的，内

存消耗得比较小，使用很方便，在各种编程语言中都有对应实现的类库

二、Bloom的原理

BloomFilter本身是一个非常长的二进制向量（可以看成一个位数组）和一个映射函数。这个位数组初始情

况下内部全部是0，长度是m；对于每个新增的项，我们使用K种不同的hash算法对他计算hash值，可以得到K

个hash值，再使用这些hash值对m取模映射到数组范围内，假设取模后的结果是x，便会把x值对应的位置标记

为1，过程图如下：

3Tbkk9.png

但是当插入的数据大幅提升的时候，位数组中大部分的元素就会被置成１。此时如果查询一个元素，通过

哈希函数映射到的位置可能已经被标记了，这时候就会出现误判；但是如果所有映射的位置中出现未被标记的

位置，那么这个元素一定是不存在的，原理示意图如下：

3TbEf1.png

我们可以使用Python将Bloomfilter实现的原理用代码实现：

#插入元素
def BloomFilter(filter,value,hash_functions):
    m = len(filter)
    for func in hash_functions: 
        idx = func(value) % m     #哈希映射取模
        filter[idx] = True        #对应的位置进行标记
    return filter

#判断元素
def MemberInFilter(filter,value,hash_functions):
    m = len(filter)
    for func in hash_functions:
        idx = func(value) % m
        if not filter[idx]:
            return False
    return True

　通过上面的代码实现我们可以看到BloomFilter插入数据和查询数据时的时间复杂度都是O（k）,其中k是哈

希函数的个数；注意一点BloomFilter是不支持删除的，因为它的每一位并不是独占的，很有可能多个元素共享了

某一位，如果我们直接删除这一位的话，可能会影响其他元素

三、BloomFilter的使用

BloomFilter的设计实际上是非常复杂的，但是好在各种编程语言都有对应的实现；比如Java中的Guava中就

有BloomFilter的具体实现；Python中的pybloom包中也有两个类用来实现BloomFilter的功能，简单介绍下Python

中这种数据结构的使用吧

pip install bloom-filter       #安装bloom-filter对应的包

#基本的使用如下
from bloom_filter import BloomFilter

bloom = BloomFilter(max_elements = 10000,error_rate = 0.1)
#max_elements是其存储的最大元素数量，error_rate是误判率

# BloomFilter为空时，测试test_key是否存在
assert "test-key" in bloom is False     #不存在

# 添加元素
bloom.add("test-key")

# 再次查询是否存在
assert "test-key" in bloom is True  #存在

四、BloomFilter的典型应用

  • 网页爬虫中，避免爬取相同的URL地址

  • 反垃圾邮件，从数十亿个垃圾邮件列表中判断某邮箱是否是垃圾邮箱

  • 缓存击穿，将已经存在的缓存置于布隆过滤器中，如果访问不存在的缓存可以迅速判断