Crate subms_cuckoo_filter 

Cuckoo filter. Bloom-alternative that supports delete.

Two candidate buckets per key: i1 = h(key) & mask, i2 = i1 ^ h(fp) & mask. Each bucket holds B 8-bit fingerprints. Insert tries i1 then i2; if both full, kicks a random fingerprint out and re-places it. Delete removes a matching fingerprint from either bucket.

use subms_cuckoo_filter::CuckooFilter;
let mut cf = CuckooFilter::with_capacity(10_000);
assert!(cf.insert("hello"));
assert!(cf.contains("hello"));
assert!(cf.delete("hello"));
assert!(!cf.contains("hello"));

Single writer. CuckooFilter is Send + Sync in the ordinary Rust sense (&mut for every mutation), and has no internal synchronisation: two threads mutating one filter is a compile error, and shared read access while a writer holds &mut is too. For read fan-out across threads take a CuckooSnapshot behind the concurrent-reads feature.

Full writeup, design notes and measured benchmarks: https://www.submillisecond.com/cookbook/recipes/subms-cuckoo-filter

Re-exports

pub use features::compressed_buckets::CompressedCuckooFilter;

pub use features::concurrent_reads::CuckooSnapshot;

pub use features::dynamic::DynamicCuckooFilter;

pub use features::variable_fingerprint::FingerprintWidth;

pub use features::variable_fingerprint::VariableFpCuckooFilter;

Modules

features

Opt-in feature catalog. Each submodule is gated by its own Cargo feature flag and adds a specific capability to the base cuckoo filter without bloating the core build.

recipe

SubMsRecipe impl.

Structs

CuckooFilter

Enums

CuckooError

Every way an operation on a CuckooFilter can refuse.

Constants

BUCKET_SIZE

Slots per bucket. 4 gives ~95% load factor; higher values raise load factor but slow lookups linearly.

FINGERPRINT_BITS

Fingerprint bits held per slot in the base filter. The variable-fingerprint feature widens this to 12 or 16.

MAX_KICKS

Max kick-out attempts during a single insert.