A few types of filters support deletion (e.g. counting bloom filters and cuckoo filters). To my knowledge all of them require prior knowledge that an entry was successfully inserted. That is, if you guess at deleting an entry and are successful, then you'll ruin the filter by creating a false-negative case.

As for collisions, only a limited number of colliding entries can be inserted into a cuckoo - after which a subsequent insertion will knowingly fail. So say Alice and Bob hash out to the same values, and you've inserted 2 Alices and 1 Bob. When you delete one Alice, it doesn't matter which entry is removed - two entries still remain that hash to Alice and Bob.

Perhaps the nuance you mention is that the alternate bucket index for an entry is calculated only from the fingerprint, not from the entry data. This has the effect that even when multiple entries share fingerprints, any one can be removed. (Again, _only_ if the system requesting the delete positively knows that the entry was previously successfully inserted.) The other colliding entry will still be found on query and will generate a "maybe" response.

I had the same thoughts and checked the paper[0]. They address it under 3.3 Delete

>Deletion does not have to clean the entry after deleting an item. It also avoids the “false deletion”....

[0]https://www.cs.cmu.edu/~dga/papers/cuckoo-conext2014.pdf

Having quickly read the paper, the deletion guarantees seem slightly weak.

An item's position in the table is derived from two things: a fingerprint (a constant-sized hash) and second hash (ranging over the table). Nothing prevents two or more items from colliding on both hashes and therefore being indistinguishable from each other.

If the number of items in such a collision exceeds twice the fixed bucket size then deletion may result in false negatives.

In most practical applications there will be no useful way to bound the number of collisions. The paper shows results with bucket sizes of 4 and 8, but I don't know what the real-world probabilities of breaching these limits would be.

Hashing items that present themselves as equivalent is a very old problem with plenty of literature. It can be a pain in the butt to fix retroactively but it does tend to get fixed when there are big enough performance or correctness concerns in play.

The idea is that two elements x and y despite having the same fingerprint, will be stored into two different buckets. So you can have several time the same fingerprint in a Cuckoo filter, which you can't in a Bloom Filter.

When you want to remove x, you remove one of the two fingerprints, it does not matter which since they're the same. Next when you query y you will be sure to still have a positive answer.

Note that however the deletion won't necessarily make the filter forget about x. It will just clear some place in the structure.