Un filtro Bloom è una struttura di dati che permette ai computer di vedere se un dato elemento è presente in un set. I filtri Bloom utilizzano funzioni hash per fare questo. Per ogni elemento che viene aggiunto, viene calcolato un valore di hash. Quando un nuovo elemento viene aggiunto, il suo valore di hash viene confrontato con quello degli altri elementi dell'insieme. Un filtro Bloom è una struttura di dati probabilistica. È possibile ottenere un falso positivo, ma non un falso negativo. In altre parole, una query restituisce "possibilmente nell'insieme" o "decisamente non nell'insieme". Gli elementi possono essere aggiunti al set, ma non rimossi. Per ogni elemento aggiunto, la probabilità di ottenere un falso positivo cresce.
Edward Bloom propose il filtro Bloom nel 1970. Nell'articolo, Bloom suppone che ci sia un algoritmo per sillabare le parole alla fine di una riga. Secondo l'esempio, la maggior parte delle parole ha un semplice schema di sillabazione. Ma circa il 10% delle parole richiede un lungo lavoro di ricerca per trovare la regola corretta. Il suo caso è stato quello della sillabazione di circa 500.000 parole. Egli ha visto che l'uso delle "normali" tecniche di hashing senza errori, memorizzando gli schemi di sillabazione, avrebbe richiesto molta memoria. Scoprì che usando la sua tecnica, poteva eliminare la maggior parte delle ricerche. Per esempio, un'area di hash solo il 15% della dimensione necessaria per un hash ideale senza errori elimina ancora l'85% degli accessi al disco.
Più in generale, sono necessari meno di 10 bit per elemento per una probabilità di falsi positivi dell'1%, indipendentemente dalle dimensioni o dal numero di elementi dell'insieme.