3 ms·
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 constan
by bograt 9y ago
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.
- hinkley 9y agoHashing 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.