BloomFilter (ORC Core 1.6.6 API)
Date: 2021-01-13

org.apache.orc.util

## Class BloomFilter

- java.lang.Object
- - org.apache.orc.util.BloomFilter

- Direct Known Subclasses:
    BloomFilterUtf8

      public class BloomFilter
      extends Object

  BloomFilter is a probabilistic data structure for set membership check. BloomFilters are highly space efficient when compared to using a HashSet. Because of the probabilistic nature of bloom filter false positive (element not present in bloom filter but test() says true) are possible but false negatives are not possible (if element is present then test() will never say false). The false positive probability is configurable (default: 5%) depending on which storage requirement may increase or decrease. Lower the false positive probability greater is the space requirement. Bloom filters are sensitive to number of elements that will be inserted in the bloom filter. During the creation of bloom filter expected number of entries must be specified. If the number of insertions exceed the specified initial number of entries then false positive probability will increase accordingly. Internally, this implementation of bloom filter uses Murmur3 fast non-cryptographic hash algorithm. Although Murmur2 is slightly faster than Murmur3 in Java, it suffers from hash collisions for specific sequence of repeating bytes. Check the following link for more info https://code.google.com/p/smhasher/wiki/MurmurHash2Flaw Note that this class is here for backwards compatibility, because it uses the JVM default character set for strings. All new users should BloomFilterUtf8, which always uses UTF8 for the encoding.

- - ### Nested Class Summary

    Nested Classes
    Modifier and Type | Class and Description
    --- | ---
    `static class` | `BloomFilter.BitSet` Bare metal bit set implementation.

  - ### Field Summary

    Fields
    Modifier and Type | Field and Description
    --- | ---
    `static double` | `DEFAULT_FPP`

  - ### Constructor Summary

    Constructors
    Constructor and Description
    `BloomFilter(long expectedEntries)`
    `BloomFilter(long[] bits, int numFuncs)` A constructor to support rebuilding the BloomFilter from a serialized representation.
    `BloomFilter(long expectedEntries, double fpp)`

  - ### Method Summary

    All Methods Instance Methods Concrete Methods
    Modifier and Type | Method and Description
    --- | ---
    `void` | `add(byte[] val)`
    `void` | `addBytes(byte[] val, int offset, int length)`
    `void` | `addDouble(double val)`
    `void` | `addLong(long val)`
    `void` | `addString(String val)`
    `boolean` | `equals(Object other)`
    `long[]` | `getBitSet()`
    `int` | `getBitSize()`
    `int` | `getNumHashFunctions()`
    `int` | `hashCode()`
    `void` | `merge(BloomFilter that)` Merge the specified bloom filter with current bloom filter.
    `void` | `reset()`
    `long` | `sizeInBytes()`
    `boolean` | `test(byte[] val)`
    `boolean` | `testBytes(byte[] val, int offset, int length)`
    `boolean` | `testDouble(double val)`
    `boolean` | `testLong(long val)`
    `boolean` | `testString(String val)`
    `String` | `toString()`

    - ### Methods inherited from class java.lang.Object

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

- - ### Field Detail

    - #### DEFAULT_FPP

          public static final double DEFAULT_FPP

      See Also:
        Constant Field Values

  - ### Constructor Detail

    - #### BloomFilter

          public BloomFilter(long expectedEntries)

    - #### BloomFilter

          public BloomFilter(long expectedEntries,
                             double fpp)

    - #### BloomFilter

          public BloomFilter(long[] bits,
                             int numFuncs)

      A constructor to support rebuilding the BloomFilter from a serialized representation.
      Parameters:
        `bits` - the serialized bits
        `numFuncs` - the number of functions used

  - ### Method Detail

    - #### equals

          public boolean equals(Object other)

      Overrides:
        `equals` in class `Object`

    - #### hashCode

          public int hashCode()

      Overrides:
        `hashCode` in class `Object`

    - #### add

          public void add(byte[] val)

    - #### addBytes

          public void addBytes(byte[] val,
                               int offset,
                               int length)

    - #### addString

          public void addString(String val)

    - #### addLong

          public void addLong(long val)

    - #### addDouble

          public void addDouble(double val)

    - #### test

          public boolean test(byte[] val)

    - #### testBytes

          public boolean testBytes(byte[] val,
                                   int offset,
                                   int length)

    - #### testString

          public boolean testString(String val)

    - #### testLong

          public boolean testLong(long val)

    - #### testDouble

          public boolean testDouble(double val)

    - #### sizeInBytes

          public long sizeInBytes()

    - #### getBitSize

          public int getBitSize()

    - #### getNumHashFunctions

          public int getNumHashFunctions()

    - #### getBitSet

          public long[] getBitSet()

    - #### toString

          public String toString()

      Overrides:
        `toString` in class `Object`

    - #### merge

          public void merge(BloomFilter that)

      Merge the specified bloom filter with current bloom filter.
      Parameters:
        `that` - - bloom filter to merge

    - #### reset

          public void reset()

Copyright © 2013–2021 The Apache Software Foundation. All rights reserved.