org.edg.data.util
Class CountingBloomFilter
java.lang.Object
|
+--org.edg.data.util.BloomFilter
|
+--org.edg.data.util.CountingBloomFilter
- All Implemented Interfaces:
- java.io.Serializable
- public class CountingBloomFilter
- extends BloomFilter
A Representation of a Bloom Filter which stores counts for each bit. See
The
Math of Bloom Filters for how to tune the Filter. Note you must
specify the size of the filter a priori (i.e. set m
), but it can
tell you when it has too many entries, and will start to degrade (i.e. more
than n
entries.
We store the counts as a single nybble, i.e. 4 bits. We don't deal with
overflow, so if the same bit is added more than 15 times, and then removed
15 times, the bit will be set to 0. The above reference shows the
probability of this overflow happening is bounded by
1.37e-15 x m
.
We use MD5
to compute the hash functions, which are fixed to 4.
We deal with bloom filters with up to 2^^31 bits in them.
- Version:
- $ Id:$
- Author:
- James Casey
- See Also:
- Serialized Form
Constructor Summary |
CountingBloomFilter(byte[] bits,
int entries,
int numBits,
int optimalNumKeys)
create a read-only Bloomfilter from a pre-created bit array. |
CountingBloomFilter(int bitsPerEntry,
int optimalNumKeys)
create a new bloom filter |
Method Summary |
protected void |
clearBit(int bit)
|
protected boolean |
isSet(int bit)
|
protected void |
setBit(int bit)
|
Methods inherited from class org.edg.data.util.BloomFilter |
add, contains, delete, equals, getNumberOfHashes, getNumBits, getNumEntries, getOptimalNumKeys, hashCode, isFull, toString, writeBits |
Methods inherited from class java.lang.Object |
clone, finalize, getClass, notify, notifyAll, wait, wait, wait |
CountingBloomFilter
public CountingBloomFilter(int bitsPerEntry,
int optimalNumKeys)
- create a new bloom filter
- Parameters:
bitsPerEntry
- The number of bits per entry in the filter we require (also
known as m/n
)optimalNumKeys
- The number of keys for which this filter optimally
support (also known as n
)
CountingBloomFilter
public CountingBloomFilter(byte[] bits,
int entries,
int numBits,
int optimalNumKeys)
- create a read-only Bloomfilter from a pre-created bit array.
- Parameters:
bits
- the bit array.entries
- current number of entries in filternumBits
- the number of bits in this filteroptimalNumKeys
- The number of keys for which this filter optimally
support (also known as n
)
setBit
protected void setBit(int bit)
- Specified by:
setBit
in class BloomFilter
clearBit
protected void clearBit(int bit)
- Specified by:
clearBit
in class BloomFilter
isSet
protected boolean isSet(int bit)
- Specified by:
isSet
in class BloomFilter