2

I am currently working on a Bloom filter implementation. I was wondering how can I test such a data structure since a Bloom filter is probabilistic in nature, I guess . I want to unit test and also test for false positives. in particular how can I unit test the filter methods (add/contains) and how can I verify that false positives are below a certain percent?

3
1

False positives are possible in a bloom filter. So having one isn't a failure. You can test for many other things but this is asking the impossible.

You could set a threshold that you expect the false positives to be under but that requires enough trials that the test stops being fast.

3
  • ...or a deterministic unit test. It's still possible for the test to fail, even with a threshold set. Jun 1 '17 at 2:26
  • @RobertHarvey Well, kinda. You could use the same data in the test every time trying to make it deterministic. But then the implementation becomes the source of random making it fail or pass based on arbitrary implementation choices that aren't actually wrong, just unlucky. Jun 1 '17 at 2:38
  • 1
    @CandiedOrange I'd try hard to separate testing the Bloom filter (which I think is doable if you can mock out the hash functions) from testing the behaviour of the hash functions themselves, which I agree is a hard problem. Jun 1 '17 at 6:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.