한양과기고 에듀테크 수업도구 대시보드

블룸 필터 (Bloom Filter)

블룸 필터는 "이 원소가 집합에 있나요?"라는 질문에 아주 적은 메모리로 답하는 확률적 자료구조다. 원소 자체는 저장하지 않고, 비트 배열 하나와 여러 개의 해시 함수만 쓴다. 대답은 딱 두 가지: "확실히 없음" 또는 "아마 있음". 거짓 양성(false positive)은 있어도 거짓 음성(false negative)은 절대 없다는 게 핵심이다.

직접 해보기 — 단어를 넣고, 없는 단어로 조회해 보자

해시 함수 개수 k 3 · 비트 배열 크기 m = 32

단어를 넣으면 k개의 해시 위치 비트가 1로 켜집니다.

실제로 넣은 단어 (필터는 이 목록을 저장하지 않지만, 비교용으로 표시):

아직 없음

초록 = 켜진 비트(1) · 주황 = 지금 조회가 확인한 비트(모두 1) · 빨강 = 0인 비트를 만나 "없음" 확정

어떻게 동작할까

넣기 (add)

원소를 k개의 서로 다른 해시 함수에 통과시킨다.
각 결과를 mod m 해서 비트 배열의 위치 k개를 얻는다.
그 위치의 비트를 모두 1로 켠다 (이미 1이면 그대로).
원소 값은 어디에도 저장하지 않는다 → 삭제도 불가.

조회 (query)

같은 k개 해시로 위치 k개를 계산한다.
하나라도 0이면 → 확실히 없음.
전부 1이면 → 아마 있음 (다른 원소들이 우연히 그 비트들을 다 켰을 수 있음 = 거짓 양성).
넣은 적 있는 원소는 반드시 전부 1 → 거짓 음성 0%.

비유: 도서관에서 책 제목을 듣고 "그런 책 절대 없어요"는 확신할 수 있지만, "아마 있을 거예요, 서가 가서 확인하세요"라고 답하는 사서. 헛걸음(거짓 양성)은 가끔 시키지만, 있는 책을 없다고 하진 않는다.

거짓 양성률(FPR) 계산기 — 크기·해시 개수·원소 수를 조절해 보자

비트 배열 크기 m 9,600

해시 함수 개수 k 7

넣을 원소 수 n 1,000

예상 거짓 양성률 (1 − e^−kn/m)^k

—

원소당 메모리 (m / n)

—

이 m, n에서 최적 k = (m/n)·ln2

—

슬라이더를 움직이면 값이 실시간으로 바뀝니다.

직관: 비트 배열을 키우면(m↑) 충돌이 줄어 FPR이 낮아진다. 해시를 너무 많이 쓰면(k↑) 비트가 빨리 가득 차서 오히려 나빠진다 — 그래서 최적 k가 존재한다. 예: 원소당 10비트(약 1.25바이트)면 최적 k≈7에서 FPR이 약 1%. 해시맵/셋이 원소당 수십~수백 바이트를 쓰는 것과 비교하면 극단적으로 작다.

해시 셋(HashSet)과 비교

항목	블룸 필터	해시 셋 / 딕셔너리
원소당 메모리	몇 비트 (예: ~10bit)	키 크기 + 포인터 (수십~수백 byte)
add / query	`O(k)` 상수	`O(1)` 평균
"없음" 응답	항상 정확	항상 정확
"있음" 응답	가끔 틀림 (거짓 양성)	항상 정확
원소 나열 / 조회	불가 (값을 안 가짐)	가능
삭제	불가 (Counting Bloom은 가능)	가능

언제 쓰나: "대부분 없을 것"이 예상되고, 비싼 확인(디스크 읽기·네트워크 요청)을 미리 걸러내고 싶을 때. 거짓 양성은 "헛걸음 한 번"으로 끝나지만, 거짓 음성이 없으므로 있는 걸 놓치지 않는다.

파이썬으로 구현 (double hashing으로 k개 해시 생성)

import hashlib, math

class BloomFilter:
    def __init__(self, n, fpr=0.01):
        # 목표 원소 수 n, 목표 거짓 양성률 fpr 로부터 m, k 계산
        self.m = math.ceil(-n * math.log(fpr) / (math.log(2) ** 2))
        self.k = max(1, round((self.m / n) * math.log(2)))
        self.bits = bytearray((self.m + 7) // 8)

    def _positions(self, item):
        d = hashlib.sha256(str(item).encode()).digest()
        h1 = int.from_bytes(d[:8], "big")
        h2 = int.from_bytes(d[8:16], "big") | 1
        for i in range(self.k):       # gi(x) = h1 + i*h2  (mod m)
            yield (h1 + i * h2) % self.m

    def add(self, item):
        for p in self._positions(item):
            self.bits[p >> 3] |= 1 << (p & 7)

    def __contains__(self, item):
        return all(self.bits[p >> 3] & (1 << (p & 7))
                   for p in self._positions(item))

# bf = BloomFilter(n=10000, fpr=0.01)
# bf.add("apple");  "apple" in bf  -> True
# "banana" in bf  -> False (거의 항상), 드물게 True (거짓 양성)

실제로 어디에 쓰일까

데이터베이스 (Cassandra·HBase·RocksDB) — SSTable마다 블룸 필터를 두고, 없는 키의 디스크 읽기를 건너뛴다.
웹 브라우저 (예전 크롬) — 악성 URL 목록을 블룸 필터로 빠르게 1차 판별.
CDN·캐시 — "한 번만 요청된 객체는 캐싱 안 함" 규칙(one-hit-wonder 필터링).
비트코인 (SPV 지갑) — 관심 주소만 필터로 요청해 프라이버시·대역폭 절약.
스팸·중복 제거 — 이미 본 URL·기사·추천 항목인지 대략 체크.

변형: 삭제가 필요하면 비트 대신 카운터를 쓰는 Counting Bloom Filter, 용량이 자라야 하면 Scalable Bloom Filter, 더 적은 공간에 같은 정확도를 원하면 Cuckoo Filter·XOR Filter를 쓴다.