|
||||||||||
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.
Field Summary | |
---|---|
protected int[] |
bitOffset
|
protected int |
count
|
protected int[] |
filter
|
protected int |
filterBits
|
protected int |
filterWords
|
protected int |
k
|
protected KeySelector |
ks
|
protected int |
m
|
protected int[] |
wordOffset
|
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 | |
---|---|
static java.lang.String |
btoh(byte b)
convert single byte to String |
int |
capacity()
|
void |
clear()
Synchronized version |
protected void |
doClear()
Clear the filter, unsynchronized |
double |
falsePositives()
|
double |
falsePositives(int n)
|
void |
insert(byte[] b)
Add a key to the set represented by the filter. |
void |
insert(byte[] b,
int offset,
int len)
|
protected boolean |
isMember(byte[] b)
Is a key in the filter. |
protected boolean |
isMember(byte[] b,
int offset,
int len)
|
static java.lang.String |
itoh(int i)
convert 32-bit integer to String |
static java.lang.String |
keyToString(byte[] key)
|
void |
locked_insert(byte[] b)
|
void |
locked_insert(byte[] b,
int offset,
int len)
|
boolean |
locked_member(byte[] b)
|
boolean |
locked_member(byte[] b,
int offset,
int len)
|
static java.lang.String |
ltoh(long i)
convert 64-bit integer to hex String |
static void |
main(java.lang.String[] args)
|
boolean |
member(byte[] b)
Is a key in the filter. |
boolean |
member(byte[] b,
int offset,
int len)
|
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 |
Field Detail |
---|
protected final int m
protected final int k
protected int count
protected final int[] filter
protected KeySelector ks
protected final int[] wordOffset
protected final int[] bitOffset
protected final int filterBits
protected final int filterWords
Constructor Detail |
---|
public BloomSHA1(int m, int k)
m
- determines number of bits in filter, defaults to 20k
- number of hash functions, defaults to 8public BloomSHA1(int m)
m
- determines size of filterpublic BloomSHA1()
Method Detail |
---|
public static void main(java.lang.String[] args)
protected void doClear()
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)
protected final boolean isMember(byte[] b)
b
- byte array representing a key (SHA1 digest)
protected final boolean isMember(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 final double falsePositives(int n)
n
- number of set members
public final double falsePositives()
public static java.lang.String keyToString(byte[] key)
public static java.lang.String ltoh(long i)
public static java.lang.String itoh(int i)
public static java.lang.String btoh(byte b)
|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |