org.xlattice.crypto.filters

## Class BloomSHA1

- java.lang.Object
- - org.xlattice.crypto.filters.BloomSHA1

-     public class BloomSHA1
      extends Object

  A Bloom filter for sets of SHA1 digests. A Bloom filter uses a set of k hash functions to determine set membership. Each hash function produces a value in the range 0..M-1. The filter is of size M. To add a member to the set, apply each function to the new member and set the corresponding bit in the filter. For M very large relative to k, this will normally set k bits in the filter. To check whether x is a member of the set, apply each of the k hash functions to x and check whether the corresponding bits are set in the filter. If any are not set, x is definitely not a member. If all are set, x may be a member. The probability of error (the false positive rate) is f = (1 - e^(-kN/M))^k, where N is the number of set members. This class takes advantage of the fact that SHA1 digests are good- quality pseudo-random numbers. The k hash functions are the values of distinct sets of bits taken from the 20-byte SHA1 hash. The number of bits in the filter, M, is constrained to be a power of 2; M == 2^m. The number of bits in each hash function may not exceed floor(m/k). This class is designed to be thread-safe, but this has not been exhaustively tested.

- - ### Nested Class Summary

    Nested Classes
    Modifier and Type | Class and Description
    --- | ---
    `static class` | `BloomSHA1.FilterKey` Stores the (opaque) bloom filter offsets for reuse.

  - ### Constructor Summary

    Constructors
    Constructor and Description
    `BloomSHA1()` Creates a filter of 2^20 bits with k defaulting to 8.
    `BloomSHA1(int m)` Creates a filter of 2^m bits, with the number of 'hash functions" k defaulting to 8.
    `BloomSHA1(int m, int k)` Creates a filter with 2^m bits and k 'hash functions', where each hash function is portion of the 160-bit SHA1 hash.

  - ### Method Summary

    All Methods Instance Methods Concrete Methods
    Modifier and Type | Method and Description
    --- | ---
    `int` | `capacity()` Returns the number of bits in the filter.
    `void` | `clear()` Clears the filter, synchronized.
    `double` | `falsePositives()` Calculates the approximate false positive rate for the current number of set members.
    `double` | `falsePositives(int n)` Calculates the approximate false positive rate for a given number of set members.
    `BloomSHA1.FilterKey` | `getFilterKey(byte[] b, int offset, int len)` Get the bloom filter offsets for reuse.
    `void` | `insert(byte[] b)` Add a key to the set represented by the filter.
    `void` | `insert(byte[] b, int offset, int len)` Add a key to the set represented by the filter.
    `void` | `locked_insert(BloomSHA1.FilterKey fk)` Add the key to the filter.
    `void` | `locked_insert(byte[] b)` Add a key to the filter without synchronization.
    `void` | `locked_insert(byte[] b, int offset, int len)` Add a key to the filter without synchronization.
    `boolean` | `locked_member(BloomSHA1.FilterKey fk)` Is the key in the filter.
    `boolean` | `locked_member(byte[] b)` Checks if a key is in the filter without synchronization.
    `boolean` | `locked_member(byte[] b, int offset, int len)` Checks if a key is in the filter without synchronization.
    `boolean` | `member(byte[] b)` Is a key in the filter.
    `boolean` | `member(byte[] b, int offset, int len)` Is a key in the filter.
    `void` | `release(BloomSHA1.FilterKey fk)` Releases filter key arrays back to the buffer pool.
    `int` | `size()` Returns the number of keys which have been inserted.

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

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

- - ### Constructor Detail

    - #### BloomSHA1

          public BloomSHA1()

      Creates a filter of 2^20 bits with k defaulting to 8.

    - #### BloomSHA1

          public BloomSHA1(int m)

      Creates a filter of 2^m bits, with the number of 'hash functions" k defaulting to 8.
      Parameters:
        `m` - determines size of filter

    - #### BloomSHA1

          public BloomSHA1(int m,
                           int k)

      Creates a filter with 2^m bits and k 'hash functions', where each hash function is portion of the 160-bit SHA1 hash.
      Parameters:
        `m` - determines number of bits in filter
        `k` - number of hash functions See KeySelector for important restriction on max m and k

  - ### Method Detail

    - #### capacity

          public final int capacity()

      Returns the number of bits in the filter.
      Returns:
        number of bits in filter

    - #### clear

          public void clear()

      Clears the filter, synchronized.

    - #### falsePositives

          public final double falsePositives()

      Calculates the approximate false positive rate for the current number of set members.
      Returns:
        approximate false positive rate

    - #### falsePositives

          public final double falsePositives(int n)

      Calculates the approximate false positive rate for a given number of set members.
      Parameters:
        `n` - number of set members
      Returns:
        approximate false positive rate

    - #### getFilterKey

          public BloomSHA1.FilterKey getFilterKey(byte[] b,
                                                  int offset,
                                                  int len)

      Get the bloom filter offsets for reuse. Caller should call release(rv) when done with it.
      Parameters:
        `b` - byte array representing a key (SHA1 digest)
        `offset` - starting offset in the byte array
        `len` - number of bytes to use
      Returns:
        filter key containing the offsets

    - #### insert

          public void insert(byte[] b)

      Add a key to the set represented by the filter. XXX This version does not maintain 4-bit counters, it is not a counting Bloom filter.
      Parameters:
        `b` - byte array representing a key (SHA1 digest)

    - #### insert

          public void insert(byte[] b,
                             int offset,
                             int len)

      Add a key to the set represented by the filter. XXX This version does not maintain 4-bit counters, it is not a counting Bloom filter.
      Parameters:
        `b` - byte array representing a key (SHA1 digest)
        `offset` - starting offset in the byte array
        `len` - number of bytes to use

    - #### locked_insert

          public void locked_insert(BloomSHA1.FilterKey fk)

      Add the key to the filter.
      Parameters:
        `fk` - filter key containing offsets

    - #### locked_insert

          public final void locked_insert(byte[] b)

      Add a key to the filter without synchronization.
      Parameters:
        `b` - byte array representing a key (SHA1 digest)

    - #### locked_insert

          public final void locked_insert(byte[] b,
                                          int offset,
                                          int len)

      Add a key to the filter without synchronization.
      Parameters:
        `b` - byte array representing a key (SHA1 digest)
        `offset` - starting offset in the byte array
        `len` - number of bytes to use

    - #### locked_member

          public boolean locked_member(BloomSHA1.FilterKey fk)

      Is the key in the filter.
      Parameters:
        `fk` - filter key containing offsets
      Returns:
        true if the key is in the filter

    - #### locked_member

          public final boolean locked_member(byte[] b)

      Checks if a key is in the filter without synchronization.
      Parameters:
        `b` - byte array representing a key (SHA1 digest)
      Returns:
        true if b is in the filter

    - #### locked_member

          public final boolean locked_member(byte[] b,
                                             int offset,
                                             int len)

      Checks if a key is in the filter without synchronization.
      Parameters:
        `b` - byte array representing a key (SHA1 digest)
        `offset` - starting offset in the byte array
        `len` - number of bytes to use
      Returns:
        true if b is in the filter

    - #### member

          public final boolean member(byte[] b)

      Is a key in the filter. External interface, internally synchronized.
      Parameters:
        `b` - byte array representing a key (SHA1 digest)
      Returns:
        true if b is in the filter

    - #### member

          public final boolean member(byte[] b,
                                      int offset,
                                      int len)

      Is a key in the filter. External interface, internally synchronized.
      Parameters:
        `b` - byte array representing a key (SHA1 digest)
        `offset` - starting offset in the byte array
        `len` - number of bytes to use
      Returns:
        true if b is in the filter

    - #### release

          public void release(BloomSHA1.FilterKey fk)

      Releases filter key arrays back to the buffer pool.
      Parameters:
        `fk` - filter key to release

    - #### size

          public final int size()

      Returns the number of keys which have been inserted. This class (BloomSHA1) does not guarantee uniqueness in any sense; if the same key is added N times, the number of set members reported will increase by N.
      Returns:
        number of set members