A high-performance, generic Cuckoo filter implementation in Go. Cuckoo filters are space-efficient probabilistic data structures used to test whether an element is a member of a set, with the added benefit of supporting deletions unlike traditional Bloom filters.

• ✅ Generic Implementation: Works with any hashable type (string, int, []byte, etc.)
• ✅ Deletion Support: Unlike Bloom filters, supports item removal
• ✅ High Performance: O(1) expected time for all operations
• ✅ Space Efficient: Better space utilization than Bloom filters for low false positive rates
• ✅ Bounded False Positives: Guaranteed maximum false positive rate
• ✅ Cache Friendly: Bucket-based design for better memory locality

go get github.com/jamra/cuckoo

package main

import (
    "fmt"
    "github.com/jamra/cuckoo"
)

func main() {
    // Create a new Cuckoo filter for strings with capacity of 1000
    cf := cuckoo.New[string](1000)
    
    // Insert items
    cf.Insert("apple")
    cf.Insert("banana")
    cf.Insert("cherry")
    
    // Lookup items
    fmt.Println(cf.Lookup("apple"))   // true
    fmt.Println(cf.Lookup("banana"))  // true
    fmt.Println(cf.Lookup("grape"))   // false (probably)
    
    // Delete items (unique feature compared to Bloom filters!)
    cf.Delete("apple")
    fmt.Println(cf.Lookup("apple"))   // false
    
    // Get statistics
    stats := cf.GetStats()
    fmt.Printf("Size: %d, Load Factor: %.2f%%\n", 
        stats.Size, stats.LoadFactor*100)
}

// Create a filter for strings
cf := cuckoo.New[string](1000)

// Create a filter for integers
cfInt := cuckoo.New[int](1000)

// Create a filter for byte slices
cfBytes := cuckoo.New[[]byte](1000)

// Insert an item
success := cf.Insert("item")

// Check if item exists (may have false positives)
exists := cf.Lookup("item")

// Delete an item
deleted := cf.Delete("item")

// Get current size
size := cf.Size()

// Get load factor
loadFactor := cf.LoadFactor()

stats := cf.GetStats()
fmt.Printf("Size: %d\n", stats.Size)
fmt.Printf("Capacity: %d\n", stats.Capacity)
fmt.Printf("Load Factor: %.2f\n", stats.LoadFactor)
fmt.Printf("Memory Usage: %d bytes\n", stats.MemoryBytes)

The filter supports any type that satisfies the Hashable constraint:

• string
• int, int32, int64
• uint, uint32, uint64
• []byte

Cuckoo filters use cuckoo hashing with two hash functions. Each item can be stored in one of two possible buckets:

1. Primary bucket: Determined by hash of the item
2. Alternative bucket: Determined by XOR of primary bucket and hash of fingerprint

Instead of storing full items, Cuckoo filters store compact fingerprints (16-bit in this implementation):

• Reduces memory usage
• Enables efficient comparisons
• Allows reconstruction of alternative bucket index

When both possible buckets are full:

1. Randomly select one of the two buckets
2. Randomly evict an existing fingerprint
3. Insert the new fingerprint
4. Try to relocate the evicted fingerprint to its alternative bucket
5. Repeat until successful or maximum kicks reached

• Insert: O(1) expected, O(log n) worst case
• Lookup: O(1)
• Delete: O(1)

• Memory usage: ~2-3 bytes per item (depending on load factor)
• Load factor: Recommended 50-90% for optimal performance

*May fail when filter approaches capacity

• ✅ Caching Systems: When you need to evict items from cache
• ✅ Databases: Negative query optimization with deletion support
• ✅ Network Systems: Duplicate detection with item expiration
• ✅ Security: Blocklist/allowlist management with updates
• ✅ Analytics: Unique visitor tracking with GDPR deletion requirements

Run the test suite:

go test -v

Run benchmarks:

go test -bench=. -benchmem

Contributions are welcome! Please feel free to submit a Pull Request.

This project is licensed under the MIT License - see the LICENSE file for details.

• Cuckoo Filter: Practically Better Than Bloom - Original paper
• Cuckoo Hashing - Wikipedia article
• Go Generics - Official Go generics tutorial