Bloom filter
Have you ever wondered how it happens that when you try to register on a very popular portal, entering a made-up username, you get a response in a split second that this username is already taken and you should try another one? I’ll be honest, I didn’t either, but coincidentally, while reading Data Intensive Applications by Martin Kleppmann, I probably learned this secret. It is the Bloom filter. Or maybe not. Actually, I don’t know if there are companies using Bloom filter to verify usernames of their users, but I think this example is easy to understand, so I will stick with it).