Suppose a contacts application can check a server, but wants to avoid a network request for every unknown address. Keeping every contact in a local hash set may use too much memory. A Bloom filter offers a smaller first check: it can rule out an address locally, while a possible match still needs server confirmation. section 4.6.1 section 4.4.5
A Bloom filter is a probabilistic set-membership structure. It stores no keys or associated values. Its answer is either “definitely not added” or “possibly added”: false positives are possible, but the basic filter has no false negatives and cannot delete keys. section 4.4.5 section 4.8.1
Build the basic filter from a zero-filled array of m bits and k deterministic hash functions:
- Insert a key by hashing it to k bit positions and setting those bits to 1. Different keys may share positions. section 4.5
- Look up a key by hashing it again. If any selected bit is 0, return false; if all are 1, return true as a possible match. section 4.6.6
- Pack bits into an integer array when memory matters: divide a bit index by the bits per integer to find its array element, then use the remainder as its bit offset. section 4.6.2
Figure 4.3 An example of a Bloom filter. (A) Initially the filter is an array of zeroes. (B) To store an item Xi, it is hashed k times (in the example, k=3), with each hash yielding the index of a bit; then these k bits are all set to 1. Notice how the two triplets of indices generated by X1 and X2 partially overlap (they both point to the sixth element). For a more detailed example of how insertion works, see figure 4.5. (C) Likewise, to check if an element Yi is in the set, it’s hashed k times, obtaining just as many indices; then we read the corresponding bits, and if and only if all of them are set to 1, we return true. In the bottom drawing, element Y1 appears to be in the set (but we can’t exclude that the filter is returning a false positive), while element Y2 can’t be in the set because one of the indices generated from its hashing holds a 0. Check figure 4.4 for further insight into how lookup works.
The diagram shows insertion and lookup with three hash functions, including overlapping positions and the distinction between a definite miss and a possible match. section 4.5
How a false positive happens
In a four-bit filter, suppose inserting 1 sets positions 0 and 2, and inserting 2 sets positions 1 and 2. A never-inserted 3 whose hashes select positions 1 and 0 now appears present. Neither stored key needs to be 3; their set bits suffice. section 4.8.2
For server-backed contacts, load existing contacts into the filter at startup. A negative lookup avoids the server; a positive lookup goes to the server for confirmation. When adding a contact, store it on the server successfully before updating the filter, so a failed remote write does not create a misleading local state. section 4.6.1
Choose the bit count m and hash count k for the expected number of inserted keys n and an acceptable false-positive rate. More bits reduce collisions but consume memory; changing k also changes the error rate and hashing work. Under the stated independent-hash assumptions, an approximate false-positive probability is (1 − e^(−kn/m))^k. Exceeding the planned capacity does not prevent insertion, but the original accuracy target is no longer guaranteed. section 4.10 section 4.6.5
Initialization takes O(m + k) time to clear the bits and prepare the hashes. Insertions and lookups inspect k positions, in addition to the cost of hashing the input; constant-time claims therefore assume constant-length keys. Use a Bloom filter when cheap, certain rejections are valuable and occasional extra checks are acceptable—not when a positive answer must stand alone. section 4.9.2 section 4.9.1
