#bloom-filter #cuckoo #scalable #cuckoo-filter #automatic #scale

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

#264 in Data structures

Download history 83/week @ 2024-02-08 62/week @ 2024-02-15 87/week @ 2024-02-22 104/week @ 2024-02-29 431/week @ 2024-03-07 225/week @ 2024-03-14 215/week @ 2024-03-21 143/week @ 2024-03-28 271/week @ 2024-04-04 74/week @ 2024-04-11 286/week @ 2024-04-18 169/week @ 2024-04-25 187/week @ 2024-05-02 205/week @ 2024-05-09 188/week @ 2024-05-16 108/week @ 2024-05-23

689 downloads per month
Used in seadawg

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

~300–550KB
~11K SLoC