블룸 필터(Bloom Filter)는 1970년 Burton Bloom이 제안한 확률적 자료구조다. 원소가 집합에 속하는지 빠르게 확인하며, 공간 효율이 매우 높다. 거짓 양성(False Positive) 이 발생할 수 있지만 거짓 음성(False Negative)은 절대 없다.
핵심 아이디어
비트 배열(bit array)과 여러 해시 함수를 조합한다. 삽입 시 k개의 해시 함수로 인덱스를 계산해 해당 비트를 1로 설정하고, 조회 시 모든 비트가 1이면 "있을 수 있음", 하나라도 0이면 "확실히 없음"을 반환한다.
비트 배열 (크기 m=10, 초기: 모두 0)
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
0 1 2 3 4 5 6 7 8 9
"Alice" 삽입 (k=3 해시 함수):
h1("Alice") = 2 → 비트[2] = 1
h2("Alice") = 5 → 비트[5] = 1
h3("Alice") = 8 → 비트[8] = 1
[0, 0, 1, 0, 0, 1, 0, 0, 1, 0]
"Bob" 삽입:
h1("Bob") = 1, h2("Bob") = 4, h3("Bob") = 7
[0, 1, 1, 0, 1, 1, 0, 1, 1, 0]
"Alice" 조회:
비트[2]=1, 비트[5]=1, 비트[8]=1 → 모두 1 → "있을 수 있음" ✓
"Charlie" 조회:
h1("Charlie") = 3 → 비트[3]=0 → 하나라도 0 → "확실히 없음" ✓
"Dave" 조회 (실제로는 없는데):
h1("Dave")=1, h2("Dave")=4, h3("Dave")=7 → 모두 1 → "있을 수 있음" ← False Positive!
핵심 메서드
| 메서드 | 설명 |
|---|
insert(item) | k개 해시 인덱스 비트를 1로 설정 |
contains(item) | k개 비트가 모두 1이면 true, 아니면 false |
clear() | 비트 배열 전체 0으로 초기화 |
merge(other) | 두 필터의 비트 배열 OR 연산으로 합산 |
특성
| 특성 | 설명 |
|---|
| 거짓 음성 (False Negative) | 절대 없음 — "없다"고 하면 확실히 없음 |
| 거짓 양성 (False Positive) | 발생 가능 — "있다"고 해도 실제로 없을 수 있음 |
| 삭제 | 기본 블룸 필터는 불가 (카운팅 블룸 필터로 해결) |
| 공간 | 해시맵보다 훨씬 적은 메모리 |
| 시간 복잡도 | O(k) — 해시 함수 개수에만 비례 |
거짓 양성률 수식
비트 배열 크기 m, 해시 함수 k개, 삽입된 원소 n개일 때 거짓 양성 확률:
P(false positive) ≈ (1 - e^(-kn/m))^k
최적 해시 함수 개수:
k_opt = (m/n) × ln(2) ≈ 0.693 × (m/n)
예시: m=1000, n=100, k=7
P ≈ (1 - e^(-7×100/1000))^7 ≈ 0.83% (약 1% 미만)
비트 배열을 크게 할수록, 해시 함수를 최적 개수에 맞출수록 거짓 양성률이 낮아진다.
python
import hashlib
from bitarray import bitarray
class BloomFilter:
def __init__(self, size: int = 1000, hash_count: int = 7):
self.size = size
self.hash_count = hash_count
self.bits = bitarray(size)
self.bits.setall(0)
def _hashes(self, item: str):
for seed in range(self.hash_count):
h = hashlib.md5(f"{item}{seed}".encode()).hexdigest()
yield int(h, 16) % self.size
def insert(self, item: str):
for idx in self._hashes(item):
self.bits[idx] = 1
def contains(self, item: str) -> bool:
return all(self.bits[idx] for idx in self._hashes(item))
def clear(self):
self.bits.setall(0)
def merge(self, other: 'BloomFilter'):
assert self.size == other.size
self.bits |= other.bits
# 사용 예시
bf = BloomFilter(size=1000, hash_count=7)
bf.insert("alice@example.com")
bf.insert("bob@example.com")
print(bf.contains("alice@example.com")) # True (정확)
print(bf.contains("charlie@example.com")) # False (확실히 없음)
카운팅 블룸 필터
기본 블룸 필터는 삭제가 불가능하다. 카운팅 블룸 필터는 비트 대신 카운터를 사용해 삭제를 지원한다.
기본 블룸 필터: [0, 1, 0, 1, 0, 1]
카운팅 블룸 필터: [0, 2, 0, 1, 0, 3] ← 각 슬롯이 정수 카운터
삽입: 해당 슬롯 카운터 +1
삭제: 해당 슬롯 카운터 -1 (0 이하가 되면 0으로 유지)
단점: 메모리 사용량 증가 (비트 → 정수)
활용 사례
| 분야 | 사례 |
|---|
| 데이터베이스 | Bigtable·HBase·Cassandra — 디스크 접근 전 키 존재 여부 확인 |
| 웹 브라우저 | 크롬 — 악성 URL 필터링 (Safe Browsing API) |
| CDN | 캐시 히트 여부 빠른 확인 |
| 보안 | HaveIBeenPwned — 비밀번호 유출 확인 |
| 웹 크롤러 | 이미 방문한 URL 중복 방지 |
| 추천 시스템 | 이미 노출된 콘텐츠 재노출 방지 |
| 네트워크 | 라우터에서 패킷 중복 감지 |
블룸 필터 vs 해시셋
| 항목 | 블룸 필터 | 해시셋 |
|---|
| 공간 | O(m) 비트 — 매우 작음 | O(n) — 원소 수에 비례 |
| 삽입 | O(k) | O(1) 평균 |
| 조회 | O(k) | O(1) 평균 |
| False Positive | 있음 | 없음 |
| 삭제 | 기본 불가 | 가능 |
| 원소 열거 | 불가 | 가능 |
1억 개의 URL(평균 50바이트) 저장 시: 해시셋 ≈ 5GB, 블룸 필터 ≈ 200MB 수준.
관련 개념
- •해시 (Hash) — 블룸 필터의 핵심 해시 함수
- •해시맵 — 블룸 필터의 대안 (더 많은 메모리, 정확)
- •웹 크롤러 설계 — URL 방문 여부 추적에 블룸 필터 활용
- •캐시 — CDN 캐시 히트 판단에 적용
참고문헌
- •Bloom, B.H. (1970). Space/Time Trade-offs in Hash Coding with Allowable Errors
- •Tasker Dev. Bloom Filters. Velog
