一个快速、简单、轻量级的 Bloom 过滤器库,适用于 Python,由 Rust 实现。
A fast, simple and lightweight
Bloom filter library for
Python, implemented in Rust. It's designed to be as pythonic as possible,
mimicking the built-in set type where it can, and works with any
hashable object. While it's a new library (this project was started in
2023), it's currently the fastest option for Python by
a long shot (see the section
Benchmarks). Releases are published on
PyPI.
This library defines only one class, which can be used as follows:
…To prevent death and destruction, the bitwise set operations only work on
filters where all parameters are equal (including the hash functions being
the exact same object). Because this is a Bloom filter, the __contains__
and approx_items methods are probabilistic, as are all the methods that
compare two filters (such as __le__ and issubset).
Python's built-in hash function is designed to be fast, not maximally collision-resistant, so if your program depends on the false positive rate being perfectly correct, you may want to supply your own hash function. This is especially the case when working with very large filters (more than a few tens of millions of items) or when false positives are very costly and could be exploited by an adversary. Just make sure that your hash function returns an integer between -2^127 and 2^127 - 1. Feel free to use the following example in your own code:
from rbloom import Bloom
from hashlib import sha256
from pickle import dumps
def hash_func(obj):
h = sha256(dumps(obj)).digest()
# use sys.byteorder instead of "big" for a small speedup when
# reproducibility across machines isn't a concern
return int.from_bytes(h[:16], "big", signed=True)
bf = Bloom(100_000_000, 0.01, hash_func)When you throw away Python's built-in hash function and start hashing serialized representations of objects, however, you open up a breach into the scary realm of the unpythonic:
1, 1.0, 1 + 0j and True will suddenly no longer
be equal.Making you supply your own hash function in this case is a deliberate design decision intended to show you what you're doing and prevent you from shooting yourself in the foot.
Also note that using a custom hash will incur a performance penalty over using the built-in hash.
The save and load methods, along with their byte-oriented counterparts
save_bytes and load_bytes, allow you to save and load filters to and
from disk/Python bytes objects. However, as the built-in hash function's
salt changes between invocations of Python, they only work on filters with
custom hash functions. Note that it is your responsibility to ensure that
the hash function you supply to the loading functions is the same as the
one originally used by the filter you're loading!
bf = Bloom(10_000, 0.01, some_hash_func)
bf.add("hello")
bf.add("world")
# saving to a file
bf.save("bf.bloom")
# loading from a file
loaded_bf = Bloom.load("bf.bloom", some_hash_func)
assert loaded_bf == bf
# saving to bytes
bf_bytes = bf.save_bytes()
# loading from bytes
loaded_bf_from_bytes = Bloom.load_bytes(bf_bytes, some_hash_func)
assert loaded_bf_from_bytes == bfThe size of the file is bf.size_in_bits / 8 + 8 bytes.
Statement of attribution: Bloom filters were originally proposed in (Bloom, 1970). Furthermore, this implementation makes use of a constant recommended by (L'Ecuyer, 1999) for redistributing the entropy of a single hash over multiple integers using a linear congruential generator.
暂无开放 Issues,或尚未同步最近议题。