前言
这一篇我们讲一下布隆过滤器，并给出Python实现的代码。
一句话说明布隆过滤器的作用就是:判断一个元素是否在一个集合中，通常这个集合会很大。
下面引用一段话：
比如说，一个象 Yahoo,Hotmail 和 Gmai 那样的公众电子邮件（email）提供商，总是需要过滤来自发送垃圾邮件的人（spamer）的垃圾邮件。一个办法就是记录下那些发垃圾邮件的 email 地址。由于那些发送者不停地在注册新的地址，全世界少说也有几十亿个发垃圾邮件的地址，将他们都存起来则需要大量的网络服务器。如果用哈希表，每存储一亿 个 email 地址， 就需要 1.6GB 的内存（用哈希表实现的具体办法是将每一个 email 地址对应成一个八字节的信息指纹， 然后将这些信息指纹存入哈希表，由于哈希表的存储效率一般只有 50%，因此一个 email 地址需要占用十六个字节。一亿个地址大约要 1.6GB， 即十六亿字节的内存）。因此存贮几十亿个邮件地址可能需要上百 GB 的内存。除非是超级计算机，一般服务器是无法存储的。
这个时候我们就需要介绍布隆过滤器了（布隆过滤器的原理很简单，下面就把代码贴出一下，大家可以结合代码来看）。
代码及运行结果
看代码之前首先看一下一个python库bitarray的用法，他可以让你像操作数组一样操作bitarray。

再来看一下mmh3的hash用法。

接下来就是看一下完整的代码实现，代码中都包含了注释了，大家复制到本地自己看一下，运行一下。

[Python] 纯文本查看 复制代码

import mmh3
from bitarray import bitarray
# Implement a simple bloom filter with murmurhash algorithm.
# Bloom filter is used to check wether an element exists in a collection, 
# and it has a good performance in big data situation.
# It may has positive rate depend on hash functions and elements count.


class BloomFilter(object):
    def __init__(self,BIT_SIZE, HASH_NUM):
        # 初始化布隆过滤器,生成一下全0的 bitarray
        bit_array = bitarray(BIT_SIZE)
        bit_array.setall(0)
        self.bit_array = bit_array
        
    def add(self, url):
        # 添加一个url,同时获取这个url的对应的bitarray的位置
        point_list = self.get_postions(url)
        for b in point_list:
            self.bit_array[b] = 1
            
    def contains(self, url):
        # 验证这个url是否存在在集合中
        point_list = self.get_postions(url)
        result = True
        for b in point_list:[b]
            result = result and self.bit_array[b]
        return result
    
    def get_postions(self, url):
        # 一个url获取HASH_NUM个位置,之后会把这些位置变为1
        return [mmh3.hash(url, i) % BIT_SIZE for i in range(HASH_NUM)]

if __name__ == '__main__':
    BIT_SIZE = 5000000
    HASH_NUM = 10
    # 类的实例化
    bloom_filter = BloomFilter(BIT_SIZE, HASH_NUM)
    urls = ['www.baidu.com','mathpretty.com','sina.com', 'qaz', 'wsx', 'edc',
            'rfv']
    urls_check = ['mathpretty.com','zhihu.com','qaz', 'wsx']
    for url in urls:
        bloom_filter.add(url)
    for url_check in urls_check:
        result = bloom_filter.contains(url_check)
        print('被检测的网址 : ',url_check,'/ 是否被包含在原集合中 : ',result)

下面来看一下代码执行结果：

奈斯