一文搞懂布隆过滤器

>>> all_elements = {'a','b','c','d','e'}
>>> 'a' in all_elements
True
>>> 'f' in all_elements
False
>>>

public class BitMap { // Java中char类型占16bit，也即是2个字节
  private char[] bytes;
  private int nbits;
  
  public BitMap(int nbits) {
    this.nbits = nbits;
    this.bytes = new char[nbits/16+1];
  }

  public void set(int k) {
    if (k > nbits) return;
    int byteIndex = k / 16;
    int bitIndex = k % 16;
    bytes[byteIndex] |= (1 << bitIndex);
  }

  public boolean get(int k) {
    if (k > nbits) return false;
    int byteIndex = k / 16;
    int bitIndex = k % 16;
    return (bytes[byteIndex] & (1 << bitIndex)) != 0;
  }
}

class BitMap(object):
    def __init__(self, max_value):
        """
        使用多个整型元素来储存数据，每个元素4个字节（32位）
        """
        self._size = int((max_value + 31 - 1) / 31)  # 计算需要的字节数，字节数也是数组的大小
        self.array = [0 for i in range(self._size)]  # 数组的元素都初始化为0，每个元素有32位

    @staticmethod
    def get_element_index(num):
        """
        获取该数即将储存的字节在数组中下标
        """
        return num // 31

    @staticmethod
    def get_bit_index(num):
        """
        获取该数在元素中的位下标
        """
        return num % 31

    def set(self, num):
        """
        将该数存在对应的元素的对应位置
        """
        element_index = self.get_element_index(num)
        bit_index = self.get_bit_index(num)
        self.array[element_index] = self.array[element_index] | (1 << bit_index)

    def get(self, num):
        """
        查找该数是否存在与bitmap中
        """
        element_index = self.get_element_index(num)
        bit_index = self.get_bit_index(num)
        if self.array[element_index] & (1 << bit_index):
            return True
        return False

pip install bloom-filter2
pip install pybloom-live
pip install bloompy

>>> import bloompy
>>> bf = bloompy.BloomFilter(error_rate=0.001,element_num=10**3)

# 查询元素是否在过滤器里返回状态标识
# 如果不在里面则插入，返回False表示元素不在过滤器里
>>> bf.add(1) 
False
>>> bf.add(1)
True
>>> 1 in bf
True
>>> bf.exists(1)
True
>>> bf.add([1,2,3])
False
>>> bf.add([1,2,3])
True
>>> [1,2,3] in bf
True
>>> bf.exists([1,2,3])
True

# 将过滤器存储在一个文件里
>>> bf.tofile('filename.suffix')

# 从一个文件里恢复过滤器。自动识别过滤器的种类。
>>> recovered_bf = bloompy.get_filter_fromfile('filename.suffix')

# 或者使用过滤器类的类方法 'fromfile' 来进行过滤器的复原。对应的类只能恢复对应的过滤器
>>> recovered_bf = bloompy.BloomFilter.fromfile('filename.suffix')

# 返回已经插入的元素个数
>>> bf.count
2

# 过滤器的容量
>>> bf.capacity
1000

# 过滤器的位向量
>>> bf.bit_array
bitarray('00....')

# 过滤器位数组长度
>>> bf.bit_num
14400

# 过滤器的哈希种子，默认是素数，可修改
>>> bf.seeds
[2, 3, 5, 7, 11,...]

# 过滤器哈希函数个数
>>> bf.hash_num
10

>>> import  bloompy
>>> cbf  = bloompy.CountingBloomFilter(error_rate=0.001,element_num=10**3)

# 与标准布隆过滤器一样
>>> cbf.add(12)
False
>>> cbf.add(12)
True
>>> 12 in cbf
True
>>> cbf.count
1

# 查询元素状态返回标识，如果元素存在过滤器里则删除
>>> cbf.delete(12)
True
>>> cbf.delete(12)
False
>>> 12 in cbf
False
>>> cbf.count
0

# 从文件中恢复过滤器
>>> recovered_cbf = bloompy.CountingBloomFilter.fromfile('filename.suffix')

>>> import bloompy
>>> sbf = bloompy.ScalableBloomFilter(error_rate=0.001,initial_capacity=10**3)

# 默认初次可以设置容量1000
>>> len(sbf)
0
>>> 12 in sbf
False
>>> sbf.add(12)
False
>>> 12 in sbf 
True
>>> len(sbf)
1
>>> sbf.filters
[<bloompy.BloomFilter object at 0x000000000B6F5860>]
>>> sbf.capacity
1000

#当过滤器的元素个数达到容量极限时，过滤器会自动增加内置的标准过滤器，
#每次增加2倍容量，自动实现扩容
>>> for i in range(1000):
        sbf.add(i)
>>> 600 in sbf
True
>>> len(sbf)
2
>>> sbf.filters
[<bloompy.BloomFilter object at 0x000000000B6F5860>, <bloompy.BloomFilter object at 0x000000000B32F748>]
>>> sbf.capacity
3000

# 从文件中恢复过滤器
>>> recovered_sbf = bloompy.ScalableBloomFilter.fromfile('filename.suffix')

>>> import bloompy
>>> scbf = bloompy.SCBloomFilter(error_rate=0.001,initial_capacity=10**3)

>>> scbf.add(1)
False
>>> 1 in scbf
True
>>> scbf.delete(1)
True
>>> 1 in scbf
False
>>> len(scbf)
1
>>> scbf.filters
[<bloompy.CountingBloomFilter object at 0x000000000B6F5828>]

# 插入元素使其达到过滤器当前容量极限值
>>> for i in range(1100):
        scbf.add(i)
>>> len(scbf)
2
>>> scbf.filters
[<bloompy.CountingBloomFilter object at 0x000000000B6F5828>, <bloompy.CountingBloomFilter object at 0x000000000B6F5898>]

# 从文件中恢复过滤器
>>> recovered_scbf = bloompy.SCBloomFilter.fromfile('filename.suffix')

docker run -p 6379:6379 --name redis-redisbloom redislabs/rebloom:latest

127.0.0.1:6379> BF.ADD newFilter foo
(integer) 1
127.0.0.1:6379> BF.EXISTS newFilter foo
(integer) 1
127.0.0.1:6379> BF.EXISTS newFilter notpresent
(integer) 0
127.0.0.1:6379> BF.MADD myFilter foo bar baz
1) (integer) 1
2) (integer) 1
3) (integer) 1
127.0.0.1:6379> BF.MEXISTS myFilter foo nonexist bar
1) (integer) 1
2) (integer) 0
3) (integer) 1