#bloom-filter #cuckoo #cuckoo-filter #automatic #scalable #size

scalable_cuckoo_filter

A variant of Cuckoo Filter whose size automatically scales as necessary

11 releases

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

#237 in Data structures

Download history 37/week @ 2024-07-20 30/week @ 2024-07-27 261/week @ 2024-08-03 284/week @ 2024-08-10 146/week @ 2024-08-17 196/week @ 2024-08-24 223/week @ 2024-08-31 149/week @ 2024-09-07 126/week @ 2024-09-14 208/week @ 2024-09-21 243/week @ 2024-09-28 302/week @ 2024-10-05 156/week @ 2024-10-12 595/week @ 2024-10-19 185/week @ 2024-10-26 236/week @ 2024-11-02

1,205 downloads per month
Used in 2 crates

MIT license

37KB
793 lines

scalable_cuckoo_filter

scalable_cuckoo_filter Documentation Actions Status Coverage 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

~295–540KB
~10K SLoC