public class KeySelector extends Object
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:
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:
Algorithm details:
| Modifier and Type | Class and Description |
|---|---|
static interface | KeySelector.BitSelectorInterface for extracting bit offsets from cryptographic keys for Bloom filter operations. |
class | KeySelector.GenericBitSelectorGeneric implementation of BitSelector for extracting bit offsets from cryptographic keys. |
class | KeySelector.GenericWordSelectorGeneric implementation of WordSelector for extracting word offsets from cryptographic keys. |
static interface | KeySelector.WordSelectorInterface for extracting word offsets from cryptographic keys for Bloom filter operations. |
| Constructor and Description |
|---|
KeySelector(int m,
int k)Creates a key selector for a Bloom filter with specified parameters. |
| Modifier and Type | Method and 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. |
public KeySelector(int m,
int k)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.
m - size of filter as a power of 2 (determines stride)k - number of 'hash functions' (determines number of offsets to extract)IllegalArgumentException - if parameters exceed implementation limitsImplementation 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.
public void getOffsets(byte[] key,
int[] bitOffset,
int[] wordOffset)key - cryptographic key used in populating the arraysbitOffset - Out parameter of length kwordOffset - Out parameter of length kpublic void getOffsets(byte[] key,
int off,
int len,
int[] bitOffset,
int[] wordOffset)key - cryptographic key used in populating the arraysoff - starting position within the key arraylen - number of bytes to process from the keybitOffset - Out parameter of length kwordOffset - Out parameter of length k