com.google.common.hash
Class BloomFilter<T>

java.lang.Object
  extended by com.google.common.hash.BloomFilter<T>
Type Parameters:
T - the type of instances that the BloomFilter accepts
All Implemented Interfaces:
Serializable

@Beta
public final class BloomFilter<T>
extends Object
implements Serializable

A Bloom filter for instances of T. A Bloom filter offers an approximate containment test with one-sided error: if it claims that an element is contained in it, this might be in error, but if it claims that an element is not contained in it, then this is definitely true.

If you are unfamiliar with Bloom filters, this nice tutorial may help you understand how they work.

Since:
11.0
Author:
Kevin Bourrillion, Dimitris Andreou
See Also:
Serialized Form

Method Summary
static
<T> BloomFilter<T>
create(Funnel<T> funnel, int expectedInsertions)
          Creates a Builder of a BloomFilter, with the expected number of insertions, and a default expected false positive probability of 3%.
static
<T> BloomFilter<T>
create(Funnel<T> funnel, int expectedInsertions, double falsePositiveProbability)
          Creates a Builder of a BloomFilter, with the expected number of insertions and expected false positive probability.
 boolean mightContain(T instance)
          Returns true if the element might have been put in this Bloom filter, false if this is definitely not the case.
 void put(T instance)
          Puts an element into this BloomFilter.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Method Detail

mightContain

public boolean mightContain(T instance)
Returns true if the element might have been put in this Bloom filter, false if this is definitely not the case.


put

public void put(T instance)
Puts an element into this BloomFilter. Ensures that subsequent invocations of mightContain(Object) with the same element will always return true.


create

public static <T> BloomFilter<T> create(Funnel<T> funnel,
                                        int expectedInsertions,
                                        double falsePositiveProbability)
Creates a Builder of a BloomFilter, with the expected number of insertions and expected false positive probability.

Note that overflowing a BloomFilter with significantly more elements than specified, will result in its saturation, and a sharp deterioration of its false positive probability.

The constructed BloomFilter<T> will be serializable if the provided Funnel<T> is.

Parameters:
funnel - the funnel of T's that the constructed BloomFilter<T> will use
expectedInsertions - the number of expected insertions to the constructed BloomFilter<T>; must be positive
falsePositiveProbability - the desired false positive probability (must be positive and less than 1.0)
Returns:
a Builder

create

public static <T> BloomFilter<T> create(Funnel<T> funnel,
                                        int expectedInsertions)
Creates a Builder of a BloomFilter, with the expected number of insertions, and a default expected false positive probability of 3%.

Note that overflowing a BloomFilter with significantly more elements than specified, will result in its saturation, and a sharp deterioration of its false positive probability.

The constructed BloomFilter<T> will be serializable if the provided Funnel<T> is.

Parameters:
funnel - the funnel of T's that the constructed BloomFilter<T> will use
expectedInsertions - the number of expected insertions to the constructed BloomFilter<T>; must be positive
Returns:
a Builder


Copyright © 2010-2011. All Rights Reserved.