Een Bloom filter is een datastructuur waarmee computers kunnen zien of een bepaald element in een set voorkomt. Bloeifilters gebruiken hiervoor hash-functies. Voor elk element dat wordt toegevoegd, wordt een hashwaarde berekend. Wanneer een nieuw element wordt toegevoegd, wordt de hashwaarde ervan vergeleken met die van de andere elementen in de verzameling. Een Bloom filter is een probabilistische datastructuur. Het is mogelijk om een vals-positief te krijgen, maar niet om een vals negatief te krijgen. Met andere woorden, een query geeft ofwel "mogelijk in set" ofwel "zeker niet in set". Elementen kunnen worden toegevoegd aan de set, maar niet verwijderd. Voor elk toegevoegd element groeit de kans om een vals-positief te krijgen.
Edward Bloom stelde de Bloom-filter voor in 1970. In het artikel veronderstelt Bloom dat er een algoritme is om woorden aan het eind van een regel af te breken. Volgens het voorbeeld hebben de meeste woorden eenvoudige afbreekpatronen. Maar ongeveer 10% van de woorden heeft tijdrovende opzoekingen nodig om de juiste regel te vinden. Zijn geval was dat van het afbreken van ongeveer 500.000 woorden. Hij zag dat het gebruik van de "normale" foutloze hashing technieken, het opslaan van de afbreekpatronen, veel geheugen nodig zou hebben. Hij vond dat hij met behulp van zijn techniek de meeste opzoekingen kon elimineren. Bijvoorbeeld, een hashgebied dat slechts 15% van de grootte heeft die nodig is voor een ideale foutvrije hash elimineert nog steeds 85% van de schijftoegangen.
Meer in het algemeen zijn er minder dan 10 bits per element nodig voor een vals-positieve kans van 1%, onafhankelijk van de grootte of het aantal elementen in de set.