Package org.apache.hadoop.util.bloom

Class Filter

java.lang.Object
org.apache.hadoop.util.bloom.Filter
All Implemented Interfaces:
Writable
Direct Known Subclasses:
BloomFilter, CountingBloomFilter, DynamicBloomFilter
@LimitedPrivate({"HDFS","MapReduce"}) @Unstable public abstract class Filter extends Object implements Writable
Defines the general behavior of a filter.

A filter is a data structure which aims at offering a lossy summary of a set A. The key idea is to map entries of A (also called keys) into several positions in a vector through the use of several hash functions.

Typically, a filter will be implemented as a Bloom filter (or a Bloom filter extension).

It must be extended in order to define the real behavior.

See Also:

  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    protected HashFunction
    hash
    The hash function used to map a key to several positions in the vector.
    protected int
    hashType
    Type of hashing function to use.
    protected int
    nbHash
    The number of hash function to consider.
    protected int
    vectorSize
    The vector size of this filter.

  • Constructor Summary

    Constructors
    Modifier
    Constructor
    Description
    protected
    Filter()
     
    protected
    Filter(int vectorSize, int nbHash, int hashType)
    Constructor.

  • Method Summary

    Modifier and Type
    Method
    Description
    void
    add(Collection<Key> keys)
    Adds a collection of keys to this filter.
    void
    add(List<Key> keys)
    Adds a list of keys to this filter.
    abstract void
    add(Key key)
    Adds a key to this filter.
    void
    add(Key[] keys)
    Adds an array of keys to this filter.
    abstract void
    and(Filter filter)
    Peforms a logical AND between this filter and a specified filter.
    abstract boolean
    membershipTest(Key key)
    Determines wether a specified key belongs to this filter.
    abstract void
    not()
    Performs a logical NOT on this filter.
    abstract void
    or(Filter filter)
    Peforms a logical OR between this filter and a specified filter.
    void
    readFields(DataInput in)
    Deserialize the fields of this object from in.
    void
    write(DataOutput out)
    Serialize the fields of this object to out.
    abstract void
    xor(Filter filter)
    Peforms a logical XOR between this filter and a specified filter.

    Methods inherited from class java.lang.Object

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

  • Field Details

    • vectorSize

      protected int vectorSize
      The vector size of this filter.

    • hash

      protected HashFunction hash
      The hash function used to map a key to several positions in the vector.

    • nbHash

      protected int nbHash
      The number of hash function to consider.

    • hashType

      protected int hashType
      Type of hashing function to use.

  • Constructor Details

    • Filter

      protected Filter()

    • Filter

      protected Filter(int vectorSize, int nbHash, int hashType)
      Constructor.
      Parameters:
      vectorSize - The vector size of this filter.
      nbHash - The number of hash functions to consider.
      hashType - type of the hashing function (see Hash).

  • Method Details

    • add

      public abstract void add(Key key)
      Adds a key to this filter.
      Parameters:
      key - The key to add.

    • membershipTest

      public abstract boolean membershipTest(Key key)
      Determines wether a specified key belongs to this filter.
      Parameters:
      key - The key to test.
      Returns:
      boolean True if the specified key belongs to this filter. False otherwise.

    • and

      public abstract void and(Filter filter)
      Peforms a logical AND between this filter and a specified filter.

      Invariant: The result is assigned to this filter.

      Parameters:
      filter - The filter to AND with.

    • or

      public abstract void or(Filter filter)
      Peforms a logical OR between this filter and a specified filter.

      Invariant: The result is assigned to this filter.

      Parameters:
      filter - The filter to OR with.

    • xor

      public abstract void xor(Filter filter)
      Peforms a logical XOR between this filter and a specified filter.

      Invariant: The result is assigned to this filter.

      Parameters:
      filter - The filter to XOR with.

    • not

      public abstract void not()
      Performs a logical NOT on this filter.

      The result is assigned to this filter.

    • add

      public void add(List<Key> keys)
      Adds a list of keys to this filter.
      Parameters:
      keys - The list of keys.

    • add

      public void add(Collection<Key> keys)
      Adds a collection of keys to this filter.
      Parameters:
      keys - The collection of keys.

    • add

      public void add(Key[] keys)
      Adds an array of keys to this filter.
      Parameters:
      keys - The array of keys.

    • write

      public void write(DataOutput out) throws IOException
      Description copied from interface: Writable
      Serialize the fields of this object to out.
      Specified by:
      write in interface Writable
      Parameters:
      out - DataOuput to serialize this object into.
      Throws:
      IOException - any other problem for write.

    • readFields

      public void readFields(DataInput in) throws IOException
      Description copied from interface: Writable
      Deserialize the fields of this object from in.

      For efficiency, implementations should attempt to re-use storage in the existing object where possible.

      Specified by:
      readFields in interface Writable
      Parameters:
      in - DataInput to deseriablize this object from.
      Throws:
      IOException - any other problem for readFields.