Chapter 13
Cultivating Efficiency with Bloom Filters

In the previous chapter, you discovered that bit vectors can store a lot of data in an incredibly compact way. In fact, one could argue that bit vectors are the most compact of all data structures. So, if you’re looking to save space, bit vectors are an incredible tool.

However, you also learned that bit vectors are only useful in certain scenarios, specifically, where the data consists of integers that lie within a relatively short range. If you were to store integers in a large range or if you had other forms of data, such as strings, you wouldn’t be able to take advantage of the great space savings bit vectors afford.

Fortunately, there’s a variant of the bit vector that can handle even these other scenarios. In this chapter, you’ll read about the Bloom filter, a data structure that acts like a bit vector but can save space for virtually all types of data. Bloom filters are incredibly clever and rely on several concepts we explored previously, including Monte Carlo algorithms and hash function families. By the time you’re done with this chapter, you’ll be able to implement your own basic Bloom filter and use it to save space across many different applications.