简单高效的布隆过滤器

迈不过友情╰ 2022-09-18 05:58 50阅读 0赞

本文翻译自[Bloom filters, fast and simple][Bloom filters_ fast and simple]

### 简介 ###

每个人都总在胡乱谈论布隆过滤器（bloom filters），但是布隆过滤器究竟是什么、有什么用途？

> 布隆过滤器是一个空间高效的概率数据结构，用于判断一个元素是否属于一个集合。

### 操作 ###

布隆过滤器主要支持两种操作：add和query.

query操作用来检查一个元素是否在集合中，它返回一个布尔值：

*  true 如果元素可能在集合中
 *  false 如果元素肯定不在集合中

add操作将一个元素添加到集合中。

在这种简单的布隆过滤器中，删除元素操作会导致false negative，但是一些布隆过滤器变型支持删除元素操作，比如计数过滤器（[counting filters][]）

### 结构 ###

![3479982-3d633a4802e3693f.jpeg][]

布隆过滤器的结构

布隆过滤器的内部实现使用一个bit数组和多个不同的hash函数。

### 例子 ###

假设有一个大小为100的bit数组和3个hash函数。

对于add操作，添加一个单词"Maciej"到布隆过滤器中：

1.  先计算这个单词的3个hash值
2.  然后把bit数组中相应bit置为1

对于query操作，判断这个单词是否在集合中：

1.  计算这个单词的3个hash值
2.  如果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

[Bloom filters_ fast and simple]: https://link.jianshu.com?t=http://maciejczyzewski.me/2014/10/18/bloom-filters-fast-and-simple.html
[counting filters]: https://link.jianshu.com?t=http://en.wikipedia.org/wiki/Bloom_filter#Counting_filters
[3479982-3d633a4802e3693f.jpeg]: /images/20220828/73f0c89d09bd4639b3e95e045336b88c.png