org.apache.hadoop.util.bloom

类 BloomFilter

java.lang.Object

org.apache.hadoop.util.bloom.Filter

org.apache.hadoop.util.bloom.BloomFilter

所有已实现的接口:

Writable

直接已知子类:

RetouchedBloomFilter

public class BloomFilter
extends Filter

Implements a Bloom filter, as defined by Bloom in 1970.

The Bloom filter is a data structure that was introduced in 1970 and that has been adopted by the networking research community in the past decade thanks to the bandwidth efficiencies that it offers for the transmission of set membership information between networked hosts. A sender encodes the information into a bit vector, the Bloom filter, that is more compact than a conventional representation. Computation and space costs for construction are linear in the number of elements. The receiver uses the filter to test whether various elements are members of the set. Though the filter will occasionally return a false positive, it will never return a false negative. When creating the filter, the sender can choose its desired point in a trade-off between the false positive rate and the size.

Originally created by European Commission One-Lab Project 034819.

另请参阅:

The general behavior of a filter, Space/Time Trade-Offs in Hash Coding with Allowable Errors

字段概要

从类继承的字段 org.apache.hadoop.util.bloom.Filter

hash, hashType, nbHash, vectorSize

构造器概要

构造器

构造器和说明
BloomFilter() Default constructor - use with readFields
BloomFilter(int vectorSize, int nbHash, int hashType) Constructor

方法概要

方法

限定符和类型	方法和说明
void	add(Key key) Adds a key to this filter.
void	and(Filter filter) Peforms a logical AND between this filter and a specified filter.
int	getVectorSize()
boolean	membershipTest(Key key) Determines wether a specified key belongs to this filter.
void	not() Performs a logical NOT on this filter.
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.
String	toString()
void	write(DataOutput out) Serialize the fields of this object to out.
void	xor(Filter filter) Peforms a logical XOR between this filter and a specified filter.

从类继承的方法 org.apache.hadoop.util.bloom.Filter

add, add, add

从类继承的方法 java.lang.Object

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

构造器详细资料

BloomFilter

public BloomFilter()

Default constructor - use with readFields

BloomFilter

public BloomFilter(int vectorSize,
           int nbHash,
           int hashType)

Constructor

参数:

vectorSize - The vector size of this filter.

nbHash - The number of hash function to consider.

hashType - type of the hashing function (see Hash).

方法详细资料

add

public void add(Key key)

从类复制的说明: Filter

Adds a key to this filter.

指定者:

add 在类中 Filter

参数:

key - The key to add.

and

public void and(Filter filter)

从类复制的说明: Filter

Peforms a logical AND between this filter and a specified filter.

Invariant: The result is assigned to this filter.

指定者:

and 在类中 Filter

参数:

filter - The filter to AND with.

membershipTest

public boolean membershipTest(Key key)

从类复制的说明: Filter

Determines wether a specified key belongs to this filter.

指定者:

membershipTest 在类中 Filter

参数:

key - The key to test.

返回:

boolean True if the specified key belongs to this filter. False otherwise.

not

public void not()

从类复制的说明: Filter

Performs a logical NOT on this filter.

The result is assigned to this filter.

指定者:

not 在类中 Filter

or

public void or(Filter filter)

从类复制的说明: Filter

Peforms a logical OR between this filter and a specified filter.

Invariant: The result is assigned to this filter.

指定者:

or 在类中 Filter

参数:

filter - The filter to OR with.

xor

public void xor(Filter filter)

从类复制的说明: Filter

Peforms a logical XOR between this filter and a specified filter.

Invariant: The result is assigned to this filter.

指定者:

xor 在类中 Filter

参数:

filter - The filter to XOR with.

toString

public String toString()

覆盖:

toString 在类中 Object

getVectorSize

public int getVectorSize()

返回:

size of the the bloomfilter

write

public void write(DataOutput out)
           throws IOException

从接口复制的说明: Writable

Serialize the fields of this object to out.

指定者:

write 在接口中 Writable

覆盖:

write 在类中 Filter

参数:

out - DataOuput to serialize this object into.

抛出:

IOException

readFields

public void readFields(DataInput in)
                throws IOException

从接口复制的说明: Writable

Deserialize the fields of this object from in.

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

指定者:

readFields 在接口中 Writable

覆盖:

readFields 在类中 Filter

参数:

in - DataInput to deseriablize this object from.

抛出:

IOException