Class LayeredBloomFilter
- All Implemented Interfaces:
BitMapProducer
,BloomFilter
,BloomFilterProducer
,IndexProducer
In short, Layered Bloom filter contains several bloom filters arranged in layers.
- When membership in the filter is checked each layer in turn is checked
and if a match is found
true
is returned. - When merging each bloom filter is merged into the newest filter in the list of layers.
- When questions of cardinality are asked the cardinality of the union of the enclosed Bloom filters is used.
The net result is that the layered Bloom filter can be populated with more items than the Shape would indicate and yet still return a false positive rate in line with the Shape and not the over population.
This implementation uses a LayerManager to handle the manipulation of the layers.
- Level 0 is the oldest layer and the highest level is the newest.
- There is always at least one enclosed filter.
- The newest filter is the
target
into which merges are performed. - Whenever the target is retrieved, or a
merge
operation is performed the code checks if any older layers should be removed, and if so removes them. It also checks it a new layer should be added, and if so adds it and sets thetarget
before the operation.
- Since:
- 4.5
-
Field Summary
Fields inherited from interface org.apache.commons.collections4.bloomfilter.BloomFilter
SPARSE
-
Constructor Summary
-
Method Summary
Modifier and TypeMethodDescriptionint
Gets the cardinality (number of enabled bits) of this Bloom filter.int
Returns the characteristics of the filter.final void
clear()
Resets the filter to its initial, unpopulated state.boolean
contains
(BitMapProducer bitMapProducer) Returnstrue
if this filter contains the bits specified in the bit maps produced by the bitMapProducer.boolean
contains
(BloomFilter other) Returnstrue
if this any layer contained by this filter contains the specified filter.boolean
contains
(BloomFilterProducer producer) Returnstrue
if each filter within theproducer
exits within this filter.boolean
Returnstrue
if this filter contains the bits specified in the hasher.boolean
contains
(IndexProducer indexProducer) Returnstrue
if this filter contains the indices specified IndexProducer.copy()
Creates a new instance of the BloomFilter with the same properties as the current one.int
Estimates the number of items in the Bloom filter.int
estimateUnion
(BloomFilter other) Estimates the number of items in the union of this Bloom filter with the other bloom filter.int[]
find
(BitMapProducer bitMapProducer) Finds the layers in which the BitMapProducer is found.int[]
find
(BloomFilter bf) Finds the layers in which the Bloom filter is found.int[]
Finds the layers in which the Hasher is found.int[]
find
(IndexProducer indexProducer) Finds the layers in which the IndexProducer is found.static LayeredBloomFilter
Creates a fixed size layered bloom filter that adds new filters to the list, but never merges them.flatten()
Create a standard (non-layered) Bloom filter by merging all of the layers.boolean
forEachBitMap
(LongPredicate predicate) Each bit map is passed to the predicate in order.final boolean
forEachBloomFilter
(Predicate<BloomFilter> bloomFilterPredicate) Processes the Bloom filters in depth order with the most recent filters first.boolean
forEachIndex
(IntPredicate predicate) Each index is passed to the predicate.get
(int depth) Gets the Bloom filter at the specified depthfinal int
getDepth()
Gets the depth of the deepest layer.final Shape
getShape()
Gets the shape that was used when the filter was built.boolean
isEmpty()
Determines if all the bits are off.boolean
merge
(BitMapProducer bitMapProducer) Merges the specified hasher into this Bloom filter.boolean
merge
(BloomFilter bf) Merges the specified Bloom filter into this Bloom filter.boolean
merge
(IndexProducer indexProducer) Merges the specified IndexProducer into this Bloom filter.void
next()
Forces and advance to the next layer.Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
Methods inherited from interface org.apache.commons.collections4.bloomfilter.BitMapProducer
asBitMapArray, forEachBitMapPair
Methods inherited from interface org.apache.commons.collections4.bloomfilter.BloomFilter
estimateIntersection, isFull, merge, uniqueIndices
Methods inherited from interface org.apache.commons.collections4.bloomfilter.BloomFilterProducer
asBloomFilterArray, forEachBloomFilterPair
Methods inherited from interface org.apache.commons.collections4.bloomfilter.IndexProducer
asIndexArray
-
Constructor Details
-
LayeredBloomFilter
Constructor.- Parameters:
shape
- the Shape of the enclosed Bloom filterslayerManager
- the LayerManager to manage the layers.
-
-
Method Details
-
fixed
Creates a fixed size layered bloom filter that adds new filters to the list, but never merges them. List will never exceed maxDepth. As additional filters are added earlier filters are removed.- Parameters:
shape
- The shape for the enclosed Bloom filters.maxDepth
- The maximum depth of layers.- Returns:
- An empty layered Bloom filter of the specified shape and depth.
-
cardinality
Description copied from interface:BloomFilter
Gets the cardinality (number of enabled bits) of this Bloom filter.This is also known as the Hamming value or Hamming number.
- Specified by:
cardinality
in interfaceBloomFilter
- Returns:
- the cardinality of this filter
-
characteristics
Description copied from interface:BloomFilter
Returns the characteristics of the filter.Characteristics are defined as bits within the characteristics integer.
- Specified by:
characteristics
in interfaceBloomFilter
- Returns:
- the characteristics for this bloom filter.
-
clear
Description copied from interface:BloomFilter
Resets the filter to its initial, unpopulated state.- Specified by:
clear
in interfaceBloomFilter
-
contains
Description copied from interface:BloomFilter
Returnstrue
if this filter contains the bits specified in the bit maps produced by the bitMapProducer.- Specified by:
contains
in interfaceBloomFilter
- Parameters:
bitMapProducer
- theBitMapProducer
to provide the bit maps.- Returns:
true
if this filter is enabled for all bits specified by the bit maps
-
contains
Returnstrue
if this any layer contained by this filter contains the specified filter.If the
other
is a BloomFilterProducer each filter within theother
is checked to see if it exits within this filter.- Specified by:
contains
in interfaceBloomFilter
- Parameters:
other
- the other Bloom filter- Returns:
true
if this filter contains the other filter.
-
contains
Returnstrue
if each filter within theproducer
exits within this filter.- Parameters:
producer
- the BloomFilterProducer that provides the filters to check for.- Returns:
true
if this filter contains all of the filters contained in theproducer
.
-
contains
Description copied from interface:BloomFilter
Returnstrue
if this filter contains the bits specified in the hasher.Specifically this returns
true
if this filter is enabled for all bit indexes identified by thehasher
. Using the bit map representations this is effectively(this AND hasher) == hasher
.- Specified by:
contains
in interfaceBloomFilter
- Parameters:
hasher
- the hasher to provide the indexes- Returns:
- true if this filter is enabled for all bits specified by the hasher
-
contains
Description copied from interface:BloomFilter
Returnstrue
if this filter contains the indices specified IndexProducer.Specifically this returns
true
if this filter is enabled for all bit indexes identified by theIndexProducer
.- Specified by:
contains
in interfaceBloomFilter
- Parameters:
indexProducer
- the IndexProducer to provide the indexes- Returns:
true
if this filter is enabled for all bits specified by the IndexProducer
-
copy
Description copied from interface:BloomFilter
Creates a new instance of the BloomFilter with the same properties as the current one.- Specified by:
copy
in interfaceBloomFilter
- Returns:
- a copy of this BloomFilter
-
estimateN
Description copied from interface:BloomFilter
Estimates the number of items in the Bloom filter.By default this is the rounding of the
Shape.estimateN(cardinality)
calculation for the shape and cardinality of this filter.This produces an estimate roughly equivalent to the number of Hashers that have been merged into the filter by rounding the value from the calculation described in the
Shape
class Javadoc.Note:
- if cardinality == numberOfBits, then result is Integer.MAX_VALUE.
- if cardinality > numberOfBits, then an IllegalArgumentException is thrown.
- Specified by:
estimateN
in interfaceBloomFilter
- Returns:
- an estimate of the number of items in the bloom filter. Will return Integer.MAX_VALUE if the estimate is larger than Integer.MAX_VALUE.
- See Also:
-
estimateUnion
Description copied from interface:BloomFilter
Estimates the number of items in the union of this Bloom filter with the other bloom filter.This produces an estimate roughly equivalent to the number of unique Hashers that have been merged into either of the filters by rounding the value from the calculation described in the
Shape
class Javadoc.estimateUnion
should only be called with Bloom filters of the same Shape. If called on Bloom filters of differing shape this method is not symmetric. Ifother
has more bits anIllegalArgumentException
may be thrown.- Specified by:
estimateUnion
in interfaceBloomFilter
- Parameters:
other
- The other Bloom filter- Returns:
- an estimate of the number of items in the union. Will return Integer.MAX_VALUE if the estimate is larger than Integer.MAX_VALUE.
- See Also:
-
find
Finds the layers in which the BitMapProducer is found.- Parameters:
bitMapProducer
- the BitMapProducer to search for.- Returns:
- an array of layer indices in which the Bloom filter is found.
-
find
Finds the layers in which the Bloom filter is found.- Parameters:
bf
- the Bloom filter to search for.- Returns:
- an array of layer indices in which the Bloom filter is found.
-
find
Finds the layers in which the Hasher is found.- Parameters:
hasher
- the Hasher to search for.- Returns:
- an array of layer indices in which the Bloom filter is found.
-
find
Finds the layers in which the IndexProducer is found.- Parameters:
indexProducer
- the Index producer to search for.- Returns:
- an array of layer indices in which the Bloom filter is found.
-
flatten
Create a standard (non-layered) Bloom filter by merging all of the layers. If the filter is empty this method will return an empty Bloom filter.- Specified by:
flatten
in interfaceBloomFilterProducer
- Returns:
- the merged bloom filter.
-
forEachBitMap
Description copied from interface:BitMapProducer
Each bit map is passed to the predicate in order. The predicate is applied to each bit map value, if the predicate returnsfalse
the execution is stopped,false
is returned, and no further bit maps are processed.If the producer is empty this method will return true.
Any exceptions thrown by the action are relayed to the caller.
- Specified by:
forEachBitMap
in interfaceBitMapProducer
- Parameters:
predicate
- the function to execute- Returns:
true
if all bit maps returnedtrue
,false
otherwise.
-
forEachBloomFilter
Processes the Bloom filters in depth order with the most recent filters first. Each filter is passed to the predicate in turn. The function exits on the firstfalse
returned by the predicate.- Specified by:
forEachBloomFilter
in interfaceBloomFilterProducer
- Parameters:
bloomFilterPredicate
- the predicate to execute.- Returns:
true
if all filters passed the predicate,false
otherwise.
-
forEachIndex
Description copied from interface:IndexProducer
Each index is passed to the predicate. The predicate is applied to each index value, if the predicate returnsfalse
the execution is stopped,false
is returned, and no further indices are processed.Any exceptions thrown by the action are relayed to the caller.
Indices ordering and uniqueness is not guaranteed.
- Specified by:
forEachIndex
in interfaceIndexProducer
- Parameters:
predicate
- the action to be performed for each non-zero bit index.- Returns:
true
if all indexes return true from consumer,false
otherwise.
-
get
Gets the Bloom filter at the specified depth- Parameters:
depth
- the depth of the filter to return.- Returns:
- the Bloom filter at the specified depth.
- Throws:
NoSuchElementException
- if depth is not in the range [0,getDepth())
-
getDepth
Gets the depth of the deepest layer. The minimum value returned by this method is 1.- Returns:
- the depth of the deepest layer.
-
getShape
Description copied from interface:BloomFilter
Gets the shape that was used when the filter was built.- Specified by:
getShape
in interfaceBloomFilter
- Returns:
- The shape the filter was built with.
-
isEmpty
Description copied from interface:BloomFilter
Determines if all the bits are off. This is equivalent tocardinality() == 0
.Note: This method is optimised for non-sparse filters. Implementers are encouraged to implement faster checks if possible.
- Specified by:
isEmpty
in interfaceBloomFilter
- Returns:
true
if no bits are enabled,false
otherwise.
-
merge
Description copied from interface:BloomFilter
Merges the specified hasher into this Bloom filter. Specifically all bit indexes that are identified by theproducer
will be enabled in this filter.Note: This method should return
true
even if no additional bit indexes were enabled. Afalse
result indicates that this filter may or may not contain all the indexes enabled in theproducer
. This state may occur in complex Bloom filter implementations like counting Bloom filters.- Specified by:
merge
in interfaceBloomFilter
- Parameters:
bitMapProducer
- The producer to merge.- Returns:
- true if the merge was successful
-
merge
Description copied from interface:BloomFilter
Merges the specified Bloom filter into this Bloom filter.Specifically all bit indexes that are identified by the
other
will be enabled in this filter.Note: This method should return
true
even if no additional bit indexes were enabled. Afalse
result indicates that this filter may or may not contain theother
Bloom filter. This state may occur in complex Bloom filter implementations like counting Bloom filters.- Specified by:
merge
in interfaceBloomFilter
- Parameters:
bf
- The bloom filter to merge into this one.- Returns:
- true if the merge was successful
-
merge
Description copied from interface:BloomFilter
Merges the specified IndexProducer into this Bloom filter. Specifically all bit indexes that are identified by theproducer
will be enabled in this filter.Note: This method should return
true
even if no additional bit indexes were enabled. Afalse
result indicates that this filter may or may not contain all the indexes of theproducer
. This state may occur in complex Bloom filter implementations like counting Bloom filters.- Specified by:
merge
in interfaceBloomFilter
- Parameters:
indexProducer
- The IndexProducer to merge.- Returns:
- true if the merge was successful
-
next
Forces and advance to the next layer. Executes the same logic as when LayerManager.extendCheck returnstrue
- See Also:
-