ePOST API

rice.p2p.util
Class BloomFilter

java.lang.Object
  extended by 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 2844 2005-12-15 13:07:05Z jeffh $
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

PARAMETER_LENGTH

public static int PARAMETER_LENGTH
The length of the random byte arrays which are generated


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

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

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

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

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
Returns:
The result, which is guaranteed to be 0..length

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

ePOST API

Copyright © 2001-2005 - Rice Pastry.