本文翻译自Bloom filters, fast and simple
简介
每个人都总在胡乱谈论布隆过滤器（bloom filters），但是布隆过滤器究竟是什么、有什么用途？
布隆过滤器是一个空间高效的概率数据结构，用于判断一个元素是否属于一个集合。
操作
布隆过滤器主要支持两种操作：add和query.
query操作用来检查一个元素是否在集合中，它返回一个布尔值：
- true 如果元素可能在集合中
- false 如果元素肯定不在集合中
add操作将一个元素添加到集合中。
在这种简单的布隆过滤器中，删除元素操作会导致false negative，但是一些布隆过滤器变型支持删除元素操作，比如计数过滤器（counting filters）
结构
布隆过滤器的结构
布隆过滤器的内部实现使用一个bit数组和多个不同的hash函数。
例子
假设有一个大小为100的bit数组和3个hash函数。
对于add操作，添加一个单词"Maciej"到布隆过滤器中：
- 先计算这个单词的3个hash值
- 然后把bit数组中相应bit置为1
对于query操作，判断这个单词是否在集合中：
- 计算这个单词的3个hash值
- 如果bit数组相应的3个bit都被置为1，那么认为这个单词在集合中，否则不在集合中
实现
#!/usr/bin/env python
from hashlib import sha256
class Filter(object):
"""A simple bloom filter for lots of int()"""
def __init__(self, array_size=(1 * 1024), hashes=13):
"""Initializes a Filter() object
Expects:
array_size (in bytes): 4 * 1024 for a 4KB filter
hashes (int): for the number of hashes to perform
"""
self.filter = bytearray(array_size) # The filter itself
self.bitcount = array_size * 8 # Bits in the filter
self.hashes = hashes # The number of hashes to use
def _hash(self, value):
"""Creates a hash of an int and yields a generator of hash functions
Expects:
value: int()
Yields:
generator of ints()
"""
# Build an int() around the sha256 digest of int() -> value
digest = int(sha256(value.__str__()).hexdigest(), 16)
for _ in range(self.hashes):
# bitwise AND of the digest and all of the available bit positions
# in the filter
yield digest & (self.bitcount - 1)
# Shift bits in digest to the right, based on 256 (in sha256)
# divided by the number of hashes needed be produced.
# Rounding the result by using int().
# So: digest >>= (256 / 13) would shift 19 bits to the right.
digest >>= (256 / self.hashes)
def add(self, value):
"""Bitwise OR to add value(s) into the self.filter
Expects:
value: generator of digest ints()
"""
for digest in self._hash(value):
# In-place bitwise OR of the filter, position is determined
# by the (digest / 8) digest is described above in self._hash()
# Bitwise OR is undertaken on the value at the location and
# 2 to the power of digest modulo 8. Ex: 2 ** (30034 % 8)
# to grantee the value is <= 128, the bytearray not being able
# to store a value >= 256. Q: Why not use ((modulo 9) -1) then?
self.filter[(digest / 8)] |= (2 ** (digest % 8))
# The purpose here is to spread out the hashes to create a unique
# "fingerprint" with unique locations in the filter array,
# rather than just a big long hash blob.
def query(self, value):
"""Bitwise AND to query values in self.filter
Expects:
value: value to check filter against (assumed int())
"""
# If all() hashes return True from a bitwise AND (the opposite
# described above in self.add()) for each digest returned from
# self._hash return True, else False
return all(self.filter[(digest / 8)] & (2 ** (digest % 8))
for digest in self._hash(value))
if __name__ == "__main__":
bf = Filter()
bf.add(1234)
bf.add(40005)
bf.add(1)
print("Filter size {0} bytes").format(bf.filter.__sizeof__())
print bf.query(1) # True
print bf.query(40005) # True
print bf.query(123) # False
