Code Monkey home page Code Monkey logo

java-bloomfilter's Introduction

java-bloomfilter

java-bloomfilter is a stand-alone Bloom filter implementation written in Java. It is intended to be easy to include in existing projects without the overhead of additional libraries. The first version was inspired by a blog entry by Ian Clarke.

The latest version can be downloaded from GitHub.

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.

If you are new to Bloom filters, you can learn more about them in this tutorial. A more comprehensive overview is available from Wikipedia.

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.

There are several other constructors available which provide different levels of control of how the Bloom filter is initialized. You can also specify the Bloom filter parameters directly (bits per element, number of hash functions and number of elements).

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 contains()-method.

bloomFilter.contains("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()-method.

Put together, here is the full example.

double falsePositiveProbability = 0.1;
int expectedSize = 100;

BloomFilter<String> bloomFilter = new BloomFilter<String>(falsePositiveProbability, expectedSize);

bloomFilter.add("foo");

if (bloomFilter.contains("foo")) { // Always returns true
    System.out.println("BloomFilter contains foo!"); 
    System.out.println("Probability of a false positive: " + bloomFilter.expectedFalsePositiveProbability());
}

if (bloomFilter.contains("bar")) { // Should return false, but could return true
    System.out.println("There was a false positive.");
}

Compiling

To compile, run ant from the base directory.

ant

When ant is done, include dist/java-bloomfilter.jar in your project.

Alternatively, java-bloomfilter could be loaded in Netbeans and compiled using the IDE.

If you want to avoid adding another library to your project, all the Bloom filter code is in BloomFilter.java. You may copy this code directly into your project if you leave the LGPL-comment in place and reference the java-bloomfilter web page.

Changes

1.0

  • Improved the speed of the add() and contains()-methods. The speed increase is around 4-5 times on my computer, but the actual increase may vary from system to system.
  • Added benchmark code to test future code optimizations.
  • Fixed a bug in add() where numberOfAddedElements was incorrectly increased twice when adding other elements than byte-arrays. Updated test.
  • Moved project to Github
  • Added javadoc and source jar to build script.

0.9.3

  • New constructor for estimating bitSetSize from a given false positive probability.
  • New constructor for specifying bits per element, elements and hash functions (c, n, k) directly.
  • Added getExpectedBitsPerElement() and getBitsPerElement()

java-bloomfilter's People

Contributors

magnuss avatar

Stargazers

 avatar

Watchers

 avatar  avatar  avatar

Forkers

wjianlin

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    ๐Ÿ–– Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. ๐Ÿ“Š๐Ÿ“ˆ๐ŸŽ‰

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google โค๏ธ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.