com.duprasville.guava.probably

Class BloomFilter<E>

java.lang.Object

com.duprasville.guava.probably.BloomFilter<E>

Type Parameters:

E - the type of instances that the BloomFilter accepts.

All Implemented Interfaces:

ProbabilisticFilter<E>, Serializable

public final class BloomFilter<E>
extends Object
implements ProbabilisticFilter<E>, Serializable

A Bloom filter for instances of E that implements the ProbabilisticFilter interface.

This implementation is backed by Google Guava's BloomFilter. From Guava:

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.

The false positive probability (FPP) of a bloom filter is defined as the probability that contains(Object) will erroneously return true for an object that has not actually been put in the BloomFilter.

Author:

Brian Dupras, Guava Authors (underlying BloomFilter implementation)

See Also:

com.google.common.hash.BloomFilter, ProbabilisticFilter, Serialized Form

Method Summary

Methods

Modifier and Type	Method and Description
boolean	add(E e) Adds the specified element to this filter.
boolean	addAll(Collection<? extends E> c) Adds all of the elements in the specified collection to this filter.
boolean	addAll(ProbabilisticFilter<E> f) Combines this filter with another compatible filter.
long	capacity() Returns the number of elements this filter can represent at its requested FPP.
void	clear() Removes all of the elements from this filter.
boolean	contains(E e) Returns true if this filter might contain the specified element, false if this is definitely not the case.
boolean	containsAll(Collection<? extends E> c) Returns true if this filter might contain all of the elements of the specified collection (optional operation).
boolean	containsAll(ProbabilisticFilter<E> f) Not supported.
static <T> BloomFilter<T>	copyOf(BloomFilter<T> f) Creates a new BloomFilter that's a copy of this instance.
static <T> BloomFilter<T>	create(com.google.common.hash.Funnel<T> funnel, long capacity) Creates a BloomFilter with the expected number of insertions and a default expected false positive probability of 3%.
static <T> BloomFilter<T>	create(com.google.common.hash.Funnel<T> funnel, long capacity, double fpp) Creates a BloomFilter with the expected number of insertions and expected false positive probability.
double	currentFpp() Returns the current false positive probability (FPP) of this filter.
boolean	equals(Object object)
double	fpp() Returns the intended FPP limit of this filter.
int	hashCode()
boolean	isCompatible(ProbabilisticFilter<E> f) Returns true if the specified filter is compatible with this filter.
boolean	isEmpty() Returns true if this filter contains no elements.
boolean	remove(E e) Not supported.
boolean	removeAll(Collection<? extends E> c) Not supported.
boolean	removeAll(ProbabilisticFilter<E> f) Not supported.
long	size() Returns the number of elements contained in this filter (its cardinality).
long	sizeLong() Returns the number of elements contained in this filter (its cardinality).

Methods inherited from class java.lang.Object

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

Method Detail

create

@CheckReturnValue
public static <T> BloomFilter<T> create(com.google.common.hash.Funnel<T> funnel,
                                         long capacity,
                                         double fpp)

Creates 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 will be serializable if the provided Funnel is.

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

Parameters:

funnel - the funnel of T's that the constructed BloomFilter will use

capacity - the number of expected insertions to the constructed BloomFilter; must be positive

fpp - the desired false positive probability (must be positive and less than 1.0)

Returns:

a BloomFilter

See Also:

com.google.common.hash.BloomFilter#create(com.google.common.hash.Funnel, int, double)

create

@CheckReturnValue
public static <T> BloomFilter<T> create(com.google.common.hash.Funnel<T> funnel,
                                         long capacity)

Creates 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 objects than specified, will result in its saturation, and a sharp deterioration of its false positive probability.

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

It is recommended that the funnel be 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 will use

capacity - the number of expected insertions to the constructed BloomFilter; must be positive

Returns:

a BloomFilter

See Also:

com.google.common.hash.BloomFilter#create(com.google.common.hash.Funnel, int)

add

public boolean add(E e)

Adds the specified element to this filter. A return value of true ensures that contains(Object) given e will also return true.

Specified by:

add in interface ProbabilisticFilter<E>

Parameters:

e - element to be added to this filter

Returns:

always true as com.google.common.hash.BloomFilter cannot fail to add an object

Throws:

NullPointerException - if the specified element is null

See Also:

contains(Object), addAll(Collection), addAll(ProbabilisticFilter), com.google.common.hash.BloomFilter#put(T)

addAll

public boolean addAll(ProbabilisticFilter<E> f)

Combines this filter with another compatible filter. The mutations happen to this instance. Callers must ensure this filter is appropriately sized to avoid saturating it or running out of space.

Specified by:

addAll in interface ProbabilisticFilter<E>

Parameters:

f - filter to be combined into this filter - f is not mutated

Returns:

true if the operation was successful, false otherwise

Throws:

NullPointerException - if the specified filter is null

IllegalArgumentException - if isCompatible(ProbabilisticFilter) == false

See Also:

add(Object), addAll(Collection), contains(Object)

addAll

public boolean addAll(Collection<? extends E> c)

Adds all of the elements in the specified collection to this filter. The behavior of this operation is undefined if the specified collection is modified while the operation is in progress.

Specified by:

addAll in interface ProbabilisticFilter<E>

Parameters:

c - collection containing elements to be added to this filter

Returns:

true if all elements of the collection were successfully added, false otherwise

Throws:

NullPointerException - if the specified collection contains a null element, or if the specified collection is null

See Also:

add(Object), addAll(ProbabilisticFilter), contains(Object)

contains

public boolean contains(E e)

Returns true if this filter might contain the specified element, false if this is definitely not the case.

Specified by:

contains in interface ProbabilisticFilter<E>

Parameters:

e - element whose containment in this filter is to be tested

Returns:

true if this filter might contain the specified element, false if this is definitely not the case.

Throws:

ClassCastException - if the type of the specified element is incompatible with this filter (optional)

NullPointerException - if the specified element is null and this filter does not permit null elements

See Also:

containsAll(Collection), containsAll(ProbabilisticFilter), add(Object), remove(Object), com.google.common.hash.BloomFilter#mightContain(T)

currentFpp

public double currentFpp()

Returns the current false positive probability (FPP) of this filter.

Specified by:

currentFpp in interface ProbabilisticFilter<E>

Returns:

the probability that contains(Object) will erroneously return true given an element that has not actually been added to the filter.

See Also:

fpp(), com.google.common.hash.BloomFilter#put(T)

isCompatible

public boolean isCompatible(ProbabilisticFilter<E> f)

Returns true if the specified filter is compatible with this filter. f is considered compatible if this filter can use it in combinatoric operations (e.g. addAll(ProbabilisticFilter), containsAll(ProbabilisticFilter)). For two bloom filters to be compatible, they must:

• not be the same instance
• have the same number of hash functions
• have the same bit size
• have the same strategy
• have equal funnels

Specified by:

isCompatible in interface ProbabilisticFilter<E>

Parameters:

f - filter to check for compatibility with this filter

Returns:

true if the specified filter is compatible with this filter

Throws:

NullPointerException - if the specified filter is null

See Also:

addAll(ProbabilisticFilter), containsAll(ProbabilisticFilter), removeAll(ProbabilisticFilter), com.google.common.hash.BloomFilter#isCompatible(com.google.common.hash.BloomFilter)

containsAll

public boolean containsAll(Collection<? extends E> c)

Returns true if this filter might contain all of the elements of the specified collection (optional operation). More formally, returns true if contains(Object) == true for all of the elements of the specified collection.

Specified by:

containsAll in interface ProbabilisticFilter<E>

Parameters:

c - collection containing elements to be checked for containment in this filter

Returns:

true if this filter might contain all elements of the specified collection

Throws:

NullPointerException - if the specified collection contains one or more null elements, or if the specified collection is null

See Also:

contains(Object), containsAll(ProbabilisticFilter)

containsAll

public boolean containsAll(ProbabilisticFilter<E> f)

Not supported.

Specified by:

containsAll in interface ProbabilisticFilter<E>

Parameters:

f - filter containing elements to be checked for probable containment in this filter

Returns:

true if this filter might contain all elements contained in the specified filter, false if this is definitely not the case.

Throws:

UnsupportedOperationException

See Also:

ProbabilisticFilter.contains(Object), ProbabilisticFilter.containsAll(Collection)

isEmpty

public boolean isEmpty()

Returns true if this filter contains no elements.

Specified by:

isEmpty in interface ProbabilisticFilter<E>

Returns:

true if this filter contains no elements

See Also:

sizeLong()

sizeLong

public long sizeLong()

Returns the number of elements contained in this filter (its cardinality). If this filter contains more than Long.MAX_VALUE elements, returns Long.MAX_VALUE.

Specified by:

sizeLong in interface ProbabilisticFilter<E>

Returns:

the number of elements contained in this filter (its cardinality)

See Also:

capacity(), isEmpty()

size

public long size()

Returns the number of elements contained in this filter (its cardinality). If this filter contains more than Integer.MAX_VALUE elements, returns Integer.MAX_VALUE.

Specified by:

size in interface ProbabilisticFilter<E>

Returns:

the number of elements contained in this filter (its cardinality)

See Also:

capacity(), isEmpty(), sizeLong()

capacity

public long capacity()

Returns the number of elements this filter can represent at its requested FPP. This is not be a hard limit of the filter implementation. It is permissible for a filter to contain more elements than its requested capacity, though its FPP will suffer.

Specified by:

capacity in interface ProbabilisticFilter<E>

Returns:

the number of elements this filter can represent at its requested FPP.

See Also:

fpp(), currentFpp(), sizeLong()

fpp

public double fpp()

Returns the intended FPP limit of this filter. This is not a hard limit of the filter implementation. It is permissible for a filter's FPP to degrade (e.g. via saturation) beyond its intended limit.

Specified by:

fpp in interface ProbabilisticFilter<E>

Returns:

the intended FPP limit of this filter.

See Also:

currentFpp()

copyOf

public static <T> BloomFilter<T> copyOf(BloomFilter<T> f)

Creates a new BloomFilter that's a copy of this instance. The returned instance equals(f) == true but shares no mutable state.

clear

public void clear()

Removes all of the elements from this filter. The filter will be empty after this call returns.

Specified by:

clear in interface ProbabilisticFilter<E>

See Also:

sizeLong(), isEmpty()

remove

public boolean remove(E e)

Not supported. Standard bloom filters do not support element removal.

Specified by:

remove in interface ProbabilisticFilter<E>

Parameters:

e - element to be removed from this filter

Returns:

true if this filter probably contained the specified element, false otherwise

Throws:

UnsupportedOperationException

See Also:

ProbabilisticFilter.contains(Object), ProbabilisticFilter.removeAll(Collection), ProbabilisticFilter.removeAll(ProbabilisticFilter)

removeAll

public boolean removeAll(Collection<? extends E> c)

Not supported. Standard bloom filters do not support element removal.

Specified by:

removeAll in interface ProbabilisticFilter<E>

Parameters:

c - collection containing elements to be removed from this filter

Returns:

true if all of the elements of the specified collection were successfully removed from the filter, false if any of the elements was not successfully removed

Throws:

UnsupportedOperationException

See Also:

ProbabilisticFilter.contains(Object), ProbabilisticFilter.remove(Object), ProbabilisticFilter.removeAll(ProbabilisticFilter)

removeAll

public boolean removeAll(ProbabilisticFilter<E> f)

Not supported. Standard bloom filters do not support element removal.

Specified by:

removeAll in interface ProbabilisticFilter<E>

Parameters:

f - filter containing elements to remove from this filter. f is not mutated

Returns:

true if the operation was successful, false otherwise

Throws:

UnsupportedOperationException

See Also:

ProbabilisticFilter.contains(Object), ProbabilisticFilter.remove(Object), ProbabilisticFilter.removeAll(Collection)

equals

public boolean equals(@Nullable
             Object object)

Overrides:

equals in class Object

hashCode

public int hashCode()

Overrides:

hashCode in class Object