You want to check if an element is probably in a dataset. You want speed, and the possibility of a false positive doesn’t scare you that much. Say you want to

You want to check if an element is probably in a dataset. You want speed, and the possibility of a false positive doesn’t scare you that much. Say you want to lookup if a username is in a database. That could take a while if you have a really large db of usernames, but you want to tell a user quickly if a name is taken. So what you can do is make a bloom filter, which is basically just an array of bits of n length. Let’s say 10 for our example. Then gather some hash functions (h1, h2, and h3). When someone inputs a username, you run it through the hash functions, and modulo by the number of bits, and get an integer result. So: h1(“rattlesnakedave”) % 10 = 3 h2(“rattlesnakedave”) % 10 = 7 h3(“rattlesnakedave”) % 10 = 2 Then you check the bits at position 3,2, and 7 in the array. If they any of the bits are set to 0, we haven’t seen the username before. If they’re all set to 1, we have possibly seen the username before. Let’s say they’re all set to 0, so we probably haven’t seen it. We can present the message that the username is available, and allow registration. During registration, we can do a slower more expensive verification that the username isn’t actually in the dataset. Now that the username is in the dataset, we can flip the bits on our bloom filter at position 3,2, and 7 to 1. So the next time we lookup that username we can tell quickly that it’s probably taken. There is no way to delete from the bloom filter. The more values you store relative to its size, the more false positives you get. Hopefully that makes sense, and is correct.