최종 업데이트: 2026-07-13

블룸 필터 크기

블룸 필터는 단 하나의 질문에 답하는 간결한 방법입니다. "이 원소를 아마 전에 본 적이 있는가?" 블룸 필터는 키를 저장하지 않고 비트 배열만 유지하며, 작고 조절 가능한 오탐 확률을 큰 메모리 절감과 맞바꿉니다. 그 형태를 결정하는 것은 두 숫자, 즉 저장할 것으로 예상하는 원소 수와 거짓 일치를 얼마나 자주 허용할 수 있는가이며, 여기서 최적의 비트 배열 크기와 해시 함수 개수가 곧바로 따라 나옵니다.

공식

예상 원소 수 $n$과 목표 오탐률 $p$에 대해, 메모리를 최소화하는 비트 배열의 길이는 다음과 같습니다.

그러면 최적 해시 함수 개수는

를 가장 가까운 정수로 반올림한 값입니다. 여기서 $m$은 비트 수, $k$는 각 원소에 적용하는 독립 해시 함수의 수이며 $\ln 2 \approx 0.693$입니다. $p$는 1보다 작은 확률이므로 자연로그가 음수이고, 따라서 두 공식 모두 양수 값을 냅니다.

계산 예. 백만 원소($n = 1{,}000{,}000$)를 목표 1%($p = 0.01$)로 다루는 필터:

따라서 백만 원소를 1%로 다루려면 약 1.14 MiB의 메모리와 일곱 개의 해시 함수가 필요하며, 이는 원소당 약 9.6비트에 해당합니다. 이 값은 그 정확도에서 원소 수와 무관하게 일정합니다.

원소당 비트 수와 정확도 사다리

크기 공식이 $n$에 대해 선형이므로, 원소당 저장 비용 $m / n = -\ln p / (\ln 2)^2$는 목표 비율에만 좌우됩니다. 덕분에 정확도 예산을 비교하는 깔끔한 척도가 됩니다.

오탐률이 10분의 1로 떨어질 때마다 원소당 약 4.8비트와 대략 세 개의 해시 함수가 더해집니다. 메모리는 선형으로만 늘지만 오류율은 기하급수적으로 줄어드는데, 바로 이 점이 블룸 필터의 매력입니다.

해시 개수가 중요한 이유

배열 크기를 고정하면, 해시 함수가 너무 적으면 비트가 성겨 우연히 일치하기 쉽고, 너무 많으면 배열이 빽빽하게 채워져 거의 모든 비트가 세워집니다. 최적점은 비트의 절반을 세우며 $k = (m/n)\ln 2$에 놓입니다. $k$는 정수여야 하므로 계산기가 반올림하고, 실제 오탐률은 그 반올림 값으로부터 다시 계산합니다.

위 예에서 반올림한 $k = 7$은 약 1.004%를 내는데, 이상적인 $k$가 정수가 아닌 6.64였기 때문에 1% 목표를 아주 조금 웃돕니다.

블룸 필터가 할 수 있는 것과 없는 것

블룸 필터는 결코 거짓 음성을 내지 않습니다. 어떤 원소가 없다고 말하면 실제로 없는 것입니다. 유일한 오류는 오탐이며, 이 계산기는 그 비율의 크기를 정합니다. 표준 필터는 삽입과 조회를 지원하지만 삭제는 지원하지 않는데, 비트가 원소들 사이에서 공유되기 때문입니다. 한 원소의 비트를 지우면 다른 원소가 손상될 수 있습니다. 삭제가 필요하면 계수형 블룸 필터가 각 비트를 작은 카운터로 대체하지만 메모리가 몇 배로 늘고, 쿠쿠 필터는 비슷한 크기로 삭제를 제공합니다.

한 가지 유의점이 있습니다. 필터는 고정된 $n$에 맞춰 크기가 정해집니다. 계획보다 훨씬 많은 원소를 삽입하면 배열이 포화되어 오탐률이 목표를 넘어섭니다. 성장이 예상된다면 처음부터 더 큰 수로 크기를 정하거나, 여러 필터를 연결하는 확장형 설계를 사용하세요.

실무에서의 반올림

공식에서 나온 비트 수 $m$이 딱 떨어지는 수인 경우는 드뭅니다. 실제 구현은 정수 개의 머신 워드나 메모리 페이지를 할당하므로 $m$을 올림하며, 그 결과 달성된 오탐률이 목표보다 약간 낮아집니다. 작은 보너스인 셈입니다. 여기 표시된 크기는 그 반올림 이전의 이론적 최솟값입니다.

관련 계산

블룸 필터는 해싱에 기대므로 두 원소가 같은 해시를 공유할 확률은 동일한 생일 수학의 지배를 받습니다. 해시 충돌 확률 계산를 참고하세요. 고정 길이 식별자에 대해서는 UUID 충돌 확률 계산기가 같은 논리를 UUID에 적용하고, 섀넌 엔트로피 계산는 데이터 집합이 담은 정보량을 측정합니다.