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 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 4654 2009-01-08 16:33:07Z jeffh $
Author:
  Alan Mislove
See Also:
  Serialized Form

Field Summary
`protected byte[]` | `array` An internal byte[] for managing ids in a memory-efficent manner The deal with this is that we will be creating a ton of arrays in addId/check.
`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.
`IdBloomFilter(InputBuffer buf)`

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, instantiating it.
`void` | `serialize(OutputBuffer buf)`

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 The deal with this is that we will be creating a ton of arrays in addId/check. So, what we do is allocate only 1 on a lazy basis. The call to checkArray() will construct a new array if there isn't one yet, then it will encode the id into the array.

### 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

### IdBloomFilter

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

Throws:
  `java.io.IOException`

Method Detail

### checkArray

    protected void checkArray(Id id)

  Internal method for checking to see if the array exists, and if not, instantiating it. It also places the given Id into the array. See the documentation of the member variable array for more info.

  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 definitely 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

### serialize

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

  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.