java.lang.Object
org.klomp.snark.dht.BloomFilter
class BloomFilterextends Object
A BEP 33 bloom filter used to estimate the size of a DHT swarm from a get_peers response.

The filter has 256 bytes (m = 2048 bits) and two hash functions (k = 2) derived from the first four bytes of the SHA-1 of the inserted value, as specified in BEP 33. In I2P the inserted values are the 32-byte destination hashes of the peers rather than the IP addresses of the specification, as that is how peers are identified on the I2P network; both the filter builder and the estimator insert the same hashes, so the resulting filters stay compatible between clients.

The number of inserted values can be estimated from the count of zero bits, see estimateSize(). The estimate is only reliable up to a few thousand inserted values; the filter saturates around 8000.

  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    private final byte[]
    _bloom
    The filter's bits.
    private static final int
    K
    Number of hash functions, as specified in BEP 33.
    private static final int
    M
    Number of bits in the filter, as specified in BEP 33.
    (package private) static final int
    SIZE
    Size of the filter in bytes, as specified in BEP 33.

  • Constructor Summary

    Constructors
    Constructor
    Description
    BloomFilter()
    Create a new empty filter.
    BloomFilter(byte[] data)
    Create a filter from data received in a get_peers response.

  • Method Summary

    Private Methods
    Modifier and Type
    Method
    Description
    (package private) boolean
    contains(byte[] data)
    Test whether a value is probably contained in the filter.
    (package private) int
    countZeroBits()
    Count the number of bits in the filter that are still zero.
    (package private) double
    estimateSize()
    Estimate the number of values inserted into the filter.
    (package private) byte[]
    getData()
    The filter data.
    (package private) void
    insert(byte[] data)
    Insert a value into the filter, setting the two bits at indices derived from the SHA-1 of the value.
    private boolean
    isSet(int index)
    True if the bit at an index is set.
    private void
    setBit(int index)
    Sets the bit at an index, spanning bytes as needed.

    Methods inherited from class Object

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

  • Field Details

    • K

      private static final int K
      Number of hash functions, as specified in BEP 33.
      See Also:

    • M

      private static final int M
      Number of bits in the filter, as specified in BEP 33.
      See Also:

    • SIZE

      static final int SIZE
      Size of the filter in bytes, as specified in BEP 33.
      See Also:

    • _bloom

      private final byte[] _bloom
      The filter's bits.

  • Constructor Details

    • BloomFilter

      BloomFilter()
      Create a new empty filter.

    • BloomFilter

      BloomFilter(byte[] data)
      Create a filter from data received in a get_peers response.
      Parameters:
      data - 256 bytes of filter data
      Throws:
      IllegalArgumentException - if the data is not 256 bytes

  • Method Details

    • insert

      void insert(byte[] data)
      Insert a value into the filter, setting the two bits at indices derived from the SHA-1 of the value.
      Parameters:
      data - the value to insert, e.g. a 32-byte destination hash

    • contains

      boolean contains(byte[] data)
      Test whether a value is probably contained in the filter.
      Parameters:
      data - the value to test
      Returns:
      true if both of the value's bits are set

    • setBit

      private void setBit(int index)
      Sets the bit at an index, spanning bytes as needed.
      Parameters:
      index - the bit position

    • isSet

      private boolean isSet(int index)
      True if the bit at an index is set.
      Parameters:
      index - the bit position
      Returns:
      true if that bit is set

    • countZeroBits

      int countZeroBits()
      Count the number of bits in the filter that are still zero.
      Returns:
      the zero bit count

    • estimateSize

      double estimateSize()
      Estimate the number of values inserted into the filter.

      Uses the equation from BEP 33, log(c/m) / (k * log(1 - 1/m)), where c is the count of zero bits. The estimate is only meaningful while the filter is less than about half full; it breaks down as the filter approaches 8000 inserted values.

      Returns:
      the estimated number of inserted values, 0 if the filter is full

    • getData

      byte[] getData()
      The filter data.
      Returns:
      256 bytes