Crate qfilter 

Approximate Membership Query Filter (AMQ-Filter) based on the Rank Select Quotient Filter (RSQF).

This is a small and flexible general-purpose AMQ-Filter, it not only supports approximate membership testing like a bloom filter but also deletions, merging, resizing and serde serialization.

Example

let mut f = qfilter::Filter::new(1000000, 0.01).unwrap();
for i in 0..1000 {
    f.insert(i).unwrap();
}
for i in 0..1000 {
    assert!(f.contains(i));
}

Hasher

Methods accepting T: Hash are provided for convenience using foldhash-portable, which offers high performance and stability across platforms. Note that a fixed seed is used (no DoS resistance) and #[derive(Hash)] output is not guaranteed stable across Rust compiler versions.

Custom hasher

Filter supports a custom BuildHasher via its S type parameter (similar to HashMap). Use Filter::new_with_hasher() and related constructors. Caveats:

• The hasher is not serialized. On deserialization it is reconstructed via S::default(). If that doesn’t produce the correct hasher (e.g. random-seeded hashers), use Filter::with_hasher() to restore it.
• Filters being merged must use the same hasher and seed.
• The same hasher instance (or equivalent seed) must be used for all operations.

Filter size

For a given capacity and error probability the RSQF may require significantly less space than the equivalent bloom filter or other AMQ-Filters.

Bits per item	Error probability when full	Bits per item (cont.)	Error (cont.)
3.125	0.362	19.125	6.87e-06
4.125	0.201	20.125	3.43e-06
5.125	0.106	21.125	1.72e-06
6.125	0.0547	22.125	8.58e-07
7.125	0.0277	23.125	4.29e-07
8.125	0.014	24.125	2.15e-07
9.125	0.00701	25.125	1.07e-07
10.125	0.00351	26.125	5.36e-08
11.125	0.00176	27.125	2.68e-08
12.125	0.000879	28.125	1.34e-08
13.125	0.000439	29.125	6.71e-09
14.125	0.00022	30.125	3.35e-09
15.125	0.00011	31.125	1.68e-09
16.125	5.49e-05	32.125	8.38e-10
17.125	2.75e-05	..	..
18.125	1.37e-05	..	..

Performance

• Lookup/Insert/Delete: O(1) expected case, O(n) worst case with pathological hash collisions
• Memory overhead: 2.125 bits per slot for metadata (occupieds, runends, offset)
• Cache efficiency: Block-based layout with 64-slot blocks improves cache locality

Performance degrades gracefully as occupancy increases. The filter automatically limits occupancy to 95% to maintain good performance.

Legacy x86_64 CPUs support

The implementation assumes popcnt and BMI2 (pdep, tzcnt) instructions are available when compiling for x86_64 targets. These instructions are available on CPUS released after 2015. If they are not available, the Filter constructor will panic.

The legacy_x86_64_support feature enables support for older x86_64 CPUs by using portable fallbacks.

Structs

Builder

Builder for constructing a Filter from fingerprints in sorted (ascending) order.

Filter

Approximate Membership Query Filter (AMQ-Filter) based on the Rank Select Quotient Filter (RSQF).

FilterSpecs

Specifications for a filter with given parameters.

FingerprintIter

An iterator over the fingerprints stored in a Filter or FilterRef.

StableBuildHasher

A BuildHasher that produces StableHasher instances with a fixed seed.

Enums

Error

Errors returned by Filter operations.

Functions

compute_fingerprint_with_hasher

Hashes an item and truncates it to a fingerprint of the given bit size.

filter_specs

Computes filter specifications for a given capacity and false positive rate.

truncate_to_fingerprint

Truncates a hash to a fingerprint of the given bit size.

Type Aliases

FilterRef

A read-only, borrowed view of a Filter.