布隆过滤器

概念

布隆过滤器是概率型数据结构，由一个二进制向量和一系列随机映射函数组成。它可以用于检索一个元素是否在一个集合中。
实现过程
1. 定义向量长度，并赋初值为0.
2. 定义N个hash函数，并指定个数(1,N)
3. 将需要存储的值经过n个hash计算得出的值作为key来修改向量的值(0=>1)
4. 查询某个变量值是否不存在布隆过滤器里，只需要看它的hash值所对应的向量值是否为0，如果有一个为0，则一定不存在。如果全部为1，也不能证明该变量值一定在布隆过滤器里。
图例展示
- 初始化向量，并赋予初值为0
- 添加数据
- 检查数据
- 获取结论
  
  只能判断这个数据完全不存在，但是不能完全判断其存在。
优势/劣势
- 优势
  1. 布隆过滤器存储空间和插入/查询时间都是常数。
  2. Hash函数相互之间没有关系，方便由硬件并行实现。
  3. 布隆过滤器不需要存储元素本身，在某些对保密要求非常严格的场合有优势。
- 劣势
  1. 误差率
  2. 难以删除
删除在布隆过滤器的值
- 通过引用计数来实现，也就是说在hash值所对应的向量值采取引用计数方式，如果某个hash值是这个向量所对应的索引，则给它加1。如果要删除这个hash值所对应的向量的话，就看其索引值是否为0.如果不是0，就不能删除，否则可以删除。
- 删除整个布隆过滤器，重新在添加数据。

代码实现

安装 mmh3 pip install mmh3
安装bitarray pip install bitarray

from bitarray import bitarray
import mmh3
# 布隆过滤器实现类
class BloomFilter(set):
		# 初始化函数，定义向量的长度，和hash的次数
    def __init__(self, size, hash_count):
        super(BloomFilter, self).__init__()
        self.bit_array = bitarray(size)
        self.bit_array.setall(0)
        self.size = size
        self.hash_count = hash_count
		
    def __len__(self):
        return self.size

    def __iter__(self):
        return iter(self.bit_array)
		# 添加 数据到 布隆过滤器中
    def add(self, item):
        for ii in range(self.hash_count):
            index = mmh3.hash(item, ii) % self.size
            self.bit_array[index] = 1
        return self
		# 检查 hash值是否在向量中
    def __contains__(self, item):
        out = True
        for ii in range(self.hash_count):
            index = mmh3.hash(item, ii) % self.size
            if self.bit_array[index] == 0:
                out = False
        return out

# 启动文件
if __name__ == '__main__':
    bloom = BloomFilter(100, 10)
    companys = ['sina','tencent','alibaba']
    # 将数据添加到布隆过滤器中
    for company in companys:
        bloom.add(company)
    # 查看你添加的公司是否都已已经添加到布隆过滤器中？
    for company in companys:
        if company in bloom:
            print('{} 已添加'.format(company))
        else:
            print('{} 有问题'.format(company))
    # 查看其他公司是否也在布隆过滤器里
    other_companys = ['baidu','sina','facebook','twitter','microsoft','google','kingston','dajiang','douyu','momo','yy']
    for other_company in other_companys:
        if other_company in bloom:
            print('{} 可能在布隆过滤器里'.format(other_company))
        else:
            print('{} 一定不在布隆过滤器里'.format(other_company))