org.xlattice.crypto.filters

Class BloomSHA1

java.lang.Object

org.xlattice.crypto.filters.BloomSHA1

public class BloomSHA1
extends Object

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

Nested Classes

Modifier and Type	Class and Description
static class	BloomSHA1.FilterKey Stores the (opaque) bloom filter offsets for reuse.

Constructor Summary

Constructors

Constructor and Description
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

Modifier and Type	Method and Description
int	capacity() Returns the number of bits in the filter.
void	clear() Clears the filter, synchronized.
double	falsePositives() Calculates the approximate false positive rate for the current number of set members.
double	falsePositives(int n) Calculates the approximate false positive rate for a given number of set members.
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) Add a key to the set represented by the filter.
void	locked_insert(BloomSHA1.FilterKey fk) Add the key to the filter.
void	locked_insert(byte[] b) Add a key to the filter without synchronization.
void	locked_insert(byte[] b, int offset, int len) Add a key to the filter without synchronization.
boolean	locked_member(BloomSHA1.FilterKey fk) Is the key in the filter.
boolean	locked_member(byte[] b) Checks if a key is in the filter without synchronization.
boolean	locked_member(byte[] b, int offset, int len) Checks if a key is in the filter without synchronization.
boolean	member(byte[] b) Is a key in the filter.
boolean	member(byte[] b, int offset, int len) Is a key in the filter.
void	release(BloomSHA1.FilterKey fk) Releases filter key arrays back to the buffer pool.
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

BloomSHA1

public BloomSHA1()

Creates a filter of 2^20 bits with k defaulting to 8.

BloomSHA1

public BloomSHA1(int m)

Creates a filter of 2^m bits, with the number of 'hash functions" k defaulting to 8.

Parameters:

m - determines size of filter

BloomSHA1

public 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.

Parameters:

m - determines number of bits in filter

k - number of hash functions See KeySelector for important restriction on max m and k

Method Detail

capacity

public final int capacity()

Returns the number of bits in the filter.

Returns:

number of bits in filter

clear

public void clear()

Clears the filter, synchronized.

falsePositives

public final double falsePositives()

Calculates the approximate false positive rate for the current number of set members.

Returns:

approximate false positive rate

falsePositives

public final double falsePositives(int n)

Calculates the approximate false positive rate for a given number of set members.

Parameters:

n - number of set members

Returns:

approximate false positive rate

getFilterKey

public BloomSHA1.FilterKey getFilterKey(byte[] b,
                                        int offset,
                                        int len)

Get the bloom filter offsets for reuse. Caller should call release(rv) when done with it.

Parameters:

b - byte array representing a key (SHA1 digest)

offset - starting offset in the byte array

len - number of bytes to use

Returns:

filter key containing the offsets

insert

public void insert(byte[] b)

Add a key to the set represented by the filter. XXX This version does not maintain 4-bit counters, it is not a counting Bloom filter.

Parameters:

b - byte array representing a key (SHA1 digest)

insert

public void insert(byte[] b,
                   int offset,
                   int len)

Add a key to the set represented by the filter. XXX This version does not maintain 4-bit counters, it is not a counting Bloom filter.

Parameters:

b - byte array representing a key (SHA1 digest)

offset - starting offset in the byte array

len - number of bytes to use

locked_insert

public void locked_insert(BloomSHA1.FilterKey fk)

Add the key to the filter.

Parameters:

fk - filter key containing offsets

locked_insert

public final void locked_insert(byte[] b)

Add a key to the filter without synchronization.

Parameters:

b - byte array representing a key (SHA1 digest)

locked_insert

public final void locked_insert(byte[] b,
                                int offset,
                                int len)

Add a key to the filter without synchronization.

Parameters:

b - byte array representing a key (SHA1 digest)

offset - starting offset in the byte array

len - number of bytes to use

locked_member

public boolean locked_member(BloomSHA1.FilterKey fk)

Is the key in the filter.

Parameters:

fk - filter key containing offsets

Returns:

true if the key is in the filter

locked_member

public final boolean locked_member(byte[] b)

Checks if a key is in the filter without synchronization.

Parameters:

b - byte array representing a key (SHA1 digest)

Returns:

true if b is in the filter

locked_member

public final boolean locked_member(byte[] b,
                                   int offset,
                                   int len)

Checks if a key is in the filter without synchronization.

Parameters:

b - byte array representing a key (SHA1 digest)

offset - starting offset in the byte array

len - number of bytes to use

Returns:

true if b is in the filter

member

public final boolean member(byte[] b)

Is a key in the filter. External interface, internally synchronized.

Parameters:

b - byte array representing a key (SHA1 digest)

Returns:

true if b is in the filter

member

public final boolean member(byte[] b,
                            int offset,
                            int len)

Is a key in the filter. External interface, internally synchronized.

Parameters:

b - byte array representing a key (SHA1 digest)

offset - starting offset in the byte array

len - number of bytes to use

Returns:

true if b is in the filter

release

public void release(BloomSHA1.FilterKey fk)

Releases filter key arrays back to the buffer pool.

Parameters:

fk - filter key to release

size

public final int size()

Returns the number of keys which have been inserted. This class (BloomSHA1) does not guarantee uniqueness in any sense; if the same key is added N times, the number of set members reported will increase by N.

Returns:

number of set members