repository·master·Indexed 22 days ago
https://github.com/seiflotfy/cuckoofilterA space-efficient Go implementation of a Cuckoo Filter, providing a probabilistic data structure for set-membership queries that supports dynamic item deletion. It includes a standard Filter with fixed 8-bit fingerprints and a ScalableCuckooFilter that automatically grows when load factor thresholds are reached. Key features include InsertUnique, Lookup, Delete, and serialization via Encode and Decode.
A Cuckoo Filter is a space-efficient data structure used for approximated set-membership queries (e.g., "is item X in this set?"). It serves as a replacement for Bloom filters, with the key advantage of supporting item deletion.
Unlike standard Bloom filters, Cuckoo filters are based on cuckoo hashing and store fingerprints of keys. They are highly compact and are particularly effective for applications requiring low false positive rates (typically < 3%).
To use the Cuckoo Filter, initialize it using cuckoo.NewFilter(capacity) where capacity is the expected number of items. You can then perform insertions, lookups, deletions, and count the current number of items.
Key methods:
InsertUnique([]byte): Adds an item to the filter.Lookup([]byte) bool: Returns true if the item is likely in the set.Delete([]byte) bool: Removes an item from the set.Count() uint: Returns the number of items currently in the filter.Reset(): Clears the filter.package main
import "fmt"
import cuckoo "github.com/seiflotfy/cuckoofilter"
func main() {
cf := cuckoo.NewFilter(1000)
cf.InsertUnique([]byte("geeky ogre"))
// Lookup a string (and it a miss) if it exists in the cuckoofilter
cf.Lookup([]byte("hello"))
count := cf.Count()
fmt.Println(count) // count == 1
// Delete a string (and it a miss)
cf.Delete([]byte("hello"))
count = cf.Count()
fmt.Println(count) // count == 1
// Delete a string (a hit)
cf.Delete([]byte("geeky ogre"))
count = cf.Count()
fmt.Println(count) // count == 0
cf.Reset() // reset
}This implementation uses specific parameters for its hashing and storage mechanism:
Because the fingerprint size is fixed at 8 bits, the expected false positive rate is approximately r ~= 0.03 (3%).
The ScalableCuckooFilter can be serialized to a byte slice using Encode and reconstructed using DecodeScalableFilter or DecodeWithParam.
Encode(): Returns a []byte containing the serialized representation of all internal filters and the loadFactor using the gob encoding format.DecodeScalableFilter(fBytes []byte): Reconstructs the filter from a byte slice.DecodeWithParam(fBytes []byte, opts ...option): Reconstructs the filter and allows applying additional option functions to the newly created instance.Count() uint method returns the current number of items stored in the filter.The Filter provides two ways to add data (as []byte) to the counter:
Insert(data []byte) bool: Attempts to insert the data. Returns true if successful, or false if the filter is too full (reaches maxCuckooCount displacement attempts).InsertUnique(data []byte) bool: Only inserts the data if it is not already present in the filter (checked via Lookup). Returns true if the data was newly inserted, false if it already existed or insertion failed.To check if an element exists in the filter, use Lookup. It iterates through all internal filters and returns true if the data is found in any of them.
To remove an element, use Delete. It returns true if the element was found and successfully removed from one of the internal filters, otherwise it returns false.
Lookup(data []byte) bool to check if a specific piece of data is likely present in the filter. Because this is a probabilistic data structure, it may return false positives (saying an item is present when it is not), but it will never return false negatives (saying an item is not present when it actually is).Use NewScalableCuckooFilter to create a new instance of a scalable cuckoo filter. You can pass optional configuration functions (option) to customize the loadFactor or the scaleFactor.
By default, the filter uses a DefaultLoadFactor of 0.9 and starts with a DefaultCapacity of 10000. If no scaleFactor is provided, the capacity grows by multiplying the current size by bucketSize * 2 when the load factor threshold is reached.
You can persist or transmit the state of a Filter using byte slices:
Encode() []byte: Returns a byte slice representing the current state of all buckets in the filter.Decode(bytes []byte) (*Filter, error): Reconstructs a Filter instance from a previously generated byte slice.Note that Decode will return an error if the byte slice length is not a multiple of the internal bucketSize or if the slice is empty.
cuckoo package uses a default hasher for computing hashes. You can replace this global default with your own implementation by calling SetDefaultHasher. This is useful if you need to use a specific hashing algorithm for your application's requirements.The Insert method adds a byte slice to the filter. If the current filter reaches its loadFactor threshold or fails to find an empty slot, the filter automatically scales by creating a new, larger filter and appending it to the chain.
InsertUnique is a variant that first performs a Lookup. It returns false if the data is already present, and true if the data was successfully inserted as a new element.