我最近也走上了这条路；虽然听起来我的应用程序略有不同。我对在大量字符串上近似集合操作很感兴趣。
您确实做出了需要快速位向量的关键观察。根据您想要放入布隆过滤器的内容，您可能还需要考虑所使用的散列算法的速度。你可能会发现这个库很有用。您可能还想修改下面使用的随机数技术，该技术仅对您的密钥进行一次散列。
在非 Java 位数组实现方面：
我使用BitVector构建了我的布隆过滤器。我花了一些时间分析和优化库，并将我的补丁回馈给 Avi。转到该 BitVector 链接并向下滚动到 v1.5 中的致谢以查看详细信息。最后，我意识到性能不是这个项目的目标，并决定不使用它。
这是我躺在身边的一些代码。我可以把它放在 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]
作为对 Parand 的回应，他说“常见的做法似乎是使用 SHA1 之类的东西并将位拆分以形成多个哈希”，虽然从某种意义上说这是常见的做法（PyBloom 也使用它），这可能是正确的，但它仍然没有不是说这是正确的做法；-)
对于布隆过滤器，散列函数的唯一要求是它的输出空间必须在给定预期输入的情况下均匀分布。虽然加密哈希当然可以满足这一要求，但它也有点像用火箭筒射击苍蝇。
而是尝试使用每个输入字节仅使用一个 XOR 和一个乘法的FNV Hash，我估计它比 SHA1 快几百倍:)
FNV 哈希在密码学上不是安全的，但您不需要它。它有稍微不完美的雪崩行为，但你也没有将它用于完整性检查。
关于一致性，请注意第二个链接仅对 32 位 FNV 散列进行卡方检验。最好使用更多位和 FNV-1 变体，它交换 XOR 和 MUL 步骤以获得更好的位分散。对于布隆过滤器，还有一些捕获，例如将输出统一映射到位数组的索引范围。如果可能的话，我会说将位数组的大小四舍五入到最接近的 2 次幂并相应地调整k。这样您可以获得更好的准确性，并且可以使用简单的 XOR 折叠来映射范围。
Additionally, here's a reference explaining why you don't want SHA1 (or any cryptographic hash) when you need a general purpose hash.
最终我找到了 pybloomfiltermap。我没用过，但看起来很合算。
查看阵列模块。
class Bit( object ):
def __init__( self, size ):
self.bits= array.array('B',[0 for i in range((size+7)//8)] )
def set( self, bit ):
b= self.bits[bit//8]
self.bits[bit//8] = b | 1 << (bit % 8)
def get( self, bit ):
b= self.bits[bit//8]
return (b >> (bit % 8)) & 1
FWIW，所有//8and% 8操作都可以替换为>>3and &0x07。这可能会导致稍微更好的速度，但有一些晦涩的风险。
此外，在大多数硬件上更改和'B'更改8应该更快。[在某些硬件上更改为16 可能会更快，但这值得怀疑。]'L'32'H'
It's almost a decade since the most recent answers on here. And times do change.
看起来 2019 年末最受欢迎的维护布隆过滤器包现在是这个：https ://github.com/joseph-fox/python-bloomfilter ，在 PyPi 上作为 pybloom_live 提供：https ://pypi.org/project/pybloom_live /
I've put up a python bloom filter implementation at http://stromberg.dnsalias.org/~strombrg/drs-bloom-filter/
It's in pure python, has good hash functions, good automated tests, a selection of backends (disk, array, mmap, more) and more intuitive arguments to the __init__ method, so you can specify an ideal number of elements and desired maximum error rate, instead of somewhat ethereal, datastructure-specific tunables.