RollingBloomFilter is a probabilistic "keep track of most recently inserted" set. Construct it with the number of items to keep track of, and a false‐positive rate. Unlike CBloomFilter, by default nTweak is set to a cryptographically secure random value for you. Similarly rather than clear() the method reset() is provided, which also changes nTweak to decrease the impact of false‐positives.
Synopsis
Declared in <common/bloom.h>
class CRollingBloomFilter;Description
contains(item) will always return true if item was one of the last N to 1.5*N insert()'ed ... but may also return true for items that were not inserted.
It needs around 1.8 bytes per element per factor 0.1 of false positive rate. For example, if we want 1000 elements, we'd need:
-
~1800 bytes for a false positive rate of 0.1
-
~3600 bytes for a false positive rate of 0.01
-
~5400 bytes for a false positive rate of 0.001
If we make these simplifying assumptions:
-
logFpRate / log(0.5) doesn't get rounded or clamped in the nHashFuncs calculation
-
nElements is even, so that nEntriesPerGeneration == nElements / 2
Then we get a more accurate estimate for filter bytes:
3/(log(256)*log(2)) * log(1/fpRate) * nElements
Member Functions
Name |
Description |
|
Construct a rolling filter sized for a number of elements and a false‐positive rate. |
Test whether a raw key was recently inserted. |
|
Add a raw key to the filter, evicting older entries as needed. |
|
Clear the filter and re‐randomize the hash seed. |
Created with MrDocs