quickbloom 0.2.0

An industry-grade, highly scalable Bloom filter with lock-free concurrency, blocked layout, and automatic persistence.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

//! Hash utilities for Bloom filters.
//!
//! Uses enhanced double hashing with `ahash` to efficiently generate multiple
//! high-quality hash values from two independent base hashes.
//!
//! ## Algorithm
//! Given two base hashes `h1` and `h2`, the i-th hash is computed as:
//! ```text
//! h(i) = h1 + i * h2 + i^2   (enhanced double hashing)
//! ```
//! The quadratic term `i^2` reduces clustering that can occur in pure double
//! hashing at high fill ratios, improving the false-positive rate in practice.

use ahash::AHasher;
use std::hash::{BuildHasher, Hash, Hasher};

/// Generates Bloom filter hash indices using enhanced double hashing.
///
/// This struct is internal and optimized for speed and low collision rates.
pub(crate) struct HashGenerator {
    hash1: u64,
    hash2: u64,
}

impl HashGenerator {
    /// Create a new hash generator for a given item.
    #[inline]
    pub fn new<T: Hash>(item: &T) -> Self {
        let hash1 = Self::ahash(item, 0xdead_beef_cafe_babe_u128);
        let hash2 = Self::ahash(item, 0x0123_4567_89ab_cdef_u128);

        // Make hash2 odd and non-zero so the modular walk hits every slot.
        let hash2 = hash2 | 1;

        Self { hash1, hash2 }
    }

    /// Get the i-th hash value using enhanced double hashing.
    ///
    /// `h(i) = h1 + i*h2 + i^2` reduces bit clustering at high fill ratios
    /// compared to pure linear or double hashing.
    #[inline]
    pub fn nth(&self, i: usize) -> u64 {
        let i = i as u64;
        self.hash1
            .wrapping_add(i.wrapping_mul(self.hash2))
            .wrapping_add(i.wrapping_mul(i))
    }

    #[inline]
    fn ahash<T: Hash>(item: &T, seed: u128) -> u64 {
        // ahash::RandomState::with_seeds provides stable seeded hashing.
        let lo = seed as u64;
        let hi = (seed >> 64) as u64;
        let state = ahash::RandomState::with_seeds(lo, hi, lo ^ hi, lo.wrapping_add(hi));
        let mut hasher: AHasher = state.build_hasher();
        item.hash(&mut hasher);
        hasher.finish()
    }
}