rice.p2p.util
Class IdBloomFilter

java.lang.Object
  rice.p2p.util.IdBloomFilter

All Implemented Interfaces:

java.io.Serializable

public class IdBloomFilter

extends java.lang.Object

implements java.io.Serializable

Version:

$Id: IdBloomFilter.java 2605 2005-06-24 22:49:20Z jeffh $

Author:

Alan Mislove

See Also:

Serialized Form

Field Summary

protected byte[]	array An internal byte[] for managing ids in a memory-efficent manner
protected BloomFilter	filter The parameters to the hash functions for this bloom filter
static int	NUM_BITS_PER_KEY The number of bits per key in bloom filters
static int	NUM_HASH_FUNCTIONS The number of different hash functions to use in bloom filters

Constructor Summary

IdBloomFilter(IdSet set)
Constructor which takes the number of hash functions to use and the length of the set to use.

Method Summary

protected void	addId(Id id) Method which adds an Id to the underlying bloom filter
boolean	check(Id id) Method which returns whether or not an Id *may* be in the set.
void	check(IdSet set, IdSet result, int max) Method which checks an entire IdSet to see if they exist in this bloom filter, and returns the response by adding elements to the other provided id set.
protected void	checkArray(Id id) Internal method for checking to see if the array exists, and if not, instanciating it.

Methods inherited from class java.lang.Object

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

Field Detail

NUM_BITS_PER_KEY

public static int NUM_BITS_PER_KEY

The number of bits per key in bloom filters

NUM_HASH_FUNCTIONS

public static int NUM_HASH_FUNCTIONS

The number of different hash functions to use in bloom filters

array

protected transient byte[] array

An internal byte[] for managing ids in a memory-efficent manner

filter

protected BloomFilter filter

The parameters to the hash functions for this bloom filter

Constructor Detail

IdBloomFilter

public IdBloomFilter(IdSet set)

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

checkArray

protected void checkArray(Id id)

Internal method for checking to see if the array exists, and if not, instanciating it. It also places the given Id into the array.

Parameters:

id - An id to build the array from

addId

protected void addId(Id id)

Method which adds an Id to the underlying bloom filter

Parameters:

id - The id to add

check

public boolean check(Id id)

Method which returns whether or not an Id *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:

id - The id to check for

check

public void check(IdSet set,
                  IdSet result,
                  int max)

Method which checks an entire IdSet to see if they exist in this bloom filter, and returns the response by adding elements to the other provided id set.

Parameters:

set - THe set to check for

result - The set to put the non-existing objects into

max - The maximum number of keys to return