Overview | Package | Class | Use | Tree | Deprecated | Index | Help
| Rice Pastry API
PREV CLASS NEXT CLASS | FRAMES NO FRAMES
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD

## 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 3507 2006-12-21 13:18:37Z 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(InputBuffer buf)`
`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.
`static void` | `main(java.lang.String[] args)` Test serialize/deserialize
`void` | `serialize(OutputBuffer buf)`

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

### BloomFilter

    public BloomFilter(InputBuffer buf)
                throws java.io.IOException

Throws:
  `java.io.IOException`

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

### serialize

    public void serialize(OutputBuffer buf)
                   throws java.io.IOException

  Throws:
    `java.io.IOException`

### main

    public static void main(java.lang.String[] args)
                     throws java.io.IOException

  Test serialize/deserialize

  Parameters:
    `args` -
  Throws:
    `java.io.IOException`

Overview | Package | Class | Use | Tree | Deprecated | Index | Help
| Rice Pastry API
PREV CLASS NEXT CLASS | FRAMES NO FRAMES
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD

Copyright © 2001-2005 - Rice Pastry.