bloom-lib 1.0.0

Probabilistic data structure library: Bloom filters, Cuckoo filters, Count-Min Sketch, HyperLogLog, MinHash, and Top-K. Tunable false-positive rates, serializable state, merge support, and streaming-safe updates.
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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136

//! # bloom-lib
//!
//! Probabilistic data structures for Rust.
//!
//! This crate provides space-efficient structures that answer set-membership,
//! cardinality, frequency, and similarity questions with bounded, tunable
//! error in a fraction of the memory an exact structure would require. They are
//! built for streaming workloads: insertions are allocation-free, state is
//! serializable, and compatible structures can be merged.
//!
//! ## Available structures
//!
//! - [`BloomFilter`] — probabilistic set membership with a tunable
//!   false-positive rate.
//! - [`CuckooFilter`] — approximate membership that also supports deletion.
//! - [`CountMinSketch`] — approximate frequency estimation for a stream.
//! - [`HyperLogLog`] — distinct-count (cardinality) estimation in tiny memory.
//! - [`MinHash`] — Jaccard similarity estimation between sets.
//! - [`TopK`] — the most frequent items (heavy hitters) in a stream.
//!
//! ## Example
//!
//! ```
//! # #[cfg(feature = "alloc")] {
//! use bloom_lib::BloomFilter;
//!
//! // A filter sized for 100,000 items at a 0.1% false-positive rate.
//! let mut filter = BloomFilter::new(100_000, 0.001).unwrap();
//!
//! filter.insert("session-token");
//! assert!(filter.contains("session-token"));
//! assert!(!filter.contains("never-seen"));
//! # }
//! ```
//!
//! ## Hashing
//!
//! Every structure is generic over [`core::hash::BuildHasher`] and defaults to
//! the deterministic [`hash::DefaultHashBuilder`]. Determinism makes filters
//! reproducible, mergeable, and stable across serialization. Supply a
//! randomly-seeded hasher when the inputs are adversarial. See the [`hash`]
//! module for details.
//!
//! ## Feature flags
//!
//! - `std` *(default)* — enables every structure and the
//!   [`std::error::Error`] implementation for [`Error`].
//! - `alloc` — enables every structure without requiring `std`, for
//!   heap-capable `no_std` targets. Implied by `std`.
//! - `serde` — derives `Serialize`/`Deserialize` for every structure. Implies
//!   `alloc`.
//!
//! With none of these features the crate exposes only [`VERSION`] and [`Error`].
//!
//! ## License
//!
//! Dual-licensed under Apache-2.0 OR MIT.

#![doc(html_root_url = "https://docs.rs/bloom-lib")]
#![cfg_attr(docsrs, feature(doc_cfg))]
#![cfg_attr(not(feature = "std"), no_std)]
#![deny(missing_docs)]
#![deny(unsafe_op_in_unsafe_fn)]
#![deny(unused_must_use)]
#![deny(unused_results)]
#![deny(clippy::unwrap_used)]
#![deny(clippy::expect_used)]
#![deny(clippy::todo)]
#![deny(clippy::unimplemented)]
#![deny(clippy::print_stdout)]
#![deny(clippy::print_stderr)]
#![deny(clippy::dbg_macro)]
#![deny(clippy::unreachable)]
#![deny(clippy::undocumented_unsafe_blocks)]
#![deny(clippy::missing_safety_doc)]

#[cfg(feature = "alloc")]
extern crate alloc;

mod error;
pub mod hash;

pub use crate::error::Error;

#[cfg(feature = "alloc")]
mod bit_set;
#[cfg(feature = "alloc")]
mod bloom;
#[cfg(feature = "alloc")]
mod count_min;
#[cfg(feature = "alloc")]
mod cuckoo;
#[cfg(feature = "alloc")]
mod hyperloglog;
#[cfg(feature = "alloc")]
mod minhash;
#[cfg(feature = "alloc")]
mod topk;

#[cfg(feature = "alloc")]
pub use crate::bloom::BloomFilter;
#[cfg(feature = "alloc")]
pub use crate::count_min::CountMinSketch;
#[cfg(feature = "alloc")]
pub use crate::cuckoo::CuckooFilter;
#[cfg(feature = "alloc")]
pub use crate::hyperloglog::HyperLogLog;
#[cfg(feature = "alloc")]
pub use crate::minhash::MinHash;
#[cfg(feature = "alloc")]
pub use crate::topk::TopK;

/// Convenient re-exports for typical usage.
///
/// Glob-importing the prelude brings the structures, the hashing types, and the
/// error type into scope:
///
/// ```
/// # #[cfg(feature = "alloc")] {
/// use bloom_lib::prelude::*;
///
/// let mut filter = BloomFilter::new(1_000, 0.01).unwrap();
/// filter.insert("hello");
/// assert!(filter.contains("hello"));
/// # }
/// ```
pub mod prelude {
    pub use crate::hash::{DefaultHashBuilder, DefaultHasher};
    pub use crate::Error;

    #[cfg(feature = "alloc")]
    pub use crate::{BloomFilter, CountMinSketch, CuckooFilter, HyperLogLog, MinHash, TopK};
}

/// Crate version string, populated by Cargo at build time.
pub const VERSION: &str = env!("CARGO_PKG_VERSION");