Package org.forgerock.bloomfilter
Interface BloomFilter<E>
-
- Type Parameters:
E
- the type of elements contained in the bloom filter.
- All Known Implementing Classes:
BloomFilterMonitor
,ConcurrentRollingBloomFilter
public interface BloomFilter<E>
General interface contract for implementations of Bloom Filters. A Bloom Filter is a Set-like data structure that uses only a few bits of memory per element stored. This allows very large numbers (billions) of elements to be stored in-memory, with the trade-off being that set containment can now return false positives. That is, the Bloom Filter can say for certain if a given element is definitely not in the set, but it cannot say for certain whether it is. Bloom Filters are therefore appropriate as a quick initial check to reduce load on a more expensive but more accurate storage mechanism (e.g., a database) or where some level of false positives is tolerable. The expected usage pattern for the former case would be something like the following psuedo-code:BloomFilter<T> filter = ...; Set<T> expensiveSet = ...; // e.g. database, web-service if (filter.mightContain(element)) { // Perform the more expensive check to be sure return expensive.contains(element); } return false;
Note: this assumes that the Bloom Filter is kept in-sync with the definitive set! How this is accomplished is outside of the scope of this package.All Bloom Filter implementations in this package allow the probability of false positives (FPP) to be specified, and the implementation will adjust the amount of memory used to ensure the given level of accuracy for the expected number of elements.
- See Also:
- Bloom Filter Wikipedia entry
-
-
Method Summary
All Methods Instance Methods Abstract Methods Modifier and Type Method Description void
add(E element)
Adds the specified element to this set if it is not already possibly present.void
addAll(Collection<? extends E> elements)
Adds all of the specified elements to this set if they are not possibly already present.BloomFilterStatistics
getStatistics()
Gets a snapshot of the current statistics of the set.boolean
mightContain(E element)
Checks if the given element might be a member of this set.
-
-
-
Method Detail
-
add
void add(E element)
Adds the specified element to this set if it is not already possibly present. After a call to this method, subsequent calls tomightContain(Object)
will returntrue
for the same object.- Parameters:
element
- the element to add to this set.
-
addAll
void addAll(Collection<? extends E> elements)
Adds all of the specified elements to this set if they are not possibly already present.- Parameters:
elements
- the elements to add to the set.
-
mightContain
boolean mightContain(E element)
Checks if the given element might be a member of this set. If this method returnsfalse
, then the given object is definitely not a member of the set. If the result istrue
then the object may or may not be a member of this set, with a certain probability of false positives.- Parameters:
element
- the element to check for membership in this set.- Returns:
false
if the element is definitely not in the set, ortrue
if it might be.
-
getStatistics
BloomFilterStatistics getStatistics()
Gets a snapshot of the current statistics of the set.
-
-