As we saw in the previous chapter, we often need to be cognizant of how our data structures fit into local memory and how to limit retrievals from slower memory. As a data structure grows, it can store more data but might not be able to fit into the fastest memory. This chapter introduces the Bloom filter, a data structure that extends the core concepts behind a hash table to limit the amount of memory needed to filter over a large key space.
Bloom filters were invented in 1970 by computer scientist Burton Bloom. A Bloom filter tracks which keys have been inserted while ruthlessly optimizing for both memory usage and execution ...
Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month, and much more.
