|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Object | +--org.edg.data.util.BloomFilter
A Representation of a Bloom Filter. 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 use MD5
to compute the hash functions, which are fixed to 4.
Field Summary | |
protected byte[] |
m_bits
the actual bits of the filter |
Constructor Summary | |
BloomFilter(byte[] bits,
int entries,
int numBits,
int optimalNumKeys)
Create a new BloomFilter from its constituent parts |
|
BloomFilter(int bitsPerEntry,
int optimalNumKeys)
create a new bloom filter |
Method Summary | |
void |
add(java.lang.String entry)
Add an entry to the Filter |
protected abstract void |
clearBit(int bit)
|
boolean |
contains(java.lang.String entry)
|
void |
delete(java.lang.String entry)
|
boolean |
equals(java.lang.Object o)
|
int |
getNumberOfHashes()
|
int |
getNumBits()
|
int |
getNumEntries()
|
int |
getOptimalNumKeys()
|
int |
hashCode()
|
boolean |
isFull()
|
protected abstract boolean |
isSet(int bit)
|
protected abstract void |
setBit(int bit)
|
java.lang.String |
toString()
|
void |
writeBits(java.io.OutputStream out)
|
Methods inherited from class java.lang.Object |
clone, finalize, getClass, notify, notifyAll, wait, wait, wait |
Field Detail |
protected final byte[] m_bits
Constructor Detail |
public BloomFilter(int bitsPerEntry, int optimalNumKeys)
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
)public BloomFilter(byte[] bits, int entries, int numBits, int optimalNumKeys)
bits
- the array of bits for this filterentries
- the number of keys stored in the filternumBits
- the actual number of bits usedoptimalNumKeys
- the optimal number of keys to store in the filterMethod Detail |
public void add(java.lang.String entry)
entry
- the entry. If this is null
no change is made
to the filterpublic void delete(java.lang.String entry)
public boolean contains(java.lang.String entry)
public boolean isFull()
public void writeBits(java.io.OutputStream out) throws java.io.IOException
java.io.IOException
public int getOptimalNumKeys()
public int getNumEntries()
public int getNumberOfHashes()
public int getNumBits()
public java.lang.String toString()
toString
in class java.lang.Object
public boolean equals(java.lang.Object o)
equals
in class java.lang.Object
public int hashCode()
hashCode
in class java.lang.Object
protected abstract void setBit(int bit)
protected abstract void clearBit(int bit)
protected abstract boolean isSet(int bit)
|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |