Type Members

1.  sealed abstract class BitSet extends AnyRef

   A fast, immutable BitSet.

   A fast, immutable BitSet.

   This implementation is taken from cats-collections. https://github.com/typelevel/cats-collections/blob/0336992942aba9aba4a322b629447fcabe251920/core/src/main/scala/cats/collections/BitSet.scala

   A Bitset is a specialized type of set that tracks the Int values it contains: for each integer value, a BitSet uses a single bit to track whether the value is present (1) or absent (0). Bitsets are often sparse, since "missing" bits can be assumed to be zero.

   Unlike scala's default immutable this BitSet does not do a full copy on each added value.

   Internally the implementation is a tree. Each leaf uses an Array[Long] value to hold up to 2048 bits, and each branch uses an Array[BitSet] to hold up to 32 subtrees (null subtrees are treated as empty).

   Bitset treats the values it stores as 32-bit unsigned values, which is relevant to the internal addressing methods as well as the order used by iterator.

   The benchmarks suggest this bitset is MUCH faster than Scala's built-in bitset for cases where you may need many modifications and merges, (for example in a BloomFilter).

2.  final case class BloomFilter[A](numHashes: Int, width: Int)(implicit hash: Hash128[A]) extends Product with Serializable

   Bloom Filter - a probabilistic data structure to test presence of an element.

   Bloom Filter - a probabilistic data structure to test presence of an element.

   Operations 1) insert: hash the value k times, updating the bitfield at the index equal to each hashed value 2) query: hash the value k times. If there are k collisions, then return true; otherwise false.

   http://en.wikipedia.org/wiki/Bloom_filter