블룸 필터 편집하기 (부분)

== 관련 자료구조와 비교 ==

=== 블룸 필터 vs 해시 테이블 ===

{| class="wikitable"
|-
! 항목 !! 블룸 필터 !! 해시 테이블
|-
| 목적 || 멤버십 테스트만 || 저장 + 조회 + 수정
|-
| 공간 || 매우 작음 || 큼 (실제 데이터 저장)
|-
| 정확도 || 거짓 긍정 가능 || 완전 정확
|-
| 원소 열거 || 불가 || 가능
|-
| 삭제 || 기본형 불가 || 가능
|-
| 원소 복원 || 불가 || 가능
|}

=== 블룸 필터 vs Count-Min Sketch ===

[[Count-Min Sketch]]는 블룸 필터와 비슷한 개념의 확률적 자료구조로, 원소의 '''빈도수(frequency)'''를 근사 추정한다.

{| class="wikitable"
|-
! 항목 !! 블룸 필터 !! Count-Min Sketch
|-
| 질문 유형 || "있냐 없냐" (멤버십) || "몇 번 나왔냐" (빈도)
|-
| 오류 유형 || 거짓 긍정 (과대 추정) || 빈도 과대 추정
|-
| 공간 || O(m) 비트 || O(d × w) 정수
|-
| 주요 용도 || 집합 멤버십 || 스트림 빈도 추정
|}

=== 블룸 필터 vs HyperLogLog ===

[[HyperLogLog]]는 집합의 '''원소 개수(cardinality)'''를 근사 추정하는 자료구조다. 블룸 필터가 "이 원소가 집합에 있는가?"를 묻는다면, HyperLogLog는 "이 집합에 몇 개의 원소가 있는가?"를 묻는다.

=== 블룸 필터 vs MinHash ===

[[MinHash]](=MinWise Hashing)는 두 집합의 자카드 유사도(Jaccard Similarity)를 추정하는 자료구조다. LSH(Locality-Sensitive Hashing)의 기반이 된다. 블룸 필터와는 목적이 다르다.