Bloom Filter

probabilistic data structure

good to use if you could use a hash table if your data was smaller

false positives are possible - could say item exists when it doesn’t

false negatives are not - if it says item doesn’t exist then it doesn’t

takes up very little space


approximates unique items in a set

uses a lot less memory because answers are not exact

keeps list of distinct items