41–50 of 50 posts
I've just thought about how you could also have a "Bloom Map", basically as a HashSet is to Bloom Filter, a HashMap would be to a Bloom Map. It would be able to answer lookups with either "Definitely not present" or "Might map to value XYZ".
What's the intuition behind the name?
Bloom filters explained in a single HN comment: They are an efficient implementation of a Set that contains hashes of the elements. bloomfilter.add("foo") will internally add hash("foo") to the Set bloomfilter.has("foo") checks if the Set contains hash("foo") False positives arise due to different elements hashing to the same hash. If "foo" and "bar" hash to the same value, bloomfilter.has("bar") would return true. N…
Super useful and succinct!
This explanation could apply to a few hash-set style implimentations but I think it misses what made the bloom filter so beautiful and elegant when I'd discovered it. It's a specific data structure with it's own memory/performance/tuning profiles!
Bloom filters explained in a single HN comment: They are an efficient implementation of a Set that contains hashes of the elements. bloomfilter.add("foo") will internally add hash("foo") to the Set bloomfilter.has("foo") checks if the Set contains hash("foo") False positives arise due to different elements hashing to the same hash. If "foo" and "bar" hash to the same value, bloomfilter.has("bar") would return true. N…
Bloom filters explained in a single HN comment: They are an efficient implementation of a Set that contains hashes of the elements. bloomfilter.add("foo") will internally add hash("foo") to the Set bloomfilter.has("foo") checks if the Set contains hash("foo") False positives arise due to different elements hashing to the same hash. If "foo" and "bar" hash to the same value, bloomfilter.has("bar") would return true. N…
I don't think that's quite right though. A bloom filter does not keep a list of hashes. If it did it'd grow with every item added to the set, and it doesn't. A bloom filter adds a new hash by bitwise-or-ing it with the currently stored value. Checking if a hash is present in the bloom filter is as simple as checking that all the 1 bits in the bash are 1 bits in the stored value in the bloom filter. This makes sure th…
thanks for the post, it inspired this naive code: class BloomFilter: def __init__(self, size): self.f = [0] * size def contains(self, s): h1, h2, h3 = self.hashes(s) if self.f[h1] * self.f[h2] * self.f[h3] == 1: return 'Value might be in the set.' else: return 'Value is definitely not in the set.' def hashes(self, s): h1 = hash(s) % len(self.f) h2 = hash(s + 'salt') % len(self.f) h3 = hash(s + 'more salt') % len(self…
This looks fantastic! I also implemented one from scratch[0], and I was doing something very similar at first. Then I found the Python hash() function returns different outputs for the same input when you restart the interpreter. I really like your implementation, it's functional and easy to understand! [0] https://ricardoanderegg.com/posts/understanding-bloom-filter...
> found the Python hash() function returns different outputs for the same input when you restart the interpreter
I wasn't aware of this >>
Earlier quoted context omitted.
I don't think that's quite right though. A bloom filter does not keep a list of hashes. If it did it'd grow with every item added to the set, and it doesn't. A bloom filter adds a new hash by bitwise-or-ing it with the currently stored value. Checking if a hash is present in the bloom filter is as simple as checking that all the 1 bits in the bash are 1 bits in the stored value in the bloom filter. This makes sure th…
So it means with a dataset big enough, your bloom filter is virtualy all 1s, and will return true for every values you want to check regardless if it is actually in there ? Is there a threshold you can monitor to avoid this situation ?
I guess there are other techniques to dynamically grow the filter when you need it.
Bloom filters explained in a single HN comment: They are an efficient implementation of a Set that contains hashes of the elements. bloomfilter.add("foo") will internally add hash("foo") to the Set bloomfilter.has("foo") checks if the Set contains hash("foo") False positives arise due to different elements hashing to the same hash. If "foo" and "bar" hash to the same value, bloomfilter.has("bar") would return true. N…
I don't think that's quite right though. A bloom filter does not keep a list of hashes. If it did it'd grow with every item added to the set, and it doesn't. A bloom filter adds a new hash by bitwise-or-ing it with the currently stored value. Checking if a hash is present in the bloom filter is as simple as checking that all the 1 bits in the bash are 1 bits in the stored value in the bloom filter. This makes sure th…
"unrelated hashes turning on enough bits for a match" is the case of hash collisions or I am misunderstanding that part.