net.tomp2p.rpc
Class CountingBloomFilter<E>

java.lang.Object
  net.tomp2p.rpc.CountingBloomFilter<E>

Type Parameters:

E - The type of object the BloomFilter should contain

All Implemented Interfaces:

Serializable, Iterable<E>, Collection<E>, Set<E>

public class CountingBloomFilter<E>
extends Object
implements Set<E>, Serializable

A counting Bloom Filter (see http://en.wikipedia.org/wiki/Bloom_filter) that uses java.util.Random as a primitive hash function, and which implements Java's Set interface for convenience. Only the add(), addAll(), contains(), and containsAll() methods are implemented. Calling any other method will yield an UnsupportedOperationException. This code may be used, modified, and redistributed provided that the author tag below remains intact.

Author:

Ian Clarke , Thomas Bocek Made a counting bloomfliter based on the simple bloom filter.

See Also:

Serialized Form

Constructor Summary

CountingBloomFilter(int expectedElements, int[] intSet)
Constructs a CountingBloomFilter out of existing data.

Method Summary

boolean	add(E o)
boolean	addAll(Collection<? extends E> c)
int	approximateCount(E key) Returns the number of times that an element has been added.
void	clear() Clear the Bloom Filter
boolean	contains(Object o)
boolean	containsAll(Collection<?> c)
boolean	equals(Object obj)
double	expectedFalsePositiveProbability() Calculates the approximate probability of the contains() method returning true for an object that had not previously been inserted into the bloom filter.
int	getExpectedElements() Returns the expected elements that was provided by the user.
int[]	getIntSet() Returns the bitset that backs the bloom filter
int	hashCode()
boolean	isEmpty() Not implemented
Iterator<E>	iterator() Not implemented
boolean	remove(Object o) Not implemented
boolean	removeAll(Collection<?> c) Not implemented
boolean	retainAll(Collection<?> c) Not implemented
int	size() Not implemented
Object[]	toArray() Not implemented
<T> T[]	toArray(T[] a) Not implemented
String	toString()

Methods inherited from class java.lang.Object

clone, finalize, getClass, notify, notifyAll, wait, wait, wait

Constructor Detail

CountingBloomFilter

public CountingBloomFilter(int expectedElements,
                           int[] intSet)

Constructs a CountingBloomFilter out of existing data. You must specify the number of bits in the Bloom Filter, and also you should specify the number of items you expect to add. The latter is used to choose some optimal internal values to minimize the false-positive rate (which can be estimated with expectedFalsePositiveRate()).

Parameters:

expectedElements - he typical number of items you expect to be added to the CountingBloomFilter (often called 'n').

intSet - The data that will be used in the backing BitSet

Method Detail

expectedFalsePositiveProbability

public double expectedFalsePositiveProbability()

Calculates the approximate probability of the contains() method returning true for an object that had not previously been inserted into the bloom filter. This is known as the "false positive probability".

Returns:

The estimated false positive rate

getExpectedElements

public int getExpectedElements()

Returns the expected elements that was provided by the user.

Returns:

The expected elements that was provided by the user

add

public boolean add(E o)

Specified by:

add in interface Collection<E>

Specified by:

add in interface Set<E>

addAll

public boolean addAll(Collection<? extends E> c)

Specified by:

addAll in interface Collection<E>

Specified by:

addAll in interface Set<E>

Parameters:

c - The collection to add

Returns:

This method will always return false

clear

public void clear()

Clear the Bloom Filter

Specified by:

clear in interface Collection<E>

Specified by:

clear in interface Set<E>

contains

public boolean contains(Object o)

Specified by:

contains in interface Collection<E>

Specified by:

contains in interface Set<E>

Parameters:

o - The object to compare

Returns:

False indicates that o was definitely not added to this Bloom Filter, true indicates that it probably was. The probability can be estimated using the expectedFalsePositiveProbability() method.

containsAll

public boolean containsAll(Collection<?> c)

Specified by:

containsAll in interface Collection<E>

Specified by:

containsAll in interface Set<E>

Parameters:

c - The collection to check if its inside this bloom filter

Returns:

true if the collection contains all the values

isEmpty

public boolean isEmpty()

Not implemented

Specified by:

isEmpty in interface Collection<E>

Specified by:

isEmpty in interface Set<E>

iterator

public Iterator<E> iterator()

Not implemented

Specified by:

iterator in interface Iterable<E>

Specified by:

iterator in interface Collection<E>

Specified by:

iterator in interface Set<E>

remove

public boolean remove(Object o)

Not implemented

Specified by:

remove in interface Collection<E>

Specified by:

remove in interface Set<E>

removeAll

public boolean removeAll(Collection<?> c)

Not implemented

Specified by:

removeAll in interface Collection<E>

Specified by:

removeAll in interface Set<E>

retainAll

public boolean retainAll(Collection<?> c)

Not implemented

Specified by:

retainAll in interface Collection<E>

Specified by:

retainAll in interface Set<E>

size

public int size()

Not implemented

Specified by:

size in interface Collection<E>

Specified by:

size in interface Set<E>

toArray

public Object[] toArray()

Not implemented

Specified by:

toArray in interface Collection<E>

Specified by:

toArray in interface Set<E>

toArray

public <T> T[] toArray(T[] a)

Not implemented

Specified by:

toArray in interface Collection<E>

Specified by:

toArray in interface Set<E>

getIntSet

public int[] getIntSet()

Returns the bitset that backs the bloom filter

Returns:

bloom filter as a bitset

approximateCount

public int approximateCount(E key)

Returns the number of times that an element has been added. This is an approximate value and can be larger but never smaller than the actual number of additions.

Parameters:

key - The key to count

Returns:

The number of approximate additions of this object

equals

public boolean equals(Object obj)

Specified by:

equals in interface Collection<E>

Specified by:

equals in interface Set<E>

Overrides:

equals in class Object

hashCode

public int hashCode()

Specified by:

hashCode in interface Collection<E>

Specified by:

hashCode in interface Set<E>

Overrides:

hashCode in class Object

toString

public String toString()

Overrides:

toString in class Object