the cuckoo filter, a practical data structure that provides four major advantages.
1. It supports adding and removing items dynamically;
2. It provides higher lookup performance than traditional Bloom filters, even when close to full (e.g., 95% space utilized);
3. It is easier to implement than alternatives such as the quotient filter; and
4. It uses less space than Bloom filters in many practical applications, if the target false positive rate ε is less than 3%.

Algorithm 1: Insert(x)
    f = fingerprint(x);
    i1 = hash(x);
    i2 = i1 ⊕ hash(f);
    if bucket[i1] or bucket[i2] has an empty entry then
        add f to that bucket; 
        return Done;

    // must relocate existing items;
    i = randomly pick i1 or i2;
    for n = 0; n < MaxNumKicks; n++ do
        randomly select an entry e from bucket[i]; 
        swap f and the fingerprint stored in entry e; 
        i = i ⊕ hash( f );
        if bucket[i] has an empty entry then
            add f to bucket[i]; 
            return Done;

    // Hashtable is considered full; 
    return Failure;

Algorithm 2: Lookup(x)
    f = fingerprint(x);
    i1 = hash(x);
    i2 = i1 ⊕ hash(f);
    if bucket[i1] or bucket[i2] has f then
        remove a copy of f from this bucket; 
        return True;
    return False;

Algorithm 3: Delete(x)
    f = fingerprint(x);
    i1 = hash(x);
    i2 = i1 ⊕ hash(f);
    if bucket[i1] or bucket[i2] has f then
        remove a copy of f from this bucket; 
        return True;
    return False;

Note that, to delete an item x safely, it must have been previously inserted. Otherwise, deleting a non-inserted item might unintentionally remove a real, different item that happens to share the same fingerprint. This requirement also holds true for all other deletion-supporting filters.

ε 	target false positive rate f fingerprint length in bits
α 	load factor(0≤α≤1)
b 	number of entries per bucket
m 	number of buckets
n 	number of items
C 	average bits per item
f   bits number of footprint

We conclude that 4^bf must be Ω(n) to avoid a non-trivial probability of failure, as otherwise this expectation is Ω(1). Therefore, the fingerprint size must be f = Ω(log n/b) bits.
 This result seems somewhat unfortunate, as the number of bits required for the fingerprint is Ω(log n); recall that Bloom filters use a constant (approximately ln(1/ε) bits) per item. We might therefore have concerns about the scalability of this approach.

 For a Bloom filter, achieving ε = 1% requires roughly 10 bits per item, regardless of whether one thousand, one million, or billion items are stored. 
 ...
 We find that, for practical purposes, it can be treated as a reasonable-sized constant for implementation. Figure 2 shows that for cuckoo filters targeting a few billion items, 6-bit fingerprints are sufficient to ensure very high utilization of the hash table.

where α increases with b. For example, when b = 4 so 1/α ≈ 1.05, Eq. (7) shows cuckoo filters are asymptotically better (by a constant factor) than Bloom filters, which require 1.44 log2 (1/ε) bits or more for each item.

the space-optimal bucket size depends on the target false positive rate ε: when ε > 0.002, having two entries per bucket yields slightly better results than using four entries per bucket; when ε decreases to 0.00001 < ε ≤ 0.002, four entries per bucket minimizes space.
 In summary, we choose (2, 4)-cuckoo filter (i.e., each item has two candidate buckets and each bucket has up to four fingerprints) as the default configuration,...