블룸 필터 (Bloom Filter)

블룸 필터 (Bloom Filter)

원소의 존재 여부를 확률적으로 판단하는 공간 효율적인 자료구조로, 거짓 긍정(False Positive)은 가능하지만 거짓 부정(False Negative)은 없으며 비트 배열과 해시 함수를 활용

목적: 공간 효율적 집합 멤버십 테스트, 빠른 존재 확인, 대용량 데이터 필터링

특징: 확률적, 거짓 긍정 가능, 거짓 부정 없음, 삭제 불가, 매우 작은 메모리

구성요소: ① 비트 배열(m비트, 초기 0) ② k개 해시 함수

동작

• •add(x): k개 해시 함수로 k개 인덱스 계산 → 해당 비트 1로 설정
• •contains(x): k개 해시 함수로 k개 인덱스 계산 → 모두 1이면 "있을 수 있음", 하나라도 0이면 "확실히 없음"

거짓 긍정률(FPR): p ≈ (1 - e^(-kn/m))^k, n = 원소 수, m = 비트 배열 크기, k = 해시 함수 수

최적 해시 함수 수: k = (m/n) × ln(2) ≈ 0.693 × m/n

시간 복잡도: add·contains O(k), k는 상수

공간 복잡도: O(m) - 비트 배열, 매우 작음(원소당 수 비트)

장점: 매우 작은 메모리, 빠른 연산(O(k)), 거짓 부정 없음, 확장 가능

단점: 거짓 긍정 가능, 삭제 불가(Counting Bloom Filter로 해결), 정확한 멤버십 불가

적용사례

• •데이터베이스(불필요한 디스크 I/O 방지)
• •웹 캐시(중복 URL 필터)
• •네트워크 라우터(블랙리스트)
• •크롬(악성 URL 필터)
• •빅데이터(중복 검사)
• •블록체인(경량 클라이언트)

변형: Counting Bloom Filter(삭제 가능), Cuckoo Filter

비교: 블룸 필터(확률적/작음/빠름) vs 해시 테이블(정확/큼/빠름)

연관: 해시 함수, 확률적 자료구조, 거짓 긍정, Cuckoo Filter