Use Multiple Hash Functions

We can turn our Gloom filter into a Bloom filter by using one deviously clever trick. And that is, we hash each value more than once upon each insertion and lookup. Let me explain.

You learned about hash function families in Chapter 10, . That is, we can create different hash functions that all use the same underlying hashing method and yet produce different hash codes. In that chapter, we created multiple hash functions that all use division hashing, but each hash function uses a different random prime number as part of its hashing calculation.

The main point I’m driving at here is that we can run a single value through a number of different hash functions, and each hash function will compute a different hash code. For example, let’s say we have one hash function called hash1() and another function hash2(). If we use each one to hash the string "apple", we may get something like this:

When a Bloom filter is first initialized, it decides how many hash functions it’ll use, and what those hash functions are. (You’ll see later how those decisions are made.) This is all decided at the Bloom filter’s creation, and from then on, the Bloom filter uses these same hash functions for all of its operations, including lookups and insertions.

Let me demonstrate this with an example. Say that when we set up a Bloom filter, it decides that it will always use the two hash functions hash1() and hash2().

If we want to insert "apple" into our Bloom filter, we’ll run both hash functions and end up setting two bits to 1:

Because hash1("apple") is 4, and hash2("apple") is 6, we set the bits of indexes 4 and 6 as 1 bits.

Now, let’s say that we next insert "cucumber". We might get something like this:

Here, our two hash functions compute the hash codes of 4 and 0. So, the bit at index 0 gets set to 1. We’d also set the bit at index 4 to 1, but it already happens to be 1. But that’s okay—these types of collisions won’t prove to be too much of a problem.

Insertions aren’t the only operation where we use these two hash functions. When we look up an item in the Bloom filter, we also use both hash functions. That is, if we look up "cucumber", we use the two hash functions to create two hash codes corresponding to two bit indexes.

Now, here’s the key: only if both indexes have a 1 bit do we confirm that "cucumber" is present in our Bloom filter. If any of these bits were 0, that proves that "cucumber" is not in our set. If it were in our set, both bits would have been set to 1.

The Multi-Hash Advantage

Here’s the advantage of using multiple hash functions. In the previous section, when we were only using a single hash function, we hit a false positive when trying to look up "cucumber". This is because both "apple" and "cucumber" shared the same hash code of 4. So, if "apple" already flipped the bit at index 4 to 1, it appears that "cucumber" is in the set too, even though it isn’t.

But now that we’re using two hash functions, there’s less of a chance of getting this false positive. Let’s go back to the case where only "apple" is present in our set, and the Bloom filter looks like this:

If we now look up "cucumber", we’re no longer going to get a false positive as shown in the .

Although the bit at index 4 is a 1 bit, the bit at index 0 is a 0 bit, so we know that "cucumber" is not present in the set. In other words, with a single hash function, two strings have a 1 in 8 chance of sharing the same hash code. With two hash functions, though, there’s only a collision if both strings share a set of two hash codes. Because there’s only a 1 in 8 chance of a single hash code being shared, there’s a 1 in 64 chance that two hash codes will be shared (1/8 * 1/8 = 1/64). And so, we significantly reduce the chances of receiving a false positive.

Too Much of a Good Thing

Because increasing the number of hash functions reduces the odds of getting false positives, it might be tempting to keep laying on the hash functions. Why stop at two hash functions when we can use six, eight, or ten? In theory, if we used 10 hash functions in our earlier example, the odds of two values sharing the same exact hash codes for all 10 hash functions should be 1 in 8 to the 10th power, which is 1 in 8,589,934,592.

However, a funny thing happens when we use too many hash functions.

Continuing with our earlier example, let’s say that we used six hash functions for our byte of data. Here’s an example of what would happen when we insert "apple":

Almost the entire byte has been turned into 1 bits. And now here’s what happens when we insert "banana" as shown in the .

Yikes—now the byte consists entirely of 1 bits! From this point on, any string we’d look up in the set would return True whether we ever inserted that value into the set or not. The only way to get a result of False is by encountering a 0 bit, but that could never happen anymore.

It’s a curious thing, but it’s true. Increasing the number of hash functions in a Bloom filter helps reduce false positives, but if we increase the number of hash functions by too much, we end up increasing false positives. The following graph illustrates what this looks like.

In this example, having just one hash function leads to a 15 percent false positive rate. As we increase the number of hash functions, the false positive rate drops. The false positive rate is at its lowest (about 5.5 percent) when we have four hash functions. However, as we continue to increase the number of hash functions beyond four, the false positive rate starts climbing higher again.

Bloom filters rely on a mathematical formula to calculate the ideal number of hash functions needed to keep both memory consumption and false positives to a minimum. So you, as the programmer, don’t need to fret about choosing the right number of hash functions. Once you program your Bloom filter correctly, it makes that decision for you.

Let’s dig into how that works.

The Bloom Filter Variables: N, M, K, and F

Throughout the remainder of this chapter, I’m going to refer to four variables that factor into making sure our Bloom filter is optimized. You’re already familiar with all the underlying concepts; I’m now assigning each concept to a variable:

• The variable N refers to the number of items we want our Bloom filter to hold.

• The variable M refers to how much memory our Bloom filter will take up, in terms of the number of bits.

• The variable K refers to the number of hash functions our Bloom filter will be using.

• The variable F refers to the false positive rate. If F is 0.01, for example, this represents 1 percent. That is, for every 100 times our Bloom filter returns True as a result of a lookup, one of those results is expected to be a false positive.

Like or hate these variable names, these are what are used in the industry, so we’ll run with them.

It turns out that these four variables are all connected to each other through a mathematical formula. It can be expressed in Python like so:

The variables f, k, n, and m refer to the F, K, N, and M variables we’ve been discussing. So, if we’d fill in n, m, and k with actual numbers into the code and run it, the result will be the value for f, which, again, is the false positivity rate. (If you’re wondering, math.e refers to a mathematical constant known as Euler’s number, which is approximately 2.71828.)

I’m not going to explain the mathematical theory behind this equation here. However, I will show you what this formula means in practical terms.

We discovered earlier that the more bits our Bloom filter contains, the lower F will be. That is, as we increase M, we have more hash codes available to us since each hash function will produce a hash code from 0 up until M. Accordingly, we reduce the chances that any two values end up with the same hash code.

At the same time, increasing M only helps if N is significantly lower than it. Imagine that M was 1,000; that is, we have 1,000 bits inside our Bloom filter. If N is 10,000, we’re still going to have way too many collisions since we’re trying to cram 10,000 values into 1,000 slots. So, the thing to focus on is the M/N ratio—how many bits our Bloom filter will store relative to the number of items it’ll hold.

For example, if we’ll be dedicating 100 bits to our Bloom filter and only inserting 10 values, the M/N ratio is:

And so, M/N being 10 means that we’re going to have 10 times as many bits as there are values in our set.

Now, the greater M/N is, the lower F is. For example, when M/N is 10, F will be lower than when M/N is, say, 6 or 8. The following graph illustrates this idea:

Here we can see how M, N, and K all affect F. When M/N = 6, meaning that there are six times as many bits as there are values in the Bloom filter, this produces one particular curve. However, you can see that the curve of M/N = 8 reaches lower levels of F. And M/N = 10 reaches yet even lower levels of F, yielding a false positivity rate that can be even lower than 1 percent.

You can also see from here that we can’t determine what F is from M/N alone. M/N only produces the curve of what F can potentially be. It’s K that finally pegs down what F is.

Take a look at the following graph. It’s the same graph shown earlier, but here I highlight what K should ideally be for each curve (approximately):

Note that the ideal K changes based on what M/N is. When M/N is 6, it turns out that F dips to its lowest point when K is about 4. When M/N is 10, though, the ideal K is around 7.

Next up, we’re going to see how to set up our Bloom filter so that it figures out for itself what its own M, F, and K should be.

The Classic Bloom Filter Constructor

The classic way to set up a Bloom filter is that upon creation, we pass in the variables N and F. This means that we need to decide in advance how many values (N) we plan on storing inside our Bloom filter. At the same time, we also need to decide the false positive rate (F) that we’re willing to tolerate for our application.

For example, we may decide that we’re going to store 100 items and that we’re only willing to tolerate a false positive rate of up to 3 percent. Our Bloom filter’s constructor starts like this:

And we’d initialize a new Bloom filter this way:

That is, N is 100, and our maximum tolerable F is 0.03.

While it may be tempting to input a super-small F such as 0.00000001, this can only be achieved with a tremendous amount of memory (M). Given that we’re using a Bloom filter to conserve memory, we want to balance our false positive rate with keeping the memory footprint small.

Code Implementation: Bloom Filter with the Classic Constructor

Without further ado, here is a basic Python implementation of a Bloom filter:

This is the classic Bloom filter I described in the previous section, which accepts two parameters: n and f. That is, the programmer decides in advance approximately how many items the set will contain and what the maximum tolerable false positive rate should be.

With n and f in hand, the constructor first computes m with this dandy formula:

This formula is derived from the other formula we encountered earlier in . In any case, our Bloom filter now knows how much memory to allocate for our application.

Now that we’ve set both n and m, we also know our M/N ratio. Effectively, the Bloom filter has selected its desired curve from the .

Once the curve has been selected, all it needs to do now is compute k so that we hit the lowest possible f along that curve. The computation for k is:

This formula, too, is derived from the original formula.

Now that we have k in hand, which, again, is the number of hash functions our Bloom filter will use, we now have to select the actual hash functions we’ll be using. We store these hash functions in the array self.hash_functions.

To create the hash functions, we bring in the DivisionHasher class we created back in . Our strategy is as follows: all of our hash functions will use division hashing. However, each hash function will incorporate a different random prime number into its division computation. (You can feel free to choose a different hashing scheme if you’d like, though. I’m simply using division hashing because it’s simple, and we’ve covered it before.)

To make sure we don’t accidentally create two identical hash functions, we keep track of each hash function’s prime number in the hash table self.hash_function_primes. Then, the following code loops until it has created k different hash functions:

The inner while loop keeps generating a random hash function (in the variable hasher) until we get one that we haven’t already created before. When we find an acceptable hash function, we append it to our array self.hash_functions.

Finally, our constructor creates a new bit vector and stores it in the variable self.bv. Here, we’re using the bit vector class we created in .

The rest of the class is relatively smooth sailing. The insert method iterates over each of the Bloom filter’s hash functions and uses each one to hash the value into a hash code. For each hash code, we then flip the corresponding bit (based on its index) in the bit vector to 1.

Similarly, the read method uses the same set of hash functions to hash the value and checks whether each hash code has a corresponding 1 bit inside the bit vector. If all the bits we check are 1, we return True to indicate that the value is currently in our set. However, if even a single bit is 0, we know that the value is not in the set and we therefore return False.

An Alternative Constructor

A potential downside with the “classic” Bloom filter constructor is that we don’t get to tell the Bloom filter how much memory it should consume. Instead, we tell it what N and F are, and it computes M based on the mathematical formula. But what if we are absolutely constrained for space? It could happen that the Bloom filter may take up more memory than we’re able to handle.

If you find yourself in this predicament, you may consider using an alternative constructor for the Bloom filter. Specifically, when we initialize the Bloom filter, instead of passing in the variables N and F, we pass N and M. By passing in M, we are dictating to the Bloom filter the absolute maximum amount of space that it should take up.

When we do this, though, we don’t get to control F. That is, when the programmer chooses N and M, it is effectively choosing which curve on the graph the Bloom filter will use. The Bloom filter then computes the appropriate K to reduce F as much as possible. However, we’re giving up our liberty to choose what F is.

For example, if we choose that M/N is 6, the best possible F we can achieve is 4 percent, period. Hopefully, that’ll be okay for your application. If that’s not okay, a Bloom filter is not going to be a good fit for your software.

Ultimately, we have two choices. With the classic constructor, we choose what F we’re willing to tolerate, and the Bloom filter chooses the lowest possible M. With the alternative constructor, we choose what M is, and we have to deal with whatever F ends up being.

In theory, there could be yet other constructors, such as choosing F and M, and let the math choose N. However, the two constructors I’ve described so far are the most common, so we’ll stick with those.

Code Implementation: Bloom Filter with an Alternative Constructor

Here is what the alternative constructor looks like:

This constructor has the arguments of n and m. The variable k is computed using the same code as the classic constructor, as only n and m are needed to compute k.

The code then computes F. In truth, F isn’t used anywhere else in the code. However, it’s useful to have so that a programmer can check what F ends up being and can decide if it’s tolerable.