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

=== 동작 원리 ===

==== 삽입 (Insert) ====

원소 x를 블룸 필터에 추가하려면:
# k개의 해시 함수 h₁, h₂, ..., hₖ 각각에 x를 입력한다.
# 각 해시 함수가 반환하는 인덱스 h₁(x), h₂(x), ..., hₖ(x)에 해당하는 비트를 모두 '''1'''로 설정한다.

<pre>
예시: m=10, k=3, 원소 "apple" 삽입
h1("apple") = 2  →  비트[2] = 1
h2("apple") = 5  →  비트[5] = 1
h3("apple") = 8  →  비트[8] = 1

인덱스: [0][1][2][3][4][5][6][7][8][9]
값:      [0][0][1][0][0][1][0][0][1][0]
</pre>

이어서 "banana"를 삽입하면:

<pre>
h1("banana") = 1  →  비트[1] = 1
h2("banana") = 5  →  비트[5] = 1  (이미 1)
h3("banana") = 7  →  비트[7] = 1

인덱스: [0][1][2][3][4][5][6][7][8][9]
값:      [0][1][1][0][0][1][0][1][1][0]
</pre>

==== 조회 (Query / Lookup) ====

원소 y가 집합에 있는지 확인하려면:
# k개의 해시 함수 각각에 y를 입력한다.
# h₁(y), h₂(y), ..., hₖ(y)에 해당하는 비트를 모두 확인한다.
# '''하나라도 0이면''' → "확실히 없다(Definitely Not)" 반환.
# '''모두 1이면''' → "아마도 있다(Possibly Yes)" 반환.

<pre>
"apple" 조회:
h1("apple") = 2  →  비트[2] = 1 ✓
h2("apple") = 5  →  비트[5] = 1 ✓
h3("apple") = 8  →  비트[8] = 1 ✓
→  결과: "아마도 있다" (실제로 삽입했으므로 정확)

"cherry" 조회 (삽입 안 함):
h1("cherry") = 1  →  비트[1] = 1 ✓
h2("cherry") = 5  →  비트[5] = 1 ✓
h3("cherry") = 9  →  비트[9] = 0 ✗
→  결과: "확실히 없다" (정확)

"grape" 조회 (삽입 안 함):
h1("grape") = 1  →  비트[1] = 1 ✓
h2("grape") = 5  →  비트[5] = 1 ✓
h3("grape") = 7  →  비트[7] = 1 ✓
→  결과: "아마도 있다" (거짓 긍정! 실제로는 없음)
</pre>

"grape"의 경우처럼, 우연히 다른 원소들에 의해 해당 비트들이 모두 1이 되어 있으면 '''거짓 긍정(False Positive)'''이 발생한다. 이것이 블룸 필터의 본질적인 한계이자, 공간을 아끼기 위해 치르는 대가다.

==== 삭제 불가 ====

기본 블룸 필터는 '''원소를 삭제할 수 없다'''. 만약 특정 원소에 해당하는 비트를 0으로 되돌리면, 같은 비트를 공유하던 다른 원소의 정보도 손상되기 때문이다. 예를 들어 위 예시에서 비트[5]는 "apple"과 "banana" 둘 다 사용하고 있는데, "apple"을 삭제하겠다고 비트[5]를 0으로 만들면 "banana"도 조회되지 않게 된다.

이 문제를 해결한 변형이 [[#카운팅 블룸 필터(Counting Bloom Filter)|카운팅 블룸 필터]]다.