Cuckoo Filter

A space-efficient probabilistic data structure for approximate set membership queries in Kotlin. The implementation is based on Cuckoo Filter: Practically Better Than Bloom.

A cuckoo filter is similar to a Bloom filter but supports deletion. It uses a compact hash table with cuckoo hashing to store fingerprints of elements.

Like other probabilistic data structures, cuckoo filters may return false positives but never false negatives. That is:

• Querying for an item that was added will always return true
• Querying for an item that was not added may occasionally return true

• Fast lookup and insertion with amortized O(1) time complexity
• Deletion support unlike traditional Bloom filters
• Space-efficient storage using compact fingerprints
• Stable binary representation suitable for serialization and network transport
• Configurable parameters for fingerprint size, bucket size, and load factor

Add the dependency to your build.gradle.kts:

dependencies {
    implementation("no.entur.abt:abt-cuckoo-filter:<version>")
}

You can find the latest version on Maven Central

import com.google.common.hash.Funnels
import no.entur.abt.cuckoofilter.CuckooFilter

// Create a filter with minimum capacity
val filter = CuckooFilter(Funnels.byteArrayFunnel(), minCapacity = 1000)

// Add items
val item = "example".toByteArray()
filter.add(item) // returns true if successful

// Check membership
if (item in filter) {
    println("Item might be in the filter")
}

// Remove items
filter.remove(item) // returns true if found and removed

• Kotlin 2.2+
• JVM 8
• Google Guava (for hash functions and funnels)

See LICENSE.txt