Implementing a Cuckoo Filter in Go

In a recent post we have looked at a bloom filter implementation, which is a commonly used probabilistic data structure to provide fast membership tests. A quite similar data structure is the Cuckoo Filter.

A Cuckoo Filter, as opposed to a bloom filter gives us the possibility to not only store items but also delete them from the filter without sacrificing the performance for set membership tests that we get from a traditional Bloom Filter. In addition, a cuckoo filter that stores many items and targets a low false-positive rate will have a lower space overhead than space-optimized bloom filters.

Why would you want to choose a cuckoo filter over a bloom filter?

  • They support adding / removing items dynamically
  • Higher lookup performance, even when 95% space is utilized
  • Easier to implement than alternatives
  • Less space used than bloom filters in *most* cases

Similarly as with the bloom filter, you can not retrieve what data was inserted. A cuckoo filter will only store a hash (fingerprint) of the item that is being inserted rather than the item itself.

In case you don’t want to walk through the entire implementation step by step, the full code can be found on Github.

Setting up the Cuckoo Filter

Hence we’ll need to store the bucket but also some metadata for the filter and for the buckets.

// Cuckoo filter based on
type Cuckoo struct {
buckets []bucket
m uint // buckets
b uint // entries per bucket
f uint // fingerprint length
n uint // filter capacity (rename cap?)

In addition, we’ll also create a type alias for buckets and fingerprints. Because fingerprints are generated with a hash function, we’ll import crypto/sha1 as well but you could pick another hash function.

type bucket []fingerprint
type fingerprint []byte
var hasher = sha1.New()

We can tweak our cuckoo filter to change the rate of false-positives and space-time efficiency. This depends on what a user wants from the filter, hence we can use a “constructor” that accepts a requested capacity and a required false-positive rate.

// n = len(items), fp = false positive rate
func NewCuckoo(n uint, fp float64) *Cuckoo {
b := uint(4)
f := fingerprintLength(b, fp)
m := nextPower(n / f * 8)
buckets := make([]bucket, m)
for i := uint(0); i < m; i++ {
buckets[i] = make(bucket, b)
return &Cuckoo{
buckets: buckets,
m: m,
b: b,
f: f,
n: n,

If you’re wondering where the fingerprintLength and nextPower function come from, this paper sheds some light on that. I’d rather focus on the insertion / lookup and deletion algorithms in the remainder of this blog post (they’re in pseudo-code in the paper as well) 😃

Inserting values

We’ll try to enter our fingerprint in either of the two buckets as long as the bucket does not overflow. If the bucket is full, we’ll kick an item out the bucket and move it to another one.

The hash function we are using to create our hashes for the first and second bucket is based on the Sha1 hash:

func (c *Cuckoo) hashes(data string) (uint, uint, fingerprint) {
h := hash([]byte(data))
f := h[0:c.f]
i1 := uint(binary.BigEndian.Uint32(h))
i2 := i1 ^ uint(binary.BigEndian.Uint32(hash(f)))
return i1, i2, fingerprint(f)

func hash(data []byte) []byte {
hash := hasher.Sum(nil)
return hash

A high level overview of the insertion algorithm using this hash would be:

// try to store in bucket 1
// if success-> done
// if not -> try to store in bucket 2
// if success -> done
// if not ->
// while retry < retryLimit
// pick random entry (r) from bucket 1
// move entry (r) to alternate location
// try store in new bucket
// if success -> done

More visually:

Image for post
Image for post

Translated to code, trying to store the in the first or second bucket this would look like:

i1, i2, f := c.hashes(input)
// first try bucket one
b1 := c.buckets[i1%c.m]
if i, err := b1.nextIndex(); err == nil {
b1[i] = f

b2 := c.buckets[i2%c.m]
if i, err := b2.nextIndex(); err == nil {
b2[i] = f

In the best case scenario, it ends here. But in case both our buckets were full already, we’ll start kicking things out of bucket 1 and move the item that got kicked out to its alternate position.

// start relocating items
i := i1
for r := 0; r < retries; r++ {
index := i % c.m
entryIndex := rand.Intn(int(c.b))
// swap
f, c.buckets[index][entryIndex] = c.buckets[index][entryIndex], f
i = i ^ uint(binary.BigEndian.Uint32(hash(f)))
b := c.buckets[i%c.m]
if idx, err := b.nextIndex(); err == nil {
b[idx] = f
panic("cuckoo filter full")

I panic if our cuckoo filter is full, but… this should probably be handled gracefully 😅

Membership test

// lookup needle in the cuckoo nest :)
func (c *Cuckoo) lookup(needle string) bool {
i1, i2, f := c.hashes(needle)
return c.buckets[i1%c.m].contains(f) || c.buckets[i2%c.m].contains(f)
// returns the index and successful lookup
func (b bucket) contains(f fingerprint) (int, bool) {
for i, x := range b {
if bytes.Equal(x, f) {
return i, true
return -1, false


We can create a delete function by stitching together the functions we’ve already written:

// delete the fingerprint from the cuckoo filter
func (c *Cuckoo) delete(needle string) {
i1, i2, f := c.hashes(needle)
// try to remove from f1
b1 := c.buckets[i1%c.m]
if ind, ok := b1.contains(f); ok {
b1[ind] = nil

b2 := c.buckets[i2%c.m]
if ind, ok := b2.contains(f); ok {
b2[ind] = nil


The repository with all code can be found on github:

If you liked this post and ❤️ Go as well, consider:

  • Following me here, on Medium
  • Or twitter Twitter
  • Or check out to find cool Go jobs around the world. 😄

Written by

Gopher | | | Tech lead

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store