Expand description
bloom2 implements a 2-level bitmap to provide a sparse, lazily initialised, high performance bloom filter with a reduced memory footprint.
The memory usage of a sparse bloom filter grows proportionally with the load factor of the filter, resulting in substantially smaller memory footprints for filters with average, or low load factors. As bloom filters are typically sized to avoid high load factors in order to minimise false positives, this is highly effective for the typical use case.
The Bloom2
filter provides amortised O(1)
insert, and constant time
O(1)
lookup with a similar average case latency compared to a standard
bloom filter (~30ns on a Core i7 @ 2.60GHz, with a majority of this taken up
by the hashing of values).
The sparse memory behaviour is implemented in the underlying
CompressedBitmap
, which is used as the bit storage for the filter. The
CompressedBitmap
is a fast (~4ns set, 1ns get) space efficient
general-purpose bitmap suitable for use in applications in addition to the
bloom filter.
Features
serde
- enable serialisation with serde, disabled by default
Structs
- A fast, memory efficient, sparse bloom filter.
- Construct
Bloom2
instances with varying parameters. - A sparse, 2-level bitmap with a low memory footprint.
Enums
- FilterSize bounds the allocated size and false-positive rate of a
Bloom2
instance.
Traits
- A trait to abstract bit storage for use in a
Bloom2
filter.