블룸 필터(Bloom Filter)는 어떤 요소가 집합(set)에 존재하는지 여부를 빠르고 메모리 효율적으로 판별할 수 있도록 설계된 자료구조입니다.
블룸 필터의 기본 개념
블룸 필터는 확률적 자료구조(probabilistic data structure)에 속합니다. 이 자료구조를 활용하면 특정 요소가 집합에 속해 있는지, 혹은 속해 있지 않은지를 판별할 수 있습니다. 다만 확률적 자료구조의 특성상 '반드시 없다'는 보장은 가능하지만, '있다'고 판정될 때는 아주 낮은 확률로 오탐(false positive)이 발생할 수 있다는 점을 기억해야 합니다.
기반 자료구조: 비트 벡터(Bit Vector)
블룸 필터는 비트 벡터(bit vector)를 기반 자료구조로 사용합니다. 아래는 설명을 위해 준비한 작은 비트 벡터의 예입니다.
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
표의 각 빈 칸은 하나의 비트를 의미하며, 그 아래의 숫자는 해당 비트의 인덱스(위치)를 나타냅니다. 블룸 필터에 새로운 요소를 추가할 때는 그 요소를 여러 번 해싱한 뒤, 해시 값에 해당하는 위치의 비트들을 1로 설정하면 됩니다.
블룸 필터의 두 가지 핵심 동작
블룸 필터는 크게 두 가지 동작을 지원합니다. 첫째는 객체를 추가하고 그 존재를 기록하는 것이고, 둘째는 특정 객체가 이전에 등록된 적이 있는지 확인하는 것입니다.
1. 객체 추가하기
- 추가하려는 객체에 대해 해시 값을 계산합니다.
- 계산된 해시 값을 이용해 블룸 필터 상태에서 해당 비트들을 설정합니다. 이때 해시 값이 곧 설정할 비트의 위치(인덱스)가 됩니다.
2. 객체 존재 여부 확인하기
- 확인하려는 객체에 대해 해시 값을 계산합니다.
- 해시 값들이 가리키는 인덱스의 비트들이 블룸 필터 상태에서 모두 1로 설정되어 있는지 검사합니다.
주의할 점
중요한 것은 객체의 해시 값 자체가 블룸 필터 상태에 직접 저장되는 것이 아니라는 점입니다. 각 해시 함수는 단순히 어떤 비트를 설정하거나 검사할지 결정하는 역할만 수행합니다. 예를 들어 해시 함수를 하나만 사용한다면, 단 하나의 비트만 설정되거나 검사됩니다. 해시 함수의 개수가 많아질수록 오탐 확률은 낮아지지만, 그만큼 더 많은 비트가 소모된다는 트레이드오프도 함께 고려해야 합니다.