13 Bloom Filters
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 ...
Get Data Structures the Fun Way now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
