rice.p2p.util
Class BloomFilter

java.lang.Object
  rice.p2p.util.BloomFilter

All Implemented Interfaces:

java.io.Serializable

public class BloomFilter

extends java.lang.Object

implements java.io.Serializable

Version:

$Id: BloomFilter.java,v 1.3 2005/03/11 00:58:16 jeffh Exp $

Author:

Alan Mislove

See Also:

Serialized Form

Field Summary

protected int	length The length of the set to use
static int	PARAMETER_LENGTH The length of the random byte arrays which are generated
protected int[]	parameters The parameters to the hash functions for this bloom filter
protected java.util.BitSet	set The underlying bitset representation for this bloom filter

Constructor Summary

BloomFilter(int num, int length)
Constructor which takes the number of hash functions to use and the length of the set to use.

Method Summary

void	add(byte[] array) Method which adds an element to this bloom filter.
boolean	check(byte[] array) Method which returns whether or not an element *may* be in the set.
protected int	doHash(byte[] array, int seed) Method which performs a dumb hash of the provided array and the seed value.
java.lang.String	getBitSet() Method which returns what the internal bit set looks like as a string
protected int	hash(byte[] array, int i) Internal method which hashes the input argument using the ith hash function, and then mods the result by length.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

parameters

protected int[] parameters

The parameters to the hash functions for this bloom filter

length

protected int length

The length of the set to use

set

protected java.util.BitSet set

The underlying bitset representation for this bloom filter

PARAMETER_LENGTH

public static int PARAMETER_LENGTH

The length of the random byte arrays which are generated

Constructor Detail

BloomFilter

public BloomFilter(int num,
                   int length)

Constructor which takes the number of hash functions to use and the length of the set to use.

Parameters:

num - The number of hash functions to use

length - The length of the underlying bit set

Method Detail

getBitSet

public java.lang.String getBitSet()

Method which returns what the internal bit set looks like as a string

Returns:

The internal bit set as a string

add

public void add(byte[] array)

Method which adds an element to this bloom filter. This is done by computing h_1(x), h_2(x), ... and then setting bits (h_1(x) % length), (h_2(x) % length) and so forth.

Parameters:

array - The element to add

check

public boolean check(byte[] array)

Method which returns whether or not an element *may* be in the set. Specifically, if this method returns false, the element is definately not in the set. Otherwise, if true is returned, the element may be in the set, but it is not guaranteed.

Parameters:

array - The element to check for

Returns:

DESCRIBE THE RETURN VALUE

hash

protected int hash(byte[] array,
                   int i)

Internal method which hashes the input argument using the ith hash function, and then mods the result by length.

Parameters:

array - The element to hash

i - The hash function to use

Returns:

DESCRIBE THE RETURN VALUE

doHash

protected int doHash(byte[] array,
                     int seed)

Method which performs a dumb hash of the provided array and the seed value.

Parameters:

array - The input array

seed - DESCRIBE THE PARAMETER

Returns:

The result, which is guaranteed to be 0..length