说明

可以pip install pybloom,使用pybloom中的BloomFilter进行实现

>>> from pybloom import BloomFilter
>>> f = BloomFilter(capacity=1000, error_rate=0.001) # capacity是容量, error_rate 是能容忍的误报率
>>> f.add('Traim304') # 当不存在该元素,返回False
False
>>> f.add('Traim304') # 若存在,返回 True
True
>>> 'Traim304' in f # 值得注意的是若返回 True。该元素可能存在, 也可能不存在。过滤器能容许存在一定的错误
True
>>> 'Jacob' in f # 但是 False。则必定不存在
False
>>> len(f) # 当前存在的元素
1

>>> f = BloomFilter(capacity=1000, error_rate=0.001) 
>>> from pybloom import ScalableBloomFilter
>>> sbf = ScalableBloomFilter(mode=ScalableBloomFilter.SMALL_SET_GROWTH)
>>> # sbf.add() 与 BloomFilter 同

个人模拟实现布隆过滤器

from bitarray import bitarray
import mmh3
class BloomFilter(set):
    def __init__(self,size,hash_count):
        #size:the num of the bitarray
        #hash_count:the num of hash function
        super(BloomFilter,self).__init__()
        self.bit_array = bitarray(size)
        self.bit_array.setall(0) #初始化为0
        self.size = size
        self.hash_count = hash_count

    def __len__(self): # len()时调用
        return self.size

    def __iter__(self): # 迭代时调用
        return iter(self.bit_array)

    def add(self,item):
        for i in range(self.hash_count):
            index = mmh3.hash(item,i,signed = False) % self.size
            self.bit_array[index] = 1
        return self

    def __contains__(self,item): # 使用in时调用
        out = True
        for i in range(self.hash_count):
            index = mmh3.hash(item,i,signed = False)%self.size
            if bit_array[index] == 0:
                out = False
                
        return out