블룸 필터(bloom filter)는 해시 테이블에 비해 공간 효율이 매우 높은 방법이지만, 결정적(deterministic) 솔루션 대신 부정확한 결과를 얻을 수 있습니다. 블룸 필터는 거짓-부정(false negative)이 없다는 것은 보장하지만, 거짓-긍정(false positive)은 나올 수 있습니다. 즉, 특정 원소가 존재한다는 긍정적인 답변을 받을 경우, 이 원소는 실제로 있을 수도 있고 없을 수도 있습니다. 그러나 특정 원소가 존재하지 않는다는 부정적인 답변을 받았다면 이 원소는 확실히 없습니다.

뻐꾸기 해싱과 마찬가지로 블룸 필터도 여러 개의 해시 함수를 사용합니다. 보통 두 개의 해시 함수는 충분한 정확도를 기대하기 어렵기 때문에 세 개 이상을 사용해야 합니다. 블룸 필터는 실제 값을 저장하지는 않으며, 대신 특정 값이 있는지 없는지를 나타내는 부울 타입 배열을 사용합니다.

원소를 삽입할 경우, 모든 해시 함수 값을 계산하고 부울 타입 배열에서 이 해시 값에 대응되는 위치의 비트 값을 1로 설정합니다. 룩업의 경우, 모든 해시 함수 값을 계산하고 이에 대응되는 위치의 비트 값이 1로 설정되어 있는지를 검사합니다. 만약 검사한 모든 비트가 1이면 true를 반환합니다. 1이 아닌 비트가 하나라도 있다면 false를 반환하고, 이는 해당 원소가 없음을 의미합니다.

그럼 블룸 필터가 왜 결정적이지 않은 것일까요? 그 이유는 특정 비트가 다수의 원소에 의해 1로 설정될 수 있기 때문입니다. 즉, 특정 값 x와 연관된 모든 비트가 이전에 삽입된 다른 원소 값들에 의해 모두 1로 설정되어 있을 가능성이 있다는 뜻입니다. 이러한 경우 x에 대한 룩업 함수는 true를 반환할 것입니다. 이처럼 특정 원소가 있다고 잘못 판단하는 것을 거짓-긍정이라고 합니다. 원소 개수가 많아질수록 거짓-긍정이 발생할 가능성은 증가합니다. 그러나 x와 연관된 비트 중 하나라도 1로 설정되어 있지 않다면 x가 확실하게 없다고 말할 수 있습니다. 그러므로 거짓-부정은 발생할 수 없습니다.