bloom_filter 0.2.0+1

  • README.md
  • CHANGELOG.md
  • Installing
  • Versions
  • 40

bloom_filter

Build Status

A stand-alone Bloom filter implementation written in Dart inspired by Java-BloomFilter.

Bloom filters

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.

Examples

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.");
  }
}

Changelog

0.2.0

  • Add salt when creating hashes
  • Turn on strong mode and fix warnings
  • Breaking change - rename contains method to mightContain

0.1.1

  • Fix a typo in the constructor

0.1.0

  • Initial version

1. Depend on it

Add this to your package's pubspec.yaml file:


dependencies:
  bloom_filter: "^0.2.0+1"

2. Install it

You can install packages from the command line:

with pub:


$ pub get

with Flutter:


$ flutter packages get

Alternatively, your editor might support pub get or packages get. Check the docs for your editor to learn more.

3. Import it

Now in your Dart code, you can use:


import 'package:bloom_filter/bloom_filter.dart';
        
Version Uploaded Documentation Archive
0.2.0+1 Oct 31, 2016 Go to the documentation of bloom_filter 0.2.0+1 Download bloom_filter 0.2.0+1 archive
0.2.0 Oct 31, 2016 Go to the documentation of bloom_filter 0.2.0 Download bloom_filter 0.2.0 archive
0.1.1 Oct 11, 2016 Go to the documentation of bloom_filter 0.1.1 Download bloom_filter 0.1.1 archive
0.1.0 Oct 11, 2016 Go to the documentation of bloom_filter 0.1.0 Download bloom_filter 0.1.0 archive

Analysis

We analyzed this package on Apr 9, 2018, and provided a score, details, and suggestions below. Analysis was completed with status completed using:

  • Dart: 2.0.0-dev.46.0
  • pana: 0.10.6

Scores

Popularity:
Describes how popular the package is relative to other packages. [more]
0 / 100
Health:
Code health derived from static analysis. [more]
98 / 100
Maintenance:
Reflects how tidy and up-to-date the package is. [more]
56 / 100
Overall score:
Weighted score of the above. [more]
40
Learn more about scoring.

Platforms

Detected platforms: Flutter, web, other

No platform restriction found in primary library package:bloom_filter/bloom_filter.dart.

Suggestions

  • The description is too short.

    Add more detail about the package, what it does and what is its target use case. Try to write at least 60 characters.

  • Package is pre-v1 release.

    While there is nothing inherently wrong with versions of 0.*.*, it usually means that the author is still experimenting with the general direction API.

  • Fix analysis and formatting issues.

    Analysis or formatting checks reported 2 hints.

    Strong-mode analysis of lib/src/bloom_filter_base.dart gave the following hint:

    line: 52 col: 38
    'UTF8' is deprecated and shouldn't be used.

  • Use analysis_options.yaml.

    Rename old .analysis_options file to analysis_options.yaml.

Dependencies

Package Constraint Resolved Available
Direct dependencies
Dart SDK >=1.8.0 <2.0.0
bit_vector ^0.2.0 0.2.0 0.4.1
crypto ^2.0.1 2.0.2+1
Transitive dependencies
charcode 1.1.1
collection 1.14.9
convert 2.0.1
fixnum 0.10.7
typed_data 1.1.5
Dev dependencies
test >=0.12.0 <0.13.0
uuid ^0.5.3