A data structure that is used to test when an element is a member of a set. False positive members are possible (element not in the set, but the query says yes, it is there). However, false negatives are not possible (element is in the set, the query will always return that yes, it is there). One could use a hash table to do something similar, but a bloom filter is more space efficient. It may be used in firewalls to check if an IP address has been seen before. How it works: (0) Allocate an array that stores bits (0 and 1) (1) Use several independent hash functions to transform each element into a bit for each kth hash function: if the bit after hashing 1: turn on that bit in the array Now, if we want to test if an element is in an array: for each kth hash function: hash that object to a bit if the bit is 0: object not in array (all bits are 1) => object in array