#cuckoo-filter #bloom-filter

scalable_cuckoo_filter

A variant of Cuckoo Filter whose size automatically scales as necessary

6 releases

0.2.2 Jan 22, 2023
0.2.1 Jan 18, 2023
0.2.0 Apr 15, 2021
0.1.2 Jun 5, 2018
0.1.1 Jan 20, 2018

#379 in Data structures

Download history 9/week @ 2022-11-28 11/week @ 2022-12-05 15/week @ 2022-12-12 10/week @ 2022-12-19 9/week @ 2022-12-26 3/week @ 2023-01-02 12/week @ 2023-01-09 50/week @ 2023-01-16 19/week @ 2023-01-23 33/week @ 2023-01-30 50/week @ 2023-02-06 50/week @ 2023-02-13 45/week @ 2023-02-20 39/week @ 2023-02-27 124/week @ 2023-03-06 310/week @ 2023-03-13

525 downloads per month
Used in seadawg

MIT license

32KB
733 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

~310–590KB
~12K SLoC