|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Objectorg.xlattice.crypto.filters.BloomSHA1
public class BloomSHA1
A Bloom filter for sets of SHA1 digests. A Bloom filter uses a set of k hash functions to determine set membership. Each hash function produces a value in the range 0..M-1. The filter is of size M. To add a member to the set, apply each function to the new member and set the corresponding bit in the filter. For M very large relative to k, this will normally set k bits in the filter. To check whether x is a member of the set, apply each of the k hash functions to x and check whether the corresponding bits are set in the filter. If any are not set, x is definitely not a member. If all are set, x may be a member. The probability of error (the false positive rate) is f = (1 - e^(-kN/M))^k, where N is the number of set members. This class takes advantage of the fact that SHA1 digests are good- quality pseudo-random numbers. The k hash functions are the values of distinct sets of bits taken from the 20-byte SHA1 hash. The number of bits in the filter, M, is constrained to be a power of 2; M == 2^m. The number of bits in each hash function may not exceed floor(m/k). This class is designed to be thread-safe, but this has not been exhaustively tested.
Nested Class Summary | |
---|---|
static class |
BloomSHA1.FilterKey
Store the (opaque) bloom filter offsets for reuse. |
Constructor Summary | |
---|---|
BloomSHA1()
Creates a filter of 2^20 bits with k defaulting to 8. |
|
BloomSHA1(int m)
Creates a filter of 2^m bits, with the number of 'hash functions" k defaulting to 8. |
|
BloomSHA1(int m,
int k)
Creates a filter with 2^m bits and k 'hash functions', where each hash function is portion of the 160-bit SHA1 hash. |
Method Summary | |
---|---|
int |
capacity()
|
void |
clear()
Synchronized version |
double |
falsePositives()
|
double |
falsePositives(int n)
|
BloomSHA1.FilterKey |
getFilterKey(byte[] b,
int offset,
int len)
Get the bloom filter offsets for reuse. |
void |
insert(byte[] b)
Add a key to the set represented by the filter. |
void |
insert(byte[] b,
int offset,
int len)
|
void |
locked_insert(BloomSHA1.FilterKey fk)
Add the key to the filter. |
void |
locked_insert(byte[] b)
|
void |
locked_insert(byte[] b,
int offset,
int len)
|
boolean |
locked_member(BloomSHA1.FilterKey fk)
Is the key in the filter. |
boolean |
locked_member(byte[] b)
|
boolean |
locked_member(byte[] b,
int offset,
int len)
|
boolean |
member(byte[] b)
Is a key in the filter. |
boolean |
member(byte[] b,
int offset,
int len)
|
void |
release(BloomSHA1.FilterKey fk)
|
int |
size()
Returns the number of keys which have been inserted. |
Methods inherited from class java.lang.Object |
---|
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait |
Constructor Detail |
---|
public BloomSHA1(int m, int k)
m
- determines number of bits in filterk
- number of hash functionsx
See KeySelector for important restriction on max m and kpublic BloomSHA1(int m)
m
- determines size of filterpublic BloomSHA1()
Method Detail |
---|
public void clear()
public final int size()
public final int capacity()
public void insert(byte[] b)
b
- byte array representing a key (SHA1 digest)public void insert(byte[] b, int offset, int len)
public final void locked_insert(byte[] b)
public final void locked_insert(byte[] b, int offset, int len)
public final boolean locked_member(byte[] b)
public final boolean locked_member(byte[] b, int offset, int len)
public final boolean member(byte[] b)
b
- byte array representing a key (SHA1 digest)
public final boolean member(byte[] b, int offset, int len)
public BloomSHA1.FilterKey getFilterKey(byte[] b, int offset, int len)
public void locked_insert(BloomSHA1.FilterKey fk)
public boolean locked_member(BloomSHA1.FilterKey fk)
public void release(BloomSHA1.FilterKey fk)
public final double falsePositives(int n)
n
- number of set members
public final double falsePositives()
|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |