블룸 필터(Bloom filter)는 어떤 원소가 주어진 집합에 속하는지를 빠르게(그러나 확률적으로) 판별하기 위한 자료구조다. 크기 $m$(엠)인 비트배열 $B[0], B[1], \dots, B[m-1]$과, 서로 독립적인 해시 함수 $h_1, h_2, \dots, h_k$($k$는 해시 함수의 개수) 를 사용한다. 초기에는 모든 비트를 $0$으로 둔다.
삽입: 원소 $x$를 넣을 때, $h_1(x), h_2(x), \dots, h_k(x)$($h_i(x)$는 "에이치 아이 엑스", 해시 함수 $h_i$에 $x$를 대입한 나머지값)를 계산하여 $B[h_i(x) \bmod m]$($\bmod$는 "모드", 나눗셈의 나머지)의 비트를 모두 $1$로 바꾼다.
조회: 원소 $y$가 속하는지 확인할 때, $B[h_i(y) \bmod m]$이 모두 $1$이면 "속할 가능성 있음", 하나라도 $0$이면 "확실히 속하지 않음"이라고 답한다.
즉 블룸 필터는 "없다"는 답은 항상 정확하지만, "있다"는 답은 실제로는 없는데 우연히 비트가 겹쳐 있다고 잘못 판정하는 거짓 양성(false positive)이 발생할 수 있는 자료구조다.
직관
도서관 서가에 책이 있는지 확인하는 대신, 여러 개의 스위치 판을 두고 "이 책을 등록한 적 있다면 이 스위치들을 켜 둔다"고 약속했다고 생각해 보자. 스위치가 하나라도 꺼져 있으면 그 책은 확실히 등록된 적이 없다. 하지만 스위치가 전부 켜져 있어도, 그건 다른 책들 때문에 우연히 켜졌을 수도 있다. 블룸 필터는 정확한 값을 저장하지 않는 대신, 아주 작은 메모리로 "없음"을 빠르게 확인해 주는 도구다. 이 절충 덕분에 실제 원소를 저장하는 해시와 나머지 연산 기반 자료구조보다 훨씬 적은 공간을 쓴다.
성질
원소 $n$개($n$은 삽입된 원소 개수)를 넣은 뒤, 임의의 비트 하나가 특정 해시 한 번으로 $1$이 되지 않을 확률은 $1-\dfrac{1}{m}$이다. $k$번의 해시를 $n$개 원소에 대해 적용하면 그 비트가 여전히 $0$일 확률은
$$\left(1-\frac{1}{m}\right)^{kn}$$
이다. $m$이 충분히 크면 $\lim_{m\to\infty}\left(1-\dfrac{1}{m}\right)^{m} = e^{-1}$($e$는 자연상수, "이"라고 읽는다)이므로 이 확률은 $e^{-kn/m}$으로 근사된다. 따라서 거짓 양성 확률(모든 비트가 우연히 $1$일 확률)은
즉 약 $0.8\%$ 확률로 없는 원소를 "있을 수도 있음"이라고 잘못 답한다. 실제로 $k^{*}=\dfrac{1000}{100}\ln2 \approx 6.93$이므로 $k=7$은 이 조건에서 거의 최적의 선택이다.
$m=1000$, $n=100$을 고정하고 $k$를 바꿔가며 거짓 양성 확률 $p(k)=(1-e^{-k/10})^{k}$의 변화를 그려 보면 $k\approx7$ 근처에서 최솟값을 가짐을 확인할 수 있다.
🌍 실생활 예시
웹 브라우저는 악성 사이트 목록을 블룸 필터로 관리한다. 사용자가 어떤 주소에 접속하려 할 때, 블룸 필터가 "목록에 없음"이라고 답하면 즉시 안전하다고 판단해 통과시키고(이 판정은 항상 정확), "있을 수도 있음"이라고 답할 때만 서버에 다시 문의해 정확히 확인한다. 이렇게 하면 수백만 개의 악성 주소 목록을 매번 서버에 물어보지 않고도 대부분의 안전한 주소를 빠르게 걸러낼 수 있다.
⚠️ 흔은 실수
"있을 수도 있음"이라는 답을 곧 "있다"로 착각한다 → 실제로는 다른 원소들의 해시값이 겹쳐 비트가 우연히 모두 $1$이 될 수 있다. 블룸 필터가 100% 확신할 수 있는 답은 오직 "없다"뿐이다.
해시 함수 개수 $k$를 늘릴수록 항상 정확해진다고 생각한다 → $k$가 너무 커지면 삽입할 때마다 비트가 더 많이 $1$로 바뀌어 배열이 빨리 포화되고, 오히려 거짓 양성 확률이 증가한다. 최적값은 $k^{*}=\dfrac{m}{n}\ln2$로 정해져 있다.
블룸 필터에서 원소를 삭제할 수 있다고 생각한다 → 여러 원소가 같은 비트를 공유하므로 한 원소를 지우려고 비트를 $0$으로 되돌리면, 그 비트를 함께 쓰던 다른 원소까지 "없음"으로 잘못 판정될 수 있다. 기본 블룸 필터는 삭제를 지원하지 않는다.
확인 문제
$m=100$, $n=10$인 블룸 필터에서 거짓 양성 확률을 최소로 만드는 해시 함수 개수 $k^{*}$를 구하여라. 그리고 그 $k^{*}$를 정수로 반올림했을 때, $k$를 그보다 훨씬 크게(예: $k=30$) 잡으면 왜 오히려 성능이 나빠지는지 $p\approx(1-e^{-kn/m})^{k}$ 식을 이용해 설명하여라.
$m=500$, $n=50$, $k=5$일 때 거짓 양성 확률 $p$를 근사식으로 계산하여라. (단, $e^{-0.5}\approx0.607$로 계산한다.)
블룸 필터가 어떤 원소 $x$에 대해 "없다"고 답했는데 실제로 $x$가 집합에 있었던 적이 있다면, 이것이 왜 논리적으로 불가능한지 삽입 과정을 근거로 설명하여라.
정답 보기
$k^{*}=\dfrac{m}{n}\ln2=\dfrac{100}{10}\ln2\approx6.93$, 반올림하면 $7$. $k=30$처럼 지나치게 크게 잡으면 원소 하나를 넣을 때마다 $30$개의 비트가 $1$로 바뀌어 배열이 금방 거의 다 $1$로 채워지고, 결국 $(1-e^{-kn/m})$이 $1$에 매우 가까워져 $p$도 $1$에 가깝게 커진다. 즉 해시 개수는 무조건 많다고 좋은 게 아니라 $m,n$에 맞는 최적값이 존재한다.
$\dfrac{kn}{m}=\dfrac{5\times50}{500}=0.5$이므로 $p\approx(1-0.607)^{5}=0.393^{5}\approx0.0093$, 약 $0.93\%$.
삽입 과정에서 $x$를 넣었다면 $h_1(x),\dots,h_k(x)$에 해당하는 비트가 모두 $1$로 설정되어 이후 절대 $0$으로 되돌아가지 않는다(기본 블룸 필터는 삭제를 지원하지 않으므로). 따라서 $x$를 조회하면 그 비트들이 항상 $1$이어서 "없다"고 답할 수 없다. 이것이 블룸 필터에 거짓 음성이 없는 이유다.