python实现简单布隆过滤器

布隆过滤器

布隆过滤器vshash table

布隆过滤器本质上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。

优点：空间效率和查询时间都远远超过一般的算法

缺点：有一定的误识别率和删除困难

对于测试元素，当它验证这个元素所对应的⼆进制位是1的时候，那么它可能存在在布隆过滤器⾥⾯， 当它验证这个元素所对应的⼆进制位只要有⼀个不为1的话，那么我们可以百分之百肯定它不在。

那么接下来要怎么判断它到底是否存在？布隆过滤器只是放在最外⾯当⼀个缓存使的，当⼀个很快速的判断使的。当B查到了之后，布隆过滤器⾥⾯是存在的，那么B会继续到这台机器的DB⾥⾯去查。C不在布隆过滤器中，就不⽤查了。

案例

1. 比特币网络
2. 分布式系统（Map-Reduce) - Hadoop、search engine
   1. 搜索引擎，经常需要把大量的网页信息，图片信息存到整个服务器里面，一般来说，不同的网页是存在不同的集群里面的。那么就先去这个集群的布隆过滤器里面查一下。
3. Redis缓存
4. 垃圾邮件、评论等的过滤

简单实现示例

布隆过滤器主要有构造函数，和add一个元素，search一个元素，三个API需要实现。

构造函数，我们可以假定传入二进制数组的长度（工业实现中可能会传如元素的数量，然后推断出人禁止数组的长度），需要的哈希函数数量。

add的函数签名是 add(s:str) -> None，我们假定查询的是字符串

search是search(s:str) ->bool

示例：

import mmh3
from bitarray import bitarray

class BloomFilter:
    def __init__(self, size: int, hash_num: int):
        self.size = size
        self.hash_num = hash_num
        self.bit_array = bitarray(size)
        self.bit_array.setall(0)

    def add(self, s: str) -> None:
        for seed in range(self.hash_num):
            result = mmh3.hash(s, seed) % self.size
            self.bit_array[result] = 1

    def search(self, s: str) -> bool:
        for seed in range(self.hash_num):
            result = mmh3.hash(s, seed) % self.size
            if not self.bit_array[result]:
                return False
                # Nope
        return True
        # Probably