1. It has O(1) lookups (it has to probe at most 2 constant-size buckets) and O(1) amortised insertions (the probability of needing more than k swaps to find an empty slot decreases exponentially with k).
2. It's geared for low false positives, 3% or lower.
3. It does have false positive on lookups: signatures are lossy.
4. It has comparable space requirements to bloom filters for the same error rate and set (not universe) cardinality.
def insert(x):
for hash in hashes:
bloom_filter[hash(x)] = true
The downside is that your false positive rate will increase as you insert elements. But, on the other hand, you get the guarantee of no false negatives.
This cuckoo filter has no false negatives or false positives, but their Insert() function clearly can hit a case where it returns Failure.
Bloom filters effectively represent the infinite set when it's all ones. You can always add more, and everything will return as probably in there already.
1. It doesn't appear to have O(1) lookup or O(1) insertion.
2. It appears that this filter can become "full", which is very different from a bloom filter.
3. It appears that this doesn't have false positives on lookup either.
4. I'm not very confident that this has a constant space requirement either.
This seems like something that I wouldn't compare to a bloom filter.