net.obsearch.index.bucket
Class SimpleBloomFilter<E>

java.lang.Object
  net.obsearch.index.bucket.SimpleBloomFilter<E>

Type Parameters:

E - The type of object the BloomFilter should contain

All Implemented Interfaces:

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

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

A simple 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

See Also:

Serialized Form

Field Summary

protected int

k

Constructor Summary

SimpleBloomFilter(int bitArraySize, int expectedElements)
Construct a SimpleBloomFilter.

Method Summary

boolean	add(E o)
boolean	addAll(Collection<? extends E> c)
void	clear() Clear the Bloom Filter
boolean	contains(Object o)
boolean	containsAll(Collection<?> c)
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.
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

Methods inherited from class java.lang.Object

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

Methods inherited from interface java.util.Set

equals, hashCode

Field Detail

k

protected int k

Constructor Detail

SimpleBloomFilter

public SimpleBloomFilter(int bitArraySize,
                         int expectedElements)

Construct a SimpleBloomFilter. 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:

bitArraySize - The number of bits in the bit array (often called 'm' in the context of bloom filters).

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

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

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>

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>

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>

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>