3 ms·
I'd implement it exactly like bloom filter but instead bits I'd use 0,1,2 0 means never touched. 1 means I've seen it, 2 means I've seen it more than once. Tru
by scotty79 14y ago
I'd implement it exactly like bloom filter but instead bits I'd use 0,1,2
0 means never touched. 1 means I've seen it, 2 means I've seen it more than once.
True positive is when all places for given entry contain 1.
Adding is incrementing all places (if they have value less than 2).
Before putting new value in check if it's not already here. If it is don't add.
- bkirwi 14y agoThis doesn't work. If an object hashes to places abc, and each of a, b, and c were already incremented independantly by previous insertions, you would get a false positive.
- eridius 14y agoThat's not going to work at all. If I have an object A that hashes to bits 1, 5, 17, 24; an object B that hashes to bits 1, 5, 13, 15; and an object C that hashes to bits 2, 9, 17, 24; and I add objects B and C, then the filter will incorrectly think A has already been seen.
- scotty79 14y agoYou are right. I haven't properly thought that through.