A Bloom filter of 16 bits and 3 hash functions, all bits 0. Insert cat, dog, owl, cow, then ask about cat, ant, bee, eel. Each word maps to 3 bit positions. Inserting sets them, querying reads them. The filter never stores the words themselves.
Bloom filter with 16 bits and 3 hashes.
Insert "cat": its three hashes are 6, 4, 0, so those bits become 1. 3 of 16 bits are now set.
Insert cat: bits 6, 4, 0.
Insert "dog": its three hashes are 12, 6, 2, so those bits become 1, 1 of them already set by an earlier word. 5 of 16 bits are now set.
Insert dog: bits 12, 6, 2.
Insert "owl": its three hashes are 4, 6, 10, so those bits become 1, 2 of them already set by an earlier word. 6 of 16 bits are now set.
Insert owl: bits 4, 6, 10.
Insert "cow": its three hashes are 11, 13, 1, so those bits become 1. 9 of 16 bits are now set.
Insert cow: bits 11, 13, 1.
Query "cat": hashes 6, 4, 0. All three bits are 1, so the answer is "probably", and here it happens to be right: "cat" was inserted.
cat: probably present.
Query "ant": hashes 7, 3, 3. Bit 7 is 0, and inserting "ant" would have set it, so the word was never inserted. Definitely not.
ant: definitely absent.
Query "bee": hashes 2, 0, 4. All three bits are 1, so the filter says "probably", but "bee" was never inserted: its bits were set by other words. A false positive, the price of using 16 bits instead of storing the words.
bee: probably present.
Query "eel": hashes 12, 2, 14. Bit 14 is 0, and inserting "eel" would have set it, so the word was never inserted. Definitely not.
eel: definitely absent.
4 words set 9 of 16 bits. Of 4 queries, 2 came back "probably", 1 of them wrongly, and the rest "definitely not", which is never wrong. The false positive rate falls with more bits per key and rises as the filter fills. With about 10 bits per key and 7 hashes it is around 1 percent, at a fraction of the memory a hash set of the keys would need.
9 bits set. 1 false positives.