#cuckoo-filter #bloom-filter #insert #scalable-cuckoo-filter

scalable_cuckoo_filter

A variant of Cuckoo Filter whose size automatically scales as necessary

12 releases

0.4.0 Apr 23, 2025
0.3.2 Apr 24, 2024
0.2.4 Mar 11, 2024
0.2.3 Oct 31, 2023
0.1.1 Jan 20, 2018

#213 in Data structures

Download history 162/week @ 2025-01-10 187/week @ 2025-01-17 293/week @ 2025-01-24 580/week @ 2025-01-31 313/week @ 2025-02-07 179/week @ 2025-02-14 691/week @ 2025-02-21 296/week @ 2025-02-28 340/week @ 2025-03-07 367/week @ 2025-03-14 178/week @ 2025-03-21 242/week @ 2025-03-28 206/week @ 2025-04-04 190/week @ 2025-04-11 244/week @ 2025-04-18 206/week @ 2025-04-25

872 downloads per month
Used in 2 crates

MIT license

38KB
803 lines

scalable_cuckoo_filter

scalable_cuckoo_filter Documentation Actions Status License: MIT

A variant of Cuckoo Filter whose size automatically scales as necessary.

Documentation

Examples

Basic usage:

use scalable_cuckoo_filter::ScalableCuckooFilter;

let mut filter = ScalableCuckooFilter::new(100, 0.001);
assert!(!filter.contains("foo"));
filter.insert("foo");
assert!(filter.contains("foo"));

Filter grows automatically:

use scalable_cuckoo_filter::ScalableCuckooFilter;

let mut filter = ScalableCuckooFilter::new(100, 0.001);
assert_eq!(filter.capacity(), 128);

for i in 0..1000 {
    filter.insert(&i);
}
assert_eq!(filter.capacity(), 1923);

Filter shrinking:

use scalable_cuckoo_filter::ScalableCuckooFilter;

let mut filter = ScalableCuckooFilter::new(1000, 0.001);
for i in 0..100 {
    filter.insert(&i);
}
assert_eq!(filter.capacity(), 1024);
assert_eq!(filter.bits(), 14336);

filter.shrink_to_fit();
for i in 0..100 {
    assert!(filter.contains(&i));
}
assert_eq!(filter.capacity(), 128);
assert_eq!(filter.bits(), 1792);

References

Dependencies

~445–620KB
~12K SLoC