Struct BloomParams

pub struct BloomParams {
    pub byte_size: usize,
    pub k_hashes: usize,
}

Optimal bloom parameters for some false positive rate at a maximum number of elements added, or for some byte size with target element count, etc.

Captures the bloom filter byte size needed as well as the number of hash function evaluations needed per item to insert.

To construct this, use

• BloomParams::new_from_fpr for constructing this from a given false positive rate and desired capacity,
• similarly BloomParams::new_from_fpr_po2, but with power-of-two sizes,
• BloomParams::new_from_size for constructing from desired size and capacity.

Fields

byte_size: usize

size of the bloom filter in bytes, non-zero

k_hashes: usize

hashing functions used/number of bits set per element, non-zero

Implementations

impl BloomParams

pub fn new_from_fpr(n_elems: u64, fpr: f64) -> Self

Construct optimal bloom parameters for given number maximum elements that the bloom filter will hold as well as the approximate false positive rate it should have at that capacity.

n_elems must be non-zero, and fpr must be between 0 and 1, exclusive.

This will generate non-power-of-two sizes for bloom filters. For a variant that power-of-two (po2) sizes, see BloomParams::new_from_fpr_po2.

Example

use deterministic_bloom::common::BloomParams;

// figure out bloom parameters for 47 elements with a one in a billion false positive rate:
let params = BloomParams::new_from_fpr(47, 1.0 / 1_000_000_000.0);
assert_eq!(params, BloomParams {
    byte_size: 254,
    k_hashes: 30,
})

pub fn new_from_fpr_po2(n_elems: u64, fpr: f64) -> Self

Construct optimal bloom parameters for given capacity n_elems and false positive rate, where the target size will always be a power-of-two.

n_elems must be non-zero, and fpr must be between 0.0 and 1.0, exclusive.

It is often desirable to go for power-of-two sizes, since that simplifies generating bit indices by not requiring rejection sampling.

Example

use deterministic_bloom::common::BloomParams;

// Generate some bloom parameters
let params = BloomParams::new_from_fpr_po2(1_000_000, 0.0001);
assert_eq!(params.byte_size, params.byte_size.next_power_of_two());

pub fn new_from_size(byte_size: usize, n_elems: u64) -> Self

Construct optimal bloom parameters for given bloom filter byte_size and capacity n_elems.

pub fn false_positive_rate_at(&self, n_elems: u64) -> f64

Compute the approximate false positive rate at n_elems. n_elems must be non-zero.

Returns the false positive rate as a number between 0.0 and 1.0.

Trait Implementations

impl Clone for BloomParams

fn clone(&self) -> BloomParams

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for BloomParams

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl Ord for BloomParams

fn cmp(&self, other: &BloomParams) -> Ordering

This method returns an Ordering between self and other.

fn max(self, other: Self) -> Self

where Self: Sized,

Compares and returns the maximum of two values.

fn min(self, other: Self) -> Self

where Self: Sized,

Compares and returns the minimum of two values.

fn clamp(self, min: Self, max: Self) -> Self

where Self: Sized,

Restrict a value to a certain interval.

impl PartialEq for BloomParams

fn eq(&self, other: &BloomParams) -> bool

Tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl PartialOrd for BloomParams

fn partial_cmp(&self, other: &BloomParams) -> Option<Ordering>

This method returns an ordering between self and other values if one exists.

fn lt(&self, other: &Rhs) -> bool

Tests less than (for self and other) and is used by the < operator.

fn le(&self, other: &Rhs) -> bool

Tests less than or equal to (for self and other) and is used by the <= operator.

fn gt(&self, other: &Rhs) -> bool

Tests greater than (for self and other) and is used by the > operator.

fn ge(&self, other: &Rhs) -> bool

Tests greater than or equal to (for self and other) and is used by the >= operator.

impl Eq for BloomParams

impl StructuralPartialEq for BloomParams