A standard technique from the hashing literature is to use two hash functions h1(x) and h2(x) to simulate additional hash functions of the form gi(x) = h1(x) + ih2(x). We demonstrate that this technique can be usefully applied to Bloom filters and related data structures. Specifically, only two hash functions are necessary to effectively implement a Bloom filter without any loss in the asymptotic false positive probability. This leads to less computation and potentially less need for randomness in practice.
The central idea in this paper has become a standard trick used in many implementations, and should be known by any bloom filter implementer. Mitzenmacher’s papers are a wonderful combination of theory and practice. (His other famous bloom filter trick is “compressed bloom filters”, which is useful whenever a bloom filter must be sent over a bandwidth-limited medium.)