블룸 필터 예제

블룸 필터는 집합에 요소가 있는지 빠르고 메모리 효율적으로 검사하는 확률적 자료구조이다.

블룸 필터는 요소가 반드시 없거나 있을 수 있음만 알려주며, 거짓 긍정이 발생할 수 있다.

기본 구조는 비트 벡터와 k개의 해시 함수를 사용하는 것이다.

요소를 추가할 때 해시 결과로 얻은 인덱스 비트를 1로 설정한다.

검사할 때 동일한 해시 함수로 비트가 모두 1인지 확인하며, 하나라도 0이면 요소가 없다고 단언할 수 있다.

해시 함수는 독립적이고 균등 분포를 만족해야 하며, 빠른 비암호화 해시 함수(murmur, xxHash, FNV 등)가 권장된다.

거짓 긍정율은 필터 크기(m), 해시 함수 수(k), 삽입 요소 수(n)에 따라 조정 가능하다.

최적의 해시 함수 수 k는 (m/n)ln(2) 공식으로 계산할 수 있다.

삽입 및 조회 연산은 모두 O(k) 시간 복잡도를 가진다.

필터 크기가 클수록 거짓 긍정율이 감소하며, 작을수록 증가한다.