📌읽고 나면 진짜 쉬워지는 자료 구조 - 13. 블룸 필터

공간을 적게 사용하면서 빠르게 포함 여부를 판단할 수 있는 확률적 자료 구조

🔖 13.1. 블룸 필터란?

정의

• 해시 테이블의 확장 개념으로, 특정 데이터가 존재하는지를 빠르게 판별하는 자료 구조

• 비트 배열(bit array)과 여러 개의 해시 함수(hash function)를 사용하여 데이터를 저장함

• 빠르지만 확률적 오류(위양성) 가 존재할 수 있음

특징

• 공간 효율적: 데이터를 직접 저장하지 않고, 비트만 변경하므로 메모리 사용량이 적음

• 빠른 검색: 해시 함수를 통해 O(1)에 가깝게 조회 가능

• 위음성(False Negative) 없음: 존재하는 데이터가 "없다"고 나오는 경우는 없음

🔖 13.2. 블룸 필터의 동작 원리

데이터 추가(Add)

• 입력값을 k개의 해시 함수로 변환하여, 해당 비트 위치를 1로 설정함

데이터 조회(Check)

• 입력값을 k개의 해시 함수로 변환하여, 해당 비트가 모두 1인지 확인

• 모든 비트가 1이면 "존재할 가능성이 있다"(실제로 존재하는지 확실하지 않음)

• 하나라도 0이면 "존재하지 않는다"(정확한 결과)

위양성(False Positive) 발생 가능

• 다른 요소가 같은 해시 값을 가질 경우, 존재하지 않는 데이터가 있다고 오판할 수 있음

🔖 13.3. 블룸 필터에서 중요한 요소들

위양성(False Positive)이 생기는 이유

• 블룸 필터는 데이터 자체를 저장하지 않고 비트 배열과 해시 함수만 사용하기 때문

• 비트 배열이 가득 차거나, 해시 함수 개수가 적절하지 않으면 충돌(collision)이 증가하면서 위양성이 증가함

위양성 줄이는 방법

1. 비트 배열 크기(m) 늘리기 → 더 많은 공간을 활용하면 충돌이 줄어듦

2. 적절한 해시 함수 개수(k) 사용 → 너무 많거나 적으면 오히려 성능이 나빠짐

3. 데이터 개수(n)에 맞는 최적의 설정 → 너무 많은 데이터를 넣으면 위양성 증가

최적의 해시 함수 개수 계산 공식

k = (m/n) * ln(2)

• m: 비트 배열 크기

• n: 삽입할 요소 개수

• k: 해시 함수 개수

🔖 13.4. 블룸 필터 vs. 해시 테이블

비교 항목	블룸 필터	해시 테이블
메모리 사용량	적음	많음
정확성	위양성이 있음	정확한 값 반환
삭제 가능 여부	삭제 불가능(기본적으로)	삭제 가능
속도	매우 빠름(O(1))	빠름(O(1), 충돌 시 O(n))
적용 예시	캐싱, 검색 최적화	키-값 저장, 데이터 조회

🔖 13.5. 블룸 필터의 활용 사례

• 검색 엔진: 자주 검색되는 키워드를 빠르게 필터링하여 검색 속도 향상

• 캐시 시스템: 데이터가 캐시에 있는지 여부를 판단해 불필요한 디스크 접근 방지

• 스팸 필터: 이메일 주소가 블랙리스트에 있는지 확인

• 네트워크 보안: 악성 사이트, IP 주소 필터링

🎯 블룸 필터의 핵심 정리

• 공간을 적게 사용하면서 빠르게 조회할 수 있는 자료 구조

• 위양성이 발생할 수 있으나, 위음성(false negative)은 없음

• 비트 배열 크기(m), 해시 함수 개수(k), 데이터 개수(n)를 최적화하면 성능 향상 가능

• 빠른 필터링이 필요한 시스템(검색 엔진, 캐시, 보안)에서 유용하게 사용됨