In competitive programming there is a trick for storing a set of strings(or objects really) to reduce memory - you only keep the hashes of the strings in a hash-table (usually as 32 or 64 bit integers). This data structure has the same properties as a Bloom filter. You never have false negatives but you can have false positives. Since adding and removal are constant operation I was wondering what advantages do Bloom filters have over this method and which was is more memory efficient. If there is some formal analysis of both methods Id like to see it :)

  • $\begingroup$ Are you sure that Bloom filter supports key removal? With overhead maybe, but it is not built-in operation. Maybe you could state your goal? There are other techniques, for example trie-based, have you considered them? $\endgroup$ – Evil Oct 11 '17 at 23:28

Your Answer

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

Browse other questions tagged or ask your own question.