Cuckoo filter
Uji keanggotaan seperti Bloom filter, dengan satu tambahan: item bisa dikeluarkan lagi. Sebagai gantinya, jaminan tanpa-false-negative jadi bersyarat, dan syaratnya layak dibaca.
Di mana ini benar-benar dipakai
Di mana pun Bloom filter cocok tetapi isi set-nya terus berubah — direktori cache, daftar sertifikat yang dicabut, potongan yang sudah dimiliki sebuah peer. Bloom filter tidak bisa lupa: apa pun yang dikeluarkan dari set sebenarnya tetap tertinggal di filter selamanya, jadi satu-satunya cara menghapus adalah membangun ulang seluruh filter. Yang ini menghapus di tempat.
Jaminannya
Lookup tidak pernah melewatkan item yang dipegang filter — asalkan tidak ada insert yang gagal dan tidak ada yang dihapus tanpa pernah dimasukkan. Jaminan Bloom tanpa syarat dan Bloom tidak bisa menghapus. Itulah pertukarannya.
Cara kerjanya
Sebuah fingerprint pendek dari tiap item, disimpan di salah satu dari dua bucket kandidat. Bucket kedua adalah i₁ ⊕ h(fingerprint), sehingga rumah lain dari entry yang tergeser bisa dihitung hanya dari fingerprint-nya — itulah yang memungkinkan tabel memindahkan entry yang itemnya sudah tidak ia simpan.
Paling banyak 2b salinan satu item yang muat — item identik menghasilkan fingerprint dan bucket identik. Karena itu stream yang miring membuat filter ini menolak insert padahal ia hampir kosong. Bloom sama sekali tidak terpengaruh pengulangan.
Fan, Andersen, Kaminsky & Mitzenmacher, CoNEXT 2014