Chapter 13

These are the solutions to the .

1. You can store all usernames inside an in-memory Bloom filter. Then, each time a user asks if a particular username is available, your app would check for its existence inside the Bloom filter. Bloom filter lookups have the potential to be a lot faster than database lookups.

   Because a Bloom filter never produces a false negative, it can be trusted to say if a given username is available. (That is, it doesn’t exist within the Bloom filter.) Accordingly, we never have to worry that we’ll inadvertently allow two users to end up with the same username.

   At the same time, a Bloom filter can produce false positives, which means that it’s possible that the Bloom filter may tell us that a username is unavailable even though it’s not taken. However, this may not be a big deal, since the user can find some other username (that’s equally unclever) to use.

2. Luckily for HumbleBrag, you put the kibosh on the engineering team’s plan. Since a Bloom filter can produce a false positive, it’s possible that the Bloom filter will validate the entered password even if it’s not correct! If ten strings hash into the same set of bits in the Bloom filter, any one of those strings would be accepted as the correct password, even though only one of those passwords is the right one.

3. With this code, we can get the info we need:

   ​	​import​ ​sys​
   ​	​import​ ​bloom_filter​
   ​
   ​	bf = bloom_filter.BloomFilter(1000, 0.03)
   ​	​print​(bf.m) ​# number of bits​
   ​	​print​(bf.k) ​# number of hash functions​
   ​	​print​(sys.getsizeof(bf.bv.integers)) ​# bit vector's number of bytes​

   When I run this, I find that M (the number of bits) is 7,298, and that K (the number of hash functions) is 5.

   Now, I’d expect that if the Bloom filter takes up 7,298 bits, then it takes up around 912 bytes since 7298 // 8 = 912. However, when I run sys.getsizeof() on the actual underlying array of the bit vector (which, in turn, underlies the Bloom filter), I find that it takes up 1,888 bytes. This, again, is because Python crams some extra info into its arrays and integers. So, in reality, the size of the Bloom filter is somewhat larger than the strict computation of M.

Thank you!

We hope you enjoyed this book and that you’re already thinking about what you want to learn next. To help make that decision easier, we’re offering you this gift.

Head on over to right now, and use the coupon code BUYANOTHER2025 to save 30% on your next ebook. Offer is void where prohibited or restricted. This offer does not apply to any edition of The Pragmatic Programmer ebook.

And if you’d like to share your own expertise with the world, why not propose a writing idea to us? After all, many of our best authors started off as our readers, just like you. With up to a 50% royalty, world-class editorial services, and a name you trust, there’s nothing to lose. Visit today to learn more and to get started.

Thank you for your continued support. We hope to hear from you again soon!

The Pragmatic Bookshelf