A stand-alone Bloom filter implementation written in Dart inspired by Java-BloomFilter.
Bloom filters are used for set membership tests. They are fast and space-efficient at the cost of accuracy. Although there is a certain probability of error, Bloom filters never produce false negatives.
To create an empty Bloom filter, just call the constructor with the required false positive probability and the number of elements you expect to add to the Bloom filter.
double falsePositiveProbability = 0.1;
int expectedNumberOfElements = 100;
BloomFilter<String> bloomFilter = new
BloomFilter<String>(falsePositiveProbability, expectedNumberOfElements);
The constructor chooses a length and number of hash functions which will provide the given false positive probability (approximately). Note that if you insert more elements than the number of expected elements you specify, the actual false positive probability will rapidly increase.
After the Bloom filter has been created, new elements may be added using the
add
method.
bloomFilter.add("foo");
To check whether an element has been stored in the Bloom filter, use the
mightContain
method.
bloomFilter.mightContain("foo"); // returns true
Keep in mind that the accuracy of this method depends on the false positive
probability. It will always return true for elements which have been added to
the Bloom filter, but it may also return true for elements which have not been
added. The accuracy can be estimated using the
expectedFalsePositiveProbability
getter.
Put together, here is the full example.
import 'package:bloom_filter/bloom_filter.dart';
main() {
double falsePositiveProbability = 0.1;
int expectedSize = 100;
BloomFilter<String> bloomFilter =
new BloomFilter<String>(falsePositiveProbability, expectedSize);
bloomFilter.add("foo");
if (bloomFilter.mightContain("foo")) {
// Always returns true
print("BloomFilter contains foo!");
print(
"Probability of a false positive: ${bloomFilter.expectedFalsePositiveProbability}");
}
if (bloomFilter.mightContain("bar")) {
// Should return false, but could return true
print("There was a false positive.");
}
}