Фильтр Bloom - это структура данных, позволяющая компьютерам видеть, происходит ли данный элемент в наборе. Для этого фильтры Bloom используют хэш-функции. Для каждого добавляемого элемента вычисляется значение хэша. При добавлении нового элемента его значение хэша сравнивается со значением других элементов множества. Фильтр Блума представляет собой вероятностную структуру данных. Можно получить ложное срабатывание, но нельзя получить ложное срабатывание. Другими словами, запрос возвращает либо "возможно в множестве", либо "определенно не в множестве". Элементы могут быть добавлены в множество, но не удалены. Для каждого добавляемого элемента возрастает вероятность получения ложного срабатывания.
Эдвард Блум предложил фильтр Блума в 1970 году. В статье Блум предполагает наличие алгоритма дефисования слов в конце строки. Согласно примеру, большинство слов имеют простые шаблоны дешифровки. Но около 10% слов требуют трудоемкого поиска, чтобы получить правильное правило. В его случае дефисом было около 500 000 слов. Он видел, что при использовании "обычных" безошибочных техник хеширования, при хранении шаблонов дефисов, потребуется много памяти. Он обнаружил, что используя свою технику, он может исключить большинство поисков. Например, область хэша всего в 15% от размера, необходимого для идеального безошибочного хэша, по-прежнему исключает 85% доступа к диску.
В более общем случае для 1 % ложноположительной вероятности, независимо от размера или количества элементов в наборе, требуется менее 10 бит на элемент.