Let’s build a Bloom filter. Part 1 - A Space-Efficient Hash Set

from blog Lukas Valatka, | ↗ original
I have always been intrigued by Bloom filters. They are very similar to hash sets but somehow consume much less memory. Sometimes, they can yield false positives, creating a peculiar tradeoff.