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

@InterfaceAudience.LimitedPrivate(value={"HDFS","MapReduce"})
@InterfaceStability.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:

The general behavior of a key, A hash function

Field Summary

Fields

Modifier and Type	Field and 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 and Description
protected	Filter()
protected	Filter(int vectorSize, int nbHash, int hashType) Constructor.

Method Summary

Methods

Modifier and Type	Method and Description
void	add(Collection<Key> keys) Adds a collection 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.
void	add(List<Key> keys) Adds a list 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 Detail

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 Detail

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 Detail

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

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