现代高性能的布隆过滤器在Python中如何实现？

59 投票

6 回答

20735 浏览

数据工程师

提问于 2025-04-11 19:19

我在找一个能在生产环境中使用的布隆过滤器的实现，最好是用Python写的，能够处理比较大的数据量（比如说1亿到10亿个项目，并且假阳性率要在0.01%以内）。

Pybloom是一个选择，但它似乎有点过时了，因为在Python 2.5上经常会出现弃用警告。Joe Gregorio也有一个实现。

我的要求是查找速度要快，而且要稳定。我也愿意为特别好的C/C++实现创建Python接口，或者如果有好的Java实现，也可以考虑用Jython。

如果没有这样的实现，有没有推荐的位数组或位向量表示方法，能够处理大约16亿位的数据？

数据结构生产环境 jython 高性能计算布隆过滤器假阳性率位数组 C/C++接口

6 个回答

针对Parand提到的“常见做法似乎是使用像SHA1这样的东西，并将位分开形成多个哈希”，虽然这在某种程度上是对的（PyBloom也使用这种方法），但这并不意味着这是正确的做法；）

对于布隆过滤器来说，哈希函数唯一的要求是它的输出必须在预期输入下均匀分布。虽然加密哈希确实满足这个要求，但这就像用火箭筒打苍蝇一样。

不如试试FNV哈希，它对每个输入字节只使用一次异或和一次乘法，我估计它的速度比SHA1快几百倍呢 :)

FNV哈希并不是加密安全的，但你并不需要它具备这个特性。它有一点点不完美的雪崩效应，但你也不是用它来检查数据完整性的。

关于均匀性，注意第二个链接只对32位FNV哈希进行了卡方检验。最好使用更多位数和FNV-1变体，它将异或和乘法的步骤交换，以获得更好的位分散性。对于布隆过滤器，还有一些额外的注意事项，比如将输出均匀映射到位数组的索引范围。如果可能的话，我建议将位数组的大小调整到最接近的2的幂，并相应调整k。这样可以提高准确性，并且你可以使用简单的异或折叠来映射范围。

另外，这里有一个参考资料，解释了为什么在需要通用哈希时不想使用SHA1（或任何加密哈希）。

回答于 2025-04-11 由 Python大师

分享举报

我最近也走过这条路，不过听起来我的应用稍微有点不同。我想要对大量字符串进行集合操作的近似计算。

你提到的一个关键点是需要一个快速的位向量。根据你想在布隆过滤器中放入什么内容，你可能还需要考虑使用的哈希算法的速度。你可以参考这个库，它可能对你有帮助。你也可以尝试下面提到的随机数技术，这种方法只对你的键进行一次哈希。

关于非Java的位数组实现：

Boost有dynamic_bitset
Java内置有BitSet

我使用BitVector构建了我的布隆过滤器。我花了一些时间来分析和优化这个库，并把我的补丁贡献给了Avi。你可以去那个BitVector的链接，往下滚动到v1.5的致谢部分查看详细信息。最后，我意识到性能并不是这个项目的目标，所以决定不使用它。

这里有一些我之前写的代码。我可能会把它放到google code上的python-bloom，欢迎提出建议。

from BitVector import BitVector
from random import Random
# get hashes from http://www.partow.net/programming/hashfunctions/index.html
from hashes import RSHash, JSHash, PJWHash, ELFHash, DJBHash


#
# ryan.a.cox@gmail.com / www.asciiarmor.com
#
# copyright (c) 2008, ryan cox
# all rights reserved 
# BSD license: http://www.opensource.org/licenses/bsd-license.php
#

class BloomFilter(object):
    def __init__(self, n=None, m=None, k=None, p=None, bits=None ):
        self.m = m
        if k > 4 or k < 1:
            raise Exception('Must specify value of k between 1 and 4')
        self.k = k
        if bits:
            self.bits = bits
        else:
            self.bits = BitVector( size=m )
        self.rand = Random()
        self.hashes = []
        self.hashes.append(RSHash)
        self.hashes.append(JSHash)
        self.hashes.append(PJWHash)
        self.hashes.append(DJBHash)

        # switch between hashing techniques
        self._indexes = self._rand_indexes
        #self._indexes = self._hash_indexes

    def __contains__(self, key):
        for i in self._indexes(key): 
            if not self.bits[i]:
                return False    
        return True 

    def add(self, key):
        dupe = True 
        bits = []
        for i in self._indexes(key): 
            if dupe and not self.bits[i]:
                dupe = False
            self.bits[i] = 1
            bits.append(i)
        return dupe

    def __and__(self, filter):
        if (self.k != filter.k) or (self.m != filter.m): 
            raise Exception('Must use bloom filters created with equal k / m paramters for bitwise AND')
        return BloomFilter(m=self.m,k=self.k,bits=(self.bits & filter.bits))

    def __or__(self, filter):
        if (self.k != filter.k) or (self.m != filter.m): 
            raise Exception('Must use bloom filters created with equal k / m paramters for bitwise OR')
        return BloomFilter(m=self.m,k=self.k,bits=(self.bits | filter.bits))

    def _hash_indexes(self,key):
        ret = []
        for i in range(self.k):
            ret.append(self.hashes[i](key) % self.m)
        return ret

    def _rand_indexes(self,key):
        self.rand.seed(hash(key))
        ret = []
        for i in range(self.k):
            ret.append(self.rand.randint(0,self.m-1))
        return ret

if __name__ == '__main__':
    e = BloomFilter(m=100, k=4)
    e.add('one')
    e.add('two')
    e.add('three')
    e.add('four')
    e.add('five')        

    f = BloomFilter(m=100, k=4)
    f.add('three')
    f.add('four')
    f.add('five')
    f.add('six')
    f.add('seven')
    f.add('eight')
    f.add('nine')
    f.add("ten")        

    # test check for dupe on add
    assert not f.add('eleven') 
    assert f.add('eleven') 

    # test membership operations
    assert 'ten' in f 
    assert 'one' in e 
    assert 'ten' not in e 
    assert 'one' not in f         

    # test set based operations
    union = f | e
    intersection = f & e

    assert 'ten' in union
    assert 'one' in union 
    assert 'three' in intersection
    assert 'ten' not in intersection
    assert 'one' not in intersection

另外，在我的情况下，我发现为BitVector提供一个更快的count_bits函数是很有用的。把这段代码放到BitVector 1.5中，它应该能给你提供一个更高效的位计数方法：

def fast_count_bits( self, v ):
    bits = (
            0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
            1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
            1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
            2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
            1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
            2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
            2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
            3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
            1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
            2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
            2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
            3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
            2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
            3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
            3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
            4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8 )

    return bits[v & 0xff] + bits[(v >> 8) & 0xff] + bits[(v >> 16) & 0xff] + bits[v >> 24]

回答于 2025-04-11 由 Python大师

分享举报

最后我找到了 pybloomfiltermap。我还没用过它，但看起来它应该能满足我的需求。

回答于 2025-04-11 由 Python大师

分享举报

现代高性能的布隆过滤器在Python中如何实现？

6 个回答

撰写回答