#cuckoo-filter #bloom-filter #scalable #scale #size #automatically

scalable_cuckoo_filter

A variant of Cuckoo Filter whose size automatically scales as necessary

8 releases

new 0.2.4 Mar 11, 2024
0.2.3 Oct 31, 2023
0.2.2 Jan 22, 2023
0.2.0 Apr 15, 2021
0.1.1 Jan 20, 2018

#434 in Data structures

Download history 35/week @ 2023-11-27 12/week @ 2023-12-04 47/week @ 2023-12-11 236/week @ 2023-12-18 228/week @ 2023-12-25 75/week @ 2024-01-08 43/week @ 2024-01-15 167/week @ 2024-01-22 50/week @ 2024-01-29 65/week @ 2024-02-05 85/week @ 2024-02-12 57/week @ 2024-02-19 120/week @ 2024-02-26 143/week @ 2024-03-04

405 downloads per month
Used in seadawg

MIT license

35KB
772 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–560KB
~11K SLoC