블룸 필터 원리 – 비트 배열과 여러 해시로 만드는 확률적 집합 자료구조

핵심 메시지

• 블룸 필터는 원소 포함 여부를 물었을 때 "아마 있음"(틀릴 수 있음)과 "확실히 없음"(절대 틀리지 않음) 두 종류의 답만 내놓는 자료구조다.
• 내부는 모두 0으로 시작하는 비트 배열이며, 키를 넣을 때 여러 해시로 얻은 여러 비트를 1로 켠다.
• 검사 시 해당 비트 중 하나라도 0이면 그 키는 확실히 없는 것이고, 모두 1이면 다른 키들이 켠 비트일 수 있어 "아마 있음"에 그친다.
• 거짓 양성(있다고 잘못 말할) 확률은 삽입 개수 n, 비트 수 m, 해시 개수 k로 근사할 수 있으며, k를 적절히 고르면 최소화된다.
• 정확성을 비트로 맞바꾸는 이 성질 덕분에 데이터베이스·캐시·라우터·블록체인 등에서 값비싼 조회를 건너뛰는 빠른 사전 확인용으로 널리 쓰인다.

쉽게 이해하기

블룸 필터의 답은 두 가지뿐이다. "아마 있음"은 때때로 거짓말일 수 있지만, "확실히 없음"은 언제나 진실이다. 이 비대칭이 블룸 필터의 핵심 성격이다.

구조 자체는 단순하다. 모두 0인 비트의 한 줄에서 시작해, 키를 삽입할 때 그 키를 해시해 나온 위치의 비트를 1로 켠다. 그런데 서로 다른 두 키가 같은 위치로 해시될 수 있어(예: apple과 cherry가 같은 자리로), 해시가 하나뿐이면 충돌이 너무 많아진다.

그래서 하나가 아니라 K개의 해시를 쓴다. 각 키는 K가지 방식으로 해시되어 그만큼의 비트를 1로 켜고, 일부는 이미 켜진 비트와 겹쳐도 상관없다. 이렇게 비트 배열 자체가 필터가 되고, 원래 키들은 버려도 된다.

어떤 키가 들어 있는지 확인하려면 같은 K개의 해시로 그 비트들을 본다. 하나라도 0이면 그 키는 삽입된 적이 없다는 증거이므로 "확실히 없음"이다. 반대로 모든 비트가 1이면, 그 1들이 다른 키들 때문에 켜졌을 수도 있으므로 "아마 있음"일 뿐이다. 넣은 적 없는 키가 우연히 다른 키들이 켠 비트에 모두 걸리면 필터가 거짓 양성을 낸다.

거짓 양성 확률은 대략 (1 − e^(−kn/m))^k 로 근사되며, 여기서 n은 삽입한 원소 수, m은 비트 수, k는 해시 개수다. 오류는 k가 (m/n)·ln2 일 때 최소가 되는데, 예컨대 원소당 10비트에 해시 7개면 1% 미만으로 틀린다.

주요 인사이트

• 한쪽으로만 틀린다는 점이 핵심이다. 0 비트는 거짓말을 못 하므로 "없음"은 확실하고, 1 비트는 어디서 왔는지 알 수 없어 "있음"은 확률적이다.
• 키 자체를 저장하지 않고 비트만 유지하므로 메모리를 크게 아낀다. 정확성을 비트 수와 맞바꾸는 셈이다.
• 해시 개수 k는 많을수록 좋은 게 아니라 최적값이 존재한다. m/n에 ln2를 곱한 값 부근에서 거짓 양성이 최소화된다.
• "여기 있을지도 모른다"는 빠른 확인이 값비싼 실제 조회를 줄여주기 때문에 데이터베이스·캐시·라우터·블록체인 곳곳에 조용히 들어가 있다.

자주 묻는 질문

관련 AI 소식