블룸 필터(Bloom filter)는 해시 테이블의 핵심 개념을 확장해 대용량 키 공간을 필터링할 때 필요한 메모리양을 제한하는 자료 구조.
블룸 필터는 어떤 키가 삽입되었는지를 추적하면서 메모리 사용량과 실행 시간을 무자비하게 최적화한다.
블룸 필터는 아주 단순한 예/아니오 질문인 ‘이전에 어떤 키를 본 적이 있는가’라는 문제에 대한 답을 제공한다.
최적의 효율성을 위해 블룸 필터는 위양성(false positive) 결과를 가져올 수 있는 방식을 사용한다. ⇒ 블룸 필터가 키가 삽입됐다고 판정했는데 실제로는 삽입되지 않았을 확률이 0이 아니라는 뜻.
블룸 필터는 메모리 부가 비용이 낮고 빠른 실행 시간을 보장하면서 위음성(false negative, 실제 삽입된 키에 대해 그 키가 삽입된 적이 없다고 판정하는 경우)이 없기 때문에 선별 작업이나 더 비싼 자료구조에 액세스하기 전의 사전 검사에 유용하다.
데이터 집합에 레코드가 있는지 확인하고 싶으면 먼저 블룸 필터를 사용해 레코드가 삽입된 적이 있는지 확인한다. 블룸 필터는 빠른 메모리에 있는 간결한 자료 구조이므로 이런 검사를 빠르게 수행할 수 있다.
블룸 필터는 때로는 존재하지 않는 레코드를 탐색하게 허용하기도 하지만, 많은 무의미한 탐색을 피하는데 도움이 된다. 블룸 필터가 데이터 집합에 레코드가 없다고 판정할 때마다 우리는 즉시 탐색을 중지할 수 있다.
블룸 필터는 핵심적으로 이진 값들의 배열이다. 각 상자는 그 상자에 해당하는 해시 값에 대해 이전에 무언가가 매핑된 적이 있었는지를 추적한다.
블룸 필터는 많은 값 중에 특정 값을 쉽게 찾고 싶을 때 유용하다.
블룸 필터는 해시 테이블과 달리 체이닝 등 충돌 메커니즘을 사용하지 않음
출돌이 증가하는 문제를 가장 간단히 해결하는 방법은 해시 값의 공간을 늘리는 것이다.
블룸 필터는 충돌 문제를 해결하기 위해 해시 함수의 개념을 극한까지 확장한다. 각 키에 대해 해시 함수를 하나만 사용하는 대신, 키를 범위가 같은 해시 값으로 매핑하는 k개의 독립적인 해시 함수를 사용한다.