it.unimi.dsi.mg4j.util
Class BloomFilter

java.lang.Object
  extended byit.unimi.dsi.mg4j.util.BloomFilter
All Implemented Interfaces:
Serializable

public class BloomFilter
extends Object
implements Serializable

A Bloom filter.

Instances of this class represent a set of character sequences (with false positives) using a Bloom filter. Because of the way Bloom filters work, you cannot remove elements.

Bloom filters have an expected error rate, depending on the number of hash functions used, on the filter size and on the number of elements in the filter. This implementation uses a variable optimal number of hash functions, depending on the expected number of elements. More precisely, a Bloom filter for n character sequences with d hash functions will use ln 2 dn ≈ 1.44 dn bits; false positives will happen with probability 2-d.

Hash functions are generated at creation time using universal hashing. Each hash function uses NUMBER_OF_WEIGHTS random integers, which are cyclically multiplied by the character codes in a character sequence. The resulting integers are XOR-ed together.

This class exports access methods that are very similar to those of Set, but it does not implement that interface, as too many non-optional methods would be unimplementable (e.g., iterators).

Author:
Sebastiano Vigna
See Also:
Serialized Form

Field Summary
 int d
          The number of hash functions used by this filter.
 int m
          The number of bits in this filter.
static int NUMBER_OF_WEIGHTS
          The number of weights used to create hash functions.
 
Constructor Summary
BloomFilter(int n, int d)
          Creates a new Bloom filter with given number of hash functions and expected number of elements.
 
Method Summary
 boolean add(CharSequence s)
          Adds a character sequence to the filter.
 boolean contains(CharSequence s)
          Checks whether the given character sequence is in this filter.
 int size()
          The number of character sequences in the filter.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

NUMBER_OF_WEIGHTS

public static final int NUMBER_OF_WEIGHTS
The number of weights used to create hash functions.

See Also:
Constant Field Values

m

public final int m
The number of bits in this filter.


d

public final int d
The number of hash functions used by this filter.

Constructor Detail

BloomFilter

public BloomFilter(int n,
                   int d)
Creates a new Bloom filter with given number of hash functions and expected number of elements.

Parameters:
n - the expected number of elements.
d - the number of hash functions; if the filter add not more than n elements, false positives will happen with probability 2-d.
Method Detail

size

public int size()
The number of character sequences in the filter.

Returns:
the number of character sequences in the filter (but see contains(CharSequence)).

contains

public boolean contains(CharSequence s)
Checks whether the given character sequence is in this filter.

Note that this method may return true on a character sequence that is has not been added to the filter. This will happen with probability 2-d, where d is the number of hash functions specified at creation time, if the number of the elements in the filter is less than n, the number of expected elements specified at creation time.

Parameters:
s - a character sequence.
Returns:
true if the sequence is in the filter (or if a sequence with the same hash sequence is in the filter).

add

public boolean add(CharSequence s)
Adds a character sequence to the filter.

Parameters:
s - a character sequence.
Returns:
true if the character sequence was not in the filter (but see contains(CharSequence)).