java.lang.Object
org.xlattice.crypto.filters.KeySelector
public class KeySelectorextends Object
Utility class for extracting word and bit offsets from cryptographic keys for Bloom filter operations.

KeySelector provides the core functionality needed to map cryptographic keys to the specific bit and word positions used by Bloom filter hash functions. This is essential for implementing efficient Bloom filters where each hash function needs to examine specific bits or words from the key.

The class supports two types of selectors:

  • BitSelector: Extracts individual bit positions (5-bit stride)
  • WordSelector: Extracts word positions ((m-5)-bit stride)

Usage example: Create a KeySelector with m and k parameters, then call getOffsets() to extract bit and word offsets from a key.

Example: new KeySelector(1024, 5) creates a selector for m=1024, k=5.

Constraints and limitations:

  • Maximum supported for 32-byte keys: m=23, k=11
  • Formula constraint: ((5k + (k-1)(m-5)) / 8) + 2 ≤ keySizeInBytes
  • All methods are thread-safe for concurrent access

Algorithm details:

  • Bit selectors use 5-bit stride for optimal distribution
  • Word selectors use (m-5)-bit stride to avoid bit selector overlap
  • Both use lookup tables (UNMASK/MASK) for efficient bit operations
BloomSHA1.java and KeySelector.java are BSD licensed from 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. As of 0.8.11, bitoffset and wordoffset out parameters moved from fields to selector arguments, to allow concurrency. ALl methods are now thread-safe.

  • Nested Class Summary

    Nested Classes
    Modifier and Type
    Class
    Description
    static interface 
    KeySelector.BitSelector
    Interface for extracting bit offsets from cryptographic keys for Bloom filter operations.
    class 
    KeySelector.GenericBitSelector
    Generic implementation of BitSelector for extracting bit offsets from cryptographic keys.
    class 
    KeySelector.GenericWordSelector
    Generic implementation of WordSelector for extracting word offsets from cryptographic keys.
    static interface 
    KeySelector.WordSelector
    Interface for extracting word offsets from cryptographic keys for Bloom filter operations.

  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    private final KeySelector.BitSelector
    bitSel
    Which individual bits are selected.
    private final int
    k
    Bits selected from the block.
    private final int
    m
    Bits in the full key block.
    private static final int[]
    MASK
    AND with byte to zero out index-many bits
    private static final int
    TWO_UP_15
    2 to the 15, the largest table size allowed.
    private static final int[]
    UNMASK
    AND with byte to expose index-many bits
    private final KeySelector.WordSelector
    wordSel
    Which words are selected.

  • Constructor Summary

    Constructors
    Constructor
    Description
    KeySelector(int m, int k)
    Creates a key selector for a Bloom filter with specified parameters.

  • Method Summary

    All Methods
    Modifier and Type
    Method
    Description
    void
    getOffsets(byte[] key, int[] bitOffset, int[] wordOffset)
    Given a key, populate the word and bit offset arrays, each of which has k elements.
    void
    getOffsets(byte[] key, int off, int len, int[] bitOffset, int[] wordOffset)
    Given a key, populate the word and bit offset arrays, each of which has k elements.

    Methods inherited from class Object

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

  • Field Details

    • m

      private final int m
      Bits in the full key block.

    • k

      private final int k
      Bits selected from the block.

    • bitSel

      private final KeySelector.BitSelector bitSel
      Which individual bits are selected.

    • wordSel

      private final KeySelector.WordSelector wordSel
      Which words are selected.

    • UNMASK

      private static final int[] UNMASK
      AND with byte to expose index-many bits

    • MASK

      private static final int[] MASK
      AND with byte to zero out index-many bits

    • TWO_UP_15

      private static final int TWO_UP_15
      2 to the 15, the largest table size allowed.
      See Also:

  • Constructor Details

    • KeySelector

      public KeySelector(int m, int k)
      Creates a key selector for a Bloom filter with specified parameters.

      This constructor initializes both bit and word selectors with the appropriate algorithms for the given m and k values. The selectors will then be used to extract offsets from keys for Bloom filter operations.

      Performance characteristics:
      - Bit selection: O(k) time complexity, constant space
      - Word selection: O(k) time complexity, constant space
      - Both implementations use lookup tables for efficiency
      - Thread-safe: no shared mutable state

      Memory usage: O(1) additional space for lookup tables and selector instances.

      Parameters:
      m - size of filter as a power of 2 (determines stride)
      k - number of 'hash functions' (determines number of offsets to extract)
      Throws:
      IllegalArgumentException - if parameters exceed implementation limits

      Implementation constraints:
      - Maximum for 32-byte keys: m=23, k=11
      - Formula constraint: ((5k + (k-1)(m-5)) / 8) + 2 ≤ keySizeInBytes
      - Larger values may cause ArrayIndexOutOfBoundsException
      - m must be ≥ 2 for valid stride calculations

      Note: The constraint formula ensures that the calculated offsets don't exceed the key boundaries. For larger m/k values, consider using larger key sizes or alternative selection algorithms.

  • Method Details

    • getOffsets

      public void getOffsets(byte[] key, int[] bitOffset, int[] wordOffset)
      Given a key, populate the word and bit offset arrays, each of which has k elements.
      Parameters:
      key - cryptographic key used in populating the arrays
      bitOffset - Out parameter of length k
      wordOffset - Out parameter of length k

    • getOffsets

      public void getOffsets(byte[] key, int off, int len, int[] bitOffset, int[] wordOffset)
      Given a key, populate the word and bit offset arrays, each of which has k elements.
      Parameters:
      key - cryptographic key used in populating the arrays
      off - starting position within the key array
      len - number of bytes to process from the key
      bitOffset - Out parameter of length k
      wordOffset - Out parameter of length k