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

java.lang.Object
  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:

Dimitris Andreou, Kevin Bourrillion

See Also:

Serialized Form

Method Summary

BloomFilter<T>	copy() Creates a new BloomFilter that's a copy of this instance.
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	equals(Object o)
double	expectedFalsePositiveProbability() Returns the probability that mightContain(Object) will erroneously return true for an object that has not actually been put in the BloomFilter.
int	hashCode()
boolean	mightContain(T object) Returns true if the element might have been put in this Bloom filter, false if this is definitely not the case.
boolean	put(T object) Puts an element into this BloomFilter.

Methods inherited from class java.lang.Object

clone, finalize, getClass, notify, notifyAll, toString, wait, wait, wait

Method Detail

copy

public BloomFilter<T> copy()

Creates a new BloomFilter that's a copy of this instance. The new instance is equal to this instance but shares no mutable state.

Since:

12.0

mightContain

public boolean mightContain(T object)

Returns true if the element might have been put in this Bloom filter, false if this is definitely not the case.

put

public boolean put(T object)

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

Returns:

true if the bloom filter's bits changed as a result of this operation. If the bits changed, this is definitely the first time object has been added to the filter. If the bits haven't changed, this might be the first time object has been added to the filter. Note that put(t) always returns the opposite result to what mightContain(t) would have returned at the time it is called."

Since:

12.0 (present in 11.0 with void return type})

expectedFalsePositiveProbability

public double expectedFalsePositiveProbability()

Returns the probability that mightContain(Object) will erroneously return true for an object that has not actually been put in the BloomFilter.

Ideally, this number should be close to the falsePositiveProbability parameter passed in create(Funnel, int, double), or smaller. If it is significantly higher, it is usually the case that too many elements (more than expected) have been put in the BloomFilter, degenerating it.

equals

public boolean equals(Object o)

This implementation uses reference equality to compare funnels.

Overrides:

equals in class Object

hashCode

public int hashCode()

Overrides:

hashCode in class Object

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.

It is recommended the funnel is implemented as a Java enum. This has the benefit of ensuring proper serialization and deserialization, which is important since equals(java.lang.Object) also relies on object identity of funnels.

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 BloomFilter

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 BloomFilter