블룸 필터 시각화
확률적 자료구조인 블룸 필터의 삽입·검색과 거짓 양성(false positive)을 시각적으로 이해하세요
자료구조★★☆
삽입된 원소: 0채움률: 0.0%거짓 양성률: 0.00%
설정된 비트 빈 비트 해시 대상 검색
블룸 필터에 원소를 삽입하고 검색하는 과정을 관찰하세요.
값을 삽입하거나 검색하세요
블룸 필터란?
k개의 해시 함수와 m비트 배열로 원소의 존재 여부를 빠르게 검사하는 확률적 자료구조입니다. 거짓 양성(false positive)은 가능하지만 거짓 음성(false negative)은 절대 없습니다.
사용 방법
- 1비트 배열 크기와 해시 함수 수를 설정하세요
- 2값을 삽입하면 k개의 해시 위치가 1로 설정됩니다
- 3값을 검색하면 해당 위치가 모두 1인지 확인합니다
- 4채움률이 올라가면 거짓 양성률 변화를 관찰하세요
동작 원리
- 1삽입: 원소를 k개의 해시 함수에 통과시켜 k개의 비트 위치를 1로 설정
- 2검색: k개의 비트 위치가 모두 1이면 '있을 수 있음', 하나라도 0이면 '확실히 없음'
- 3거짓 양성: 다른 원소들이 설정한 비트가 우연히 겹쳐 '있음'으로 판정되는 경우
- 4최적 해시 함수 수: k = (m/n) × ln(2), m=비트 수, n=원소 수
실무 활용
- •Chrome의 악성 URL 사전 필터링 (Safe Browsing)
- •Cassandra/HBase의 SSTable 존재 여부 확인으로 불필요한 디스크 I/O 방지
- •Medium의 추천 시스템에서 이미 본 글 필터링
- •비트코인 SPV 노드의 트랜잭션 필터링
비슷한 알고리즘
- •해시테이블 — 정확하지만 메모리 사용량이 블룸 필터의 수십 배
- •카운팅 블룸 필터 — 삭제도 지원하지만 메모리 3~4배 필요
- •쿠쿠 필터 — 삭제 지원 + 더 나은 공간 효율성, 최근 대안
학습 팁
- •적은 원소를 넣고 검색하여 거짓 양성이 발생하지 않음을 확인하세요
- •원소를 많이 넣어 채움률을 높인 후 거짓 양성을 직접 경험해보세요
- •해시 함수 수를 바꿔가며 최적값을 찾아보세요
자주 묻는 질문
Q. 삭제가 되나요?
A. 기본 블룸 필터는 삭제 불가합니다. 카운팅 블룸 필터를 사용하면 가능합니다.
Q. 거짓 음성은?
A. 절대 발생하지 않습니다. 삽입한 원소는 반드시 '있음'으로 판정됩니다.