Package org.drasyl.util

Class BloomFilter<E>

java.lang.Object

org.drasyl.util.BloomFilter<E>

Type Parameters:

E - the type of elements maintained by this set

All Implemented Interfaces:

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

Direct Known Subclasses:

CountingBloomFilter

public class BloomFilter<E>
extends Object
implements Set<E>

A bloom filter is a probabilistic data structure that can quickly and efficiently check whether an element is included in a set.

This implementation uses Murmur3.murmur3_x86_32 as hash source is backed by a BitSet.

Although this class implements Set, not all set operations are actually supported (e.g. removal or retrieval of elements).

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
protected static class	BloomFilter.Parameters

Field Summary

Fields

Modifier and Type	Field	Description
protected final BitSet	bitSet
protected final Function<E,byte[]>	bytesSupplier
protected final BloomFilter.Parameters	parameters

Constructor Summary

Constructors

Modifier	Constructor	Description
	BloomFilter(int n, double p, int m, int k, Function<E,byte[]> bytesSupplier)	Create a new bloom filter.
	BloomFilter(int n, double p, int m, int k, Function<E,byte[]> bytesSupplier, BitSet bitSet)	Create a new bloom filter.
	BloomFilter(Integer n, Double p, Function<E,byte[]> bytesSupplier)	Create a new bloom filter.
	BloomFilter(Integer n, Double p, Function<E,byte[]> bytesSupplier, BitSet bitSet)	Create a new bloom filter.
protected	BloomFilter(BloomFilter.Parameters parameters, Function<E,byte[]> bytesSupplier)
protected	BloomFilter(BloomFilter.Parameters parameters, Function<E,byte[]> bytesSupplier, BitSet bitSet)

Method Summary

Modifier and Type	Method	Description
boolean	add(E element)	Adds element to the filter.
boolean	addAll(Collection<? extends E> c)
BitSet	bitset()	Returns the BitSet holding the internal bloom filter state.
void	clear()
boolean	contains(Object o)	Checks if o is contained in the filter.
boolean	containsAll(Collection<?> c)
protected boolean	getBit(int index)
protected int[]	hashes(E element)	Calculates k hashes for element.
boolean	isEmpty()
Iterator<E>	iterator()	Not supported.
int	k()	Returns the number of hash functions.
int	m()	Returns the number of bits in the filter.
void	merge(BloomFilter<E> other)	Merges this filter with other.
int	n()	Returns the number of items in the filter.
double	p()	Returns the probability of false positives, fraction between 0 and 1.
boolean	remove(Object o)	Not supported.
boolean	removeAll(Collection<?> c)	Not supported.
boolean	retainAll(Collection<?> c)	Not supported.
protected boolean	setBit(int index)
int	size()	Not supported.
Object[]	toArray()	Not supported.
<T> T[]	toArray(T[] a)	Not supported.
String	toString()

Methods inherited from class java.lang.Object

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

Methods inherited from interface java.util.Collection

parallelStream, removeIf, stream, toArray

Methods inherited from interface java.lang.Iterable

forEach

Methods inherited from interface java.util.Set

equals, hashCode, spliterator

Field Details

parameters

protected final BloomFilter.Parameters parameters

bitSet

protected final BitSet bitSet

bytesSupplier

protected final Function<E,byte[]> bytesSupplier

Constructor Details

BloomFilter

protected BloomFilter(BloomFilter.Parameters parameters,
 Function<E,byte[]> bytesSupplier,
 BitSet bitSet)

BloomFilter

protected BloomFilter(BloomFilter.Parameters parameters,
 Function<E,byte[]> bytesSupplier)

BloomFilter

public BloomFilter(int n,
 double p,
 int m,
 int k,
 Function<E,byte[]> bytesSupplier,
 BitSet bitSet)

Create a new bloom filter. Make sure to leave one parameter 0 as it must be derived from the other parameters.

Visit Bloom Filter Calculator to get more information about the implications/calculation of these parameters.

If m is not a multiple of MurmurHash3 x86 32-bit hash, this bloom filter is subject of the "modulo bias" effect.

Parameters:

n - Number of items in the filter. If 0, this value is derived from p, m, and k

p - Probability of false positives, fraction between 0 and 1. If 0, this value is derived from n, m, and k

m - Number of bits in the filter. If 0, this value is derived from n and p

k - Number of hash functions. If 0, this value is derived from m and n

bytesSupplier - a Function that convert objects of type E to byte[] arrays

bitSet - BitSet holding this bloom filter's state. Caller must ensure that it has the correct size.

Throws:

IllegalArgumentException - if one parameter is not 0 or p is not between 0 and 1

NullPointerException - if bytesSupplier is null

BloomFilter

public BloomFilter(int n,
 double p,
 int m,
 int k,
 Function<E,byte[]> bytesSupplier)

Create a new bloom filter. Make sure to leave one parameter 0 as it must be derived from the other parameters.

Visit Bloom Filter Calculator to get more information about the implications/calculation of these parameters.

If m is not a multiple of MurmurHash3 x86 32-bit hash, this bloom filter is subject of the "modulo bias" effect.

Parameters:

n - Number of items in the filter. If 0, this value is derived from p, m, and k

p - Probability of false positives, fraction between 0 and 1. If 0, this value is derived from n, m, and k

m - Number of bits in the filter. If 0, this value is derived from n and p

k - Number of hash functions. If 0, this value is derived from m and n

bytesSupplier - a Function that convert objects of type E to byte[] arrays

Throws:

IllegalArgumentException - if one parameter is not 0 or p is not between 0 and 1

NullPointerException - if bytesSupplier is null

BloomFilter

public BloomFilter(Integer n,
 Double p,
 Function<E,byte[]> bytesSupplier,
 BitSet bitSet)

Create a new bloom filter. Make sure to leave one parameter 0 as it must be derived from the other parameters.

Visit Bloom Filter Calculator to get more information about the implications/calculation of these parameters.

Parameters:

n - Number of items in the filter

p - Probability of false positives, fraction between 0 and 1

bytesSupplier - a Function that convert objects of type E to byte[] arrays

bitSet - BitSet holding this bloom filter's state. Caller must ensure that it has the correct size.

Throws:

IllegalArgumentException - if n or p is 0 or p is not between 0 and 1

NullPointerException - if bytesSupplier is null

BloomFilter

public BloomFilter(Integer n,
 Double p,
 Function<E,byte[]> bytesSupplier)

Create a new bloom filter. Make sure to leave one parameter 0 as it must be derived from the other parameters.

Visit Bloom Filter Calculator to get more information about the implications/calculation of these parameters.

Parameters:

n - Number of items in the filter

p - Probability of false positives, fraction between 0 and 1

bytesSupplier - a Function that convert objects of type E to byte[] arrays

Throws:

IllegalArgumentException - if n or p is 0 or p is not between 0 and 1

NullPointerException - if bytesSupplier is null

Method Details

toString

public String toString()

Overrides:

toString in class Object

size

public int size()

Not supported. Throws UnsupportedOperationException.

Specified by:

size in interface Collection<E>

Specified by:

size in interface Set<E>

Returns:

throws UnsupportedOperationException

Throws:

UnsupportedOperationException

isEmpty

public boolean isEmpty()

Specified by:

isEmpty in interface Collection<E>

Specified by:

isEmpty in interface Set<E>

contains

public boolean contains(Object o)

Checks if o is contained in the filter. False positive messages may occur.

Specified by:

contains in interface Collection<E>

Specified by:

contains in interface Set<E>

Parameters:

o - element to check

Returns:

if element

iterator

public Iterator<E> iterator()

Not supported. Throws UnsupportedOperationException.

Specified by:

iterator in interface Collection<E>

Specified by:

iterator in interface Iterable<E>

Specified by:

iterator in interface Set<E>

Returns:

throws UnsupportedOperationException

Throws:

UnsupportedOperationException

toArray

public Object[] toArray()

Not supported. Throws UnsupportedOperationException.

Specified by:

toArray in interface Collection<E>

Specified by:

toArray in interface Set<E>

Returns:

throws UnsupportedOperationException

Throws:

UnsupportedOperationException

toArray

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

Not supported. Throws UnsupportedOperationException.

Specified by:

toArray in interface Collection<E>

Specified by:

toArray in interface Set<E>

Returns:

throws UnsupportedOperationException

Throws:

UnsupportedOperationException

add

public boolean add(E element)

Adds element to the filter.

Specified by:

add in interface Collection<E>

Specified by:

add in interface Set<E>

Parameters:

element - element to add

Returns:

true if adding this element changed the bloom filter. Can be used as an indicate if element was previously not contained in the filter. But false negatives can occur.

remove

public boolean remove(Object o)

Not supported. Throws UnsupportedOperationException.

Specified by:

remove in interface Collection<E>

Specified by:

remove in interface Set<E>

Returns:

throws UnsupportedOperationException

Throws:

UnsupportedOperationException

containsAll

public boolean containsAll(Collection<?> c)

Specified by:

containsAll in interface Collection<E>

Specified by:

containsAll 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>

retainAll

public boolean retainAll(Collection<?> c)

Not supported. Throws UnsupportedOperationException.

Specified by:

retainAll in interface Collection<E>

Specified by:

retainAll in interface Set<E>

Returns:

throws UnsupportedOperationException

Throws:

UnsupportedOperationException

removeAll

public boolean removeAll(Collection<?> c)

Not supported. Throws UnsupportedOperationException.

Specified by:

removeAll in interface Collection<E>

Specified by:

removeAll in interface Set<E>

Returns:

throws UnsupportedOperationException

Throws:

UnsupportedOperationException

clear

public void clear()

Specified by:

clear in interface Collection<E>

Specified by:

clear in interface Set<E>

n

public int n()

Returns the number of items in the filter.

Returns:

number of items in the filter

p

public double p()

Returns the probability of false positives, fraction between 0 and 1.

Returns:

probability of false positives, fraction between 0 and 1

m

public int m()

Returns the number of bits in the filter.

Returns:

number of bits in the filter

k

public int k()

Returns the number of hash functions.

Returns:

number of hash functions

bitset

public BitSet bitset()

Returns the BitSet holding the internal bloom filter state.

Returns:

BitSet holding the internal bloom filter state

merge

public void merge(BloomFilter<E> other)

Merges this filter with other. While this filter will be contain the merged result, other will be unchanged.

Parameters:

other - bloom filter to merge

Throws:

IllegalArgumentException - if other bloom filter is incompatible (n, p, m, and k must be identical on both filters)

getBit

protected boolean getBit(int index)

setBit

protected boolean setBit(int index)

hashes

protected int[] hashes(E element)

Calculates k hashes for element.

Parameters:

element - element for which hashes are to be calculated.

Returns:

calculated hashes for element