Top Description Inners Fields Constructors Methods
com.google.common.hash

pack-priv sealed Enum BloomFilterStrategies

extends Enum<BloomFilterStrategies>
implements Strategy
Class Inheritance
All Implemented Interfaces
com.google.common.hash.BloomFilter.Strategy, java.io.Serializable
Annotations
@ElementTypesAreNonnullByDefault
Static Imports
com.google.common.base.Preconditions.checkArgument

Collections of strategies of generating the k * log(M) bits required for an element to be mapped to a BloomFilter of M bits and k hash functions. These strategies are part of the serialized form of the Bloom filters that use them, thus they must be preserved as is (no updates allowed, only introduction of new versions).

Important Note

the order of the constants cannot change, and they cannot be deleted - we depend on their ordinal for BloomFilter serialization.

Authors
Dimitris Andreou, Kurt Alfred Kluever

Nested and Inner Type Summary

Modifier and TypeClass and Description
pack-priv static class
BloomFilterStrategies.LockFreeBitArray

Models a lock-free array of bits.

Field Summary

Modifier and TypeField and Description
public static final BloomFilterStrategies
MURMUR128_MITZ_32

See "Less Hashing, Same Performance: Building a Better Bloom Filter" by Adam Kirsch and Michael Mitzenmacher.

public static final BloomFilterStrategies
MURMUR128_MITZ_64

This strategy uses all 128 bits of Hashing#murmur3_128 when hashing.

Constructor Summary

AccessConstructor and Description
private

Method Summary

Modifier and TypeMethod and Description
public static BloomFilterStrategies
public static BloomFilterStrategies[]
Inherited from java.lang.Enum:
clonecompareTodescribeConstableequalsfinalizegetDeclaringClasshashCodenameordinaltoStringvalueOf

Field Detail

MURMUR128_MITZ_32back to summary
public static final BloomFilterStrategies MURMUR128_MITZ_32

See "Less Hashing, Same Performance: Building a Better Bloom Filter" by Adam Kirsch and Michael Mitzenmacher. The paper argues that this trick doesn't significantly deteriorate the performance of a Bloom filter (yet only needs two 32bit hash functions).

MURMUR128_MITZ_64back to summary
public static final BloomFilterStrategies MURMUR128_MITZ_64

This strategy uses all 128 bits of Hashing#murmur3_128 when hashing. It looks different from the implementation in MURMUR128_MITZ_32 because we're avoiding the multiplication in the loop and doing a (much simpler) += hash2. We're also changing the index to a positive number by AND'ing with Long.MAX_VALUE instead of flipping the bits.

Constructor Detail

BloomFilterStrategiesback to summary
private BloomFilterStrategies()

Method Detail

valueOfback to summary
public static BloomFilterStrategies valueOf(String name)
valuesback to summary
public static BloomFilterStrategies[] values()
com.google.common.hash back to summary

pack-priv final Class BloomFilterStrategies.LockFreeBitArray

extends Object
Class Inheritance
  • java.lang.Object
  • com.google.common.hash.BloomFilterStrategies.LockFreeBitArray

Models a lock-free array of bits.

We use this instead of java.util.BitSet because we need access to the array of longs and we need compare-and-swap.

Field Summary

Modifier and TypeField and Description
private final LongAddable
pack-priv final AtomicLongArray
private static final int

Constructor Summary

AccessConstructor and Description
pack-priv
LockFreeBitArray(long bits)

pack-priv
LockFreeBitArray(long[] data)

Method Summary

Modifier and TypeMethod and Description
pack-priv long
bitCount()

Number of set bits (1s).

pack-priv long
bitSize()

Number of bits

pack-priv BloomFilterStrategies.LockFreeBitArray
copy()

pack-priv int
dataLength()

Returns the number of longs in the underlying AtomicLongArray.

public boolean
equals(Object
the reference object with which to compare.
o
)

Overrides java.lang.Object.equals.

Indicates whether some other object is "equal to" this one.
pack-priv boolean
get(long bitIndex)

public int
hashCode()

Overrides java.lang.Object.hashCode.

Returns a hash code value for this object.
pack-priv void
putAll(BloomFilterStrategies.LockFreeBitArray other)

Combines the two BitArrays using bitwise OR.

pack-priv void
putData(int i, long longValue)

ORs the bits encoded in the ith long in the underlying AtomicLongArray with the given value.

pack-priv boolean
set(long bitIndex)

Returns true if the bit changed value.

public static long[]
toPlainArray(AtomicLongArray atomicLongArray)

Careful here: if threads are mutating the atomicLongArray while this method is executing, the final long[] will be a "rolling snapshot" of the state of the bit array.

Inherited from java.lang.Object:
clonefinalizegetClassnotifynotifyAlltoStringwaitwaitwait

Field Detail

bitCountback to summary
private final LongAddable bitCount
databack to summary
pack-priv final AtomicLongArray data
LONG_ADDRESSABLE_BITSback to summary
private static final int LONG_ADDRESSABLE_BITS

Constructor Detail

LockFreeBitArrayback to summary
pack-priv LockFreeBitArray(long bits)
LockFreeBitArrayback to summary
pack-priv LockFreeBitArray(long[] data)

Method Detail

bitCountback to summary
pack-priv long bitCount()

Number of set bits (1s).

Note that because of concurrent set calls and uses of atomics, this bitCount is a (very) close *estimate* of the actual number of bits set. It's not possible to do better than an estimate without locking. Note that the number, if not exactly accurate, is *always* underestimating, never overestimating.

bitSizeback to summary
pack-priv long bitSize()

Number of bits

copyback to summary
pack-priv BloomFilterStrategies.LockFreeBitArray copy()
dataLengthback to summary
pack-priv int dataLength()

Returns the number of longs in the underlying AtomicLongArray.

equalsback to summary
public boolean equals(Object o)

Overrides java.lang.Object.equals.

Doc from java.lang.Object.equals.

Indicates whether some other object is "equal to" this one.

The equals method implements an equivalence relation on non-null object references:

  • It is reflexive: for any non-null reference value x, x.equals(x) should return true.
  • It is symmetric: for any non-null reference values x and y, x.equals(y) should return true if and only if y.equals(x) returns true.
  • It is transitive: for any non-null reference values x, y, and z, if x.equals(y) returns true and y.equals(z) returns true, then x.equals(z) should return true.
  • It is consistent: for any non-null reference values x and y, multiple invocations of x.equals(y) consistently return true or consistently return false, provided no information used in equals comparisons on the objects is modified.
  • For any non-null reference value x, x.equals(null) should return false.

An equivalence relation partitions the elements it operates on into equivalence classes; all the members of an equivalence class are equal to each other. Members of an equivalence class are substitutable for each other, at least for some purposes.

Parameters
o:Object

the reference object with which to compare.

Returns:boolean

true if this object is the same as the obj argument; false otherwise.

Annotations
@Override
getback to summary
pack-priv boolean get(long bitIndex)
hashCodeback to summary
public int hashCode()

Overrides java.lang.Object.hashCode.

Doc from java.lang.Object.hashCode.

Returns a hash code value for this object. This method is supported for the benefit of hash tables such as those provided by java.util.HashMap.

The general contract of hashCode is:

  • Whenever it is invoked on the same object more than once during an execution of a Java application, the hashCode method must consistently return the same integer, provided no information used in equals comparisons on the object is modified. This integer need not remain consistent from one execution of an application to another execution of the same application.
  • If two objects are equal according to the equals method, then calling the hashCode method on each of the two objects must produce the same integer result.
  • It is not required that if two objects are unequal according to the equals method, then calling the hashCode method on each of the two objects must produce distinct integer results. However, the programmer should be aware that producing distinct integer results for unequal objects may improve the performance of hash tables.
Returns:int

a hash code value for this object

Annotations
@Override
putAllback to summary
pack-priv void putAll(BloomFilterStrategies.LockFreeBitArray other)

Combines the two BitArrays using bitwise OR.

Note

Because of the use of atomics, if the other LockFreeBitArray is being mutated while this operation is executing, not all of those new 1's may be set in the final state of this LockFreeBitArray. The ONLY guarantee provided is that all the bits that were set in the other LockFreeBitArray at the start of this method will be set in this LockFreeBitArray at the end of this method.

putDataback to summary
pack-priv void putData(int i, long longValue)

ORs the bits encoded in the ith long in the underlying AtomicLongArray with the given value.

setback to summary
pack-priv boolean set(long bitIndex)

Returns true if the bit changed value.

toPlainArrayback to summary
public static long[] toPlainArray(AtomicLongArray atomicLongArray)

Careful here: if threads are mutating the atomicLongArray while this method is executing, the final long[] will be a "rolling snapshot" of the state of the bit array. This is usually good enough, but should be kept in mind.