membership structures bloom filters bloom filters are named for their creatorburton howard bloomwho originally proposed this idea in since then many authors have covered the implementations of bloom filters including alan tharp [ wikipediawhile not always the authoritative sourcehas very good discussion of bloom filters as well [ bloom filter shares some ideas with hash sets while using considerably less space bloom filter is data structure employing statistical probability to determine if an item is member of set of values bloom filters are not accurate bloom filter will never report false negative for set membershipmeaning that they will never report that an item doesn' belong to set when it actually does howevera bloom filter will sometimes report false positive it may report an item is in set when it is actually not consider the problem of spell checking spell checker needs to know if typed word is correctly typed by looking it up in the dictionary with bloom filterthe typed word can be given to the bloom filter which will report that it is or is not correctly typed word in some cases it may report word is correct when it is not bloom filter is an array of bits along with set of hashing functions the number of bits in the filter and the number of hashing functions influences the accuracy of the bloom filter the exact number of bits and hash functions will be discussed later consider bloom filter with bits and independent hash functions initially all the bits in the filter are set to as shown in fig consider adding the word cow to the bloom filter assume that three independent hash functions hash the word cowmodulo to and respectively the bits at indices and are set to to remember that cow has been added to the filter as shown in fig now consider adding the word cat to the same filter assume the hash values from the three hash functionsmodulo are and inserting cat into the filter results in setting the bit at index to the other two were already set by inserting cow finallyinserting dog into the filter results in the bloom filter shown in fig the hash values for dog are and fig an empty bloom filter fig after inserting cow into the bloom filter this copy belongs to 'acha