Took me a few reads, but it's actually quite simple.
You want a structure that can tell you something has been seen, but sometimes forgets, but will never incorrectly tell you something has been seen.
Solution: an array. Hash the item to find its index, swap out what's there, and see if it is your item. If so, you know for sure it was previously placed. If not, then it might not have (it may have been forgotten).
let arr = Array of key
let contains_key key =
let index = hash key % arr.length
let prev_key = arr.swap[index, key]
return prev_key = key
The hash algorithm is crucial. Reducing forgetfulness is as simple as making the array longer. And he points out that if you can compress the keys, you can reduce storage size.
@jderick: Specifically, it functions the same as a cache with a random removal policy, assuming a good hash function. So a cache and a Bloom filter are opposites: the first knows when something hasn't been seen, and might know when it has; the second knows when something hasn't been seen, and might know when it hasn't. The only difference between this and a normal cache is that we're dropping the values.
On that subject, you might as well have an LRU valueless cache if locality is going to play a role.
Sure, but this is a rather simple cache. Hash into bucket, LRU per bucket, stores the entire object. Nothing like the magic of a bloom filter that represents an object with 3-5 bits.
Pretty much. There's a reason that there's no wikipedia page for this algorithm (where there is for Bloom Filter, of course) -- it's just a hash table without chaining (i.e. it simply drops collisions).
So combining the two will not give you something that will make up for each of the ones weaknesses and always give a definite answer, but will give one of three answers – definite positive, maybe, and definitive negative.
> So combining the two will not give you something that
will make up for each of the ones weaknesses and always
give a definite answer
True, although the probability of a false answer given that
we combine them can be smaller from the probability of the same false answer in the case when we use each of them separately. This may be important in cases when the aversion
to false answers is extremely high.
You want a structure that can tell you something has been seen, but sometimes forgets, but will never incorrectly tell you something has been seen.
Solution: an array. Hash the item to find its index, swap out what's there, and see if it is your item. If so, you know for sure it was previously placed. If not, then it might not have (it may have been forgotten).
The hash algorithm is crucial. Reducing forgetfulness is as simple as making the array longer. And he points out that if you can compress the keys, you can reduce storage size.