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.

Author:
  < A HREF="mailto:jddixon@users.sourceforge.net">Jim Dixon BloomSHA1.java and KeySelector.java are BSD licensed from the xlattice app - http://xlattice.sourceforge.net/ minor tweaks by jrandom, exposing unsynchronized access and allowing larger M and K. changes released into the public domain.

### Field Summary

Fields
`protected int[]` `bitOffset`
`protected int` `count`
`protected int[]` `filter`
`protected int` `filterBits`
`protected int` `filterWords`
`protected int` `k`
`protected KeySelector` `ks`
`protected int` `m`
`protected int[]` `wordOffset`

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

Methods
`static String` `btoh(byte b)` convert single byte to String
`int` `capacity()`
`void` `clear()` Synchronized version
`protected void` `doClear()` Clear the filter, unsynchronized
`double` `falsePositives()`
`double` `falsePositives(int n)`
`void` `insert(byte[] b)` Add a key to the set represented by the filter.
`void` `insert(byte[] b, int offset, int len)`
`protected boolean` `isMember(byte[] b)` Is a key in the filter.
`protected boolean` `isMember(byte[] b, int offset, int len)`
`static String` `itoh(int i)` convert 32-bit integer to String
`static String` `keyToString(byte[] key)`
`void` `locked_insert(byte[] b)`
`void` `locked_insert(byte[] b, int offset, int len)`
`boolean` `locked_member(byte[] b)`
`boolean` `locked_member(byte[] b, int offset, int len)`
`static String` `ltoh(long i)` convert 64-bit integer to hex String
`boolean` `member(byte[] b)` Is a key in the filter.
`boolean` `member(byte[] b, int offset, int len)`
`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`

### Field Detail

#### m

    protected final int m

#### k

    protected final int k

#### count

    protected int count

#### filter

    protected final int[] filter

#### ks

    protected KeySelector ks

#### wordOffset

    protected final int[] wordOffset

#### bitOffset

    protected final int[] bitOffset

#### filterBits

    protected final int filterBits

#### filterWords

    protected final int filterWords

### Constructor Detail

#### 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 functionsx See KeySelector for important restriction on max m and k

#### 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()

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

### Method Detail

#### doClear

    protected void doClear()

Clear the filter, unsynchronized

#### clear

    public void clear()

Synchronized version

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

#### capacity

    public final int capacity()

Returns:
  number of bits in filter

#### 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)

#### locked_insert

    public final void locked_insert(byte[] b)

#### locked_insert

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

#### isMember

    protected final boolean isMember(byte[] b)

Is a key in the filter. Sets up the bit and word offset arrays.

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

#### isMember

    protected final boolean isMember(byte[] b,
                   int offset,
                   int len)

#### locked_member

    public final boolean locked_member(byte[] b)

#### locked_member

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

#### 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)

#### falsePositives

    public final double falsePositives(int n)

Parameters:
  `n` - number of set members
Returns:
  approximate false positive rate

#### falsePositives

    public final double falsePositives()

#### keyToString

    public static String keyToString(byte[] key)

#### ltoh

    public static String ltoh(long i)

convert 64-bit integer to hex String

#### itoh

    public static String itoh(int i)

convert 32-bit integer to String

#### btoh

    public static String btoh(byte b)

convert single byte to String