bloom_filter 0.2.0+1

  • README.md
  • CHANGELOG.md
  • Example
  • Installing
  • Versions
  • 0

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

example/bloom_filter_example.dart

// Copyright (c) 2016, kseo. All rights reserved. Use of this source code
// is governed by a BSD-style license that can be found in the LICENSE file.

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

Use this package as a library

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

Alternatively, your editor might support pub 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
Popularity:
Describes how popular the package is relative to other packages. [more]
0
Health:
Code health derived from static analysis. [more]
--
Maintenance:
Reflects how tidy and up-to-date the package is. [more]
--
Overall:
Weighted score of the above. [more]
0
Learn more about scoring.

The package version is not analyzed, because it does not support Dart 2. Until this is resolved, the package will receive a health and maintenance score of 0.

Analysis issues and suggestions

Support Dart 2 in pubspec.yaml.

The SDK constraint in pubspec.yaml doesn't allow the Dart 2.0.0 release. For information about upgrading it to be Dart 2 compatible, please see https://www.dartlang.org/dart-2#migration.

Maintenance issues and suggestions

Running dartdoc failed. (-10 points)

Make sure dartdoc runs without any issues.

Dependencies

Package Constraint Resolved Available
Direct dependencies
Dart SDK >=1.8.0 <2.0.0