I-6 Bloom filter — 0이면 확실히 없음, 모두 1이면 아마 있음
먼저 이 문제의 정체부터
Bloom filter는 집합에 어떤 원소가 들어 있는지 아주 적은 메모리로 검사하는 확률적 자료구조입니다. 정확한 원소 자체를 저장하지 않고 bit array와 여러 hash function으로 흔적만 남기므로 빠르고 작지만 false positive가 생길 수 있습니다.
표준 Bloom filter는 삭제를 하지 않는다고 가정합니다. 삽입된 원소가 설정한 비트는 그대로 1로 남으므로 false negative는 없습니다. 반면 다른 원소들이 우연히 같은 위치들을 모두 1로 만들 수 있어 실제로 없는데 있다고 답하는 false positive는 가능합니다.
가장 강력한 기억 문장은 '조회한 위치 중 0이 하나라도 있으면 확실히 없음; 모두 1이면 아마 있음'입니다. 확실히와 아마의 비대칭이 네 선택지 판정을 모두 해결합니다.
0. 필요한 개념을 처음부터 배우기
개념 1 · 왜 Bloom filter를 쓰는가
정확한 set은 모든 key를 저장해야 하지만 Bloom filter는 m개의 bit만 저장합니다. 원소 x를 k개의 hash function에 넣어 k개 위치를 얻고 그 비트들을 1로 설정합니다.
메모리를 아끼는 대가로 서로 다른 key가 같은 bit를 공유할 수 있습니다. Bloom filter는 '정확한 저장소'보다 '비싼 다음 검사를 건너뛸 수 있는 빠른 사전 필터'로 이해하면 좋습니다.
수식으로 정확히 쓰기
핵심 규칙비트 배열 B[0..m-1], 처음에는 모두 0
핵심 규칙k개의 해시 함수 h1,...,hk
이 절에서 꼭 기억할 것
- 원소 자체를 저장하지 않는다.
- 공간 절약과 오류 가능성은 맞교환 관계다.
개념 2 · 삽입 연산
insert(x)는 h1(x),...,hk(x)를 계산하고 해당 bit를 모두 1로 만듭니다. 이미 1인 bit를 다시 1로 만들어도 문제없습니다.
중요한 불변식은 표준형에서 bit를 1에서 0으로 되돌리지 않는다는 것입니다. 따라서 x를 삽입한 뒤 x가 조회할 모든 위치는 계속 1입니다.
수식으로 정확히 쓰기
i=1..k 각각에 대해 B[hi(x)]=1핵심 규칙비트는 \(0\to 1\)0→1방향으로만 바뀜
이 절에서 꼭 기억할 것
- 충돌은 허용된다.
- 표준형에는 안전한 개별 삭제가 없다.
개념 3 · 조회 연산
query(x)는 같은 k개 위치를 검사합니다. 하나라도 0이면 x가 삽입된 적이 있을 수 없습니다. 삽입되었다면 그 위치를 1로 만들었어야 하기 때문입니다.
모든 위치가 1이면 x가 직접 만든 흔적일 수도 있고 다른 key들이 합쳐 만든 흔적일 수도 있습니다. 그래서 결과는 '확실히 없음(definitely not present)' 또는 '있을 가능성(possibly present)' 두 종류입니다.
수식으로 정확히 쓰기
∃i
B[hi(x)]=0 ⇒ 확실히 없음∀i
B[hi(x)]=1 ⇒ 있을 가능성이 절에서 꼭 기억할 것
- 0은 확정 부재 증거
- 모든 1은 존재 증명이 아니다.
개념 4 · false positive와 false negative
False positive는 실제로 없는 원소를 있다고 답하는 오류입니다. Bloom filter에서는 다른 원소들의 hash collision 때문에 x의 모든 조회 bit가 1이 될 수 있어 가능합니다.
False negative는 실제로 삽입된 원소를 없다고 답하는 오류입니다. 삭제 없는 표준형에서는 삽입 시 설정한 bit가 지워지지 않으므로 발생하지 않습니다.
수식으로 정확히 쓰기
핵심 규칙거짓 양성(FP): x∉S이지만 \(\text{query}(x)=\)query(x)=있을 가능성
핵심 규칙거짓 음성(FN): \(x\in S\)x∈S이지만 \(\text{query}(x)=\)query(x)=없음
이 절에서 꼭 기억할 것
- positive/negative는 시스템의 답
- false는 그 답이 현실과 다름
개념 5 · 충돌로 false positive 만들기
가장 작은 예로 \(m=2, k=1\)m=2, k=1을 생각합니다. 삽입한 a와 삽입하지 않은 x가 둘 다 bit 0으로 hash되면 a를 넣은 뒤 \(B[0]=1\)B[0]=1입니다. x를 조회해도 bit 0이 1이므로 'possibly present'라고 답해 false positive가 됩니다.
k가 여러 개여도 원리는 같습니다. x의 모든 hash 위치가 다른 삽입 원소들에 의해 1이 되면 됩니다. 충돌 가능성을 0으로 만들지는 못하고 m과 k를 조절해 확률을 낮춥니다.
수식으로 정확히 쓰기
m=2,k=1,h(a)=h(x)=0insert(a) 후 query(x) ⇒ 거짓 양성이 절에서 꼭 기억할 것
- 구체적 반례로 FP 가능성을 보일 수 있다.
- false positive는 확률적이지 불가능한 사건이 아니다.
개념 6 · 전제에서 벗어나는 변형
Counting Bloom filter는 각 위치에 bit 대신 counter를 두어 삭제를 지원할 수 있습니다. 잘못된 삭제, counter overflow, 구현 오류까지 허용하면 표준형과 다른 오류 논의가 생깁니다.
시험 문항이 단순히 Bloomfilter 검색을 묻고 강의의 표준 삽입/조회 모델을 전제로 하면 삭제 없는 표준형으로 판정합니다. 조건이 추가되면 그 조건을 먼저 표시해야 합니다.
수식으로 정확히 쓰기
핵심 규칙표준 블룸 필터: 비트 배열, 삭제 없음
핵심 규칙계수형 블룸 필터: 카운터, 삭제 지원 변형
이 절에서 꼭 기억할 것
- 전제를 먼저 고정한다.
- 이 문항의 정답 B는 표준형 전제에서 성립한다.
1. 시험장에서 따라 할 풀이 순서
표준 블룸 필터 · 삭제 없음
x∈S ⇒ all queried bits remain 1
0 하나 ⇒ 확실히 없음
모두 1 ⇒ 있을 가능성
표준형 전제를 확인한다
삭제 없는 bit-array Bloom filter로 읽습니다.
핵심 규칙표준 블룸 필터 · 삭제 없음
삽입 불변식을 적는다
삽입된 x의 k개 위치는 모두 1이 되고 지워지지 않습니다.
핵심 규칙x∈S ⇒ all queried bits remain 1
0을 만난 경우를 판정한다
조회 위치 중 0 하나면 x는 삽입되지 않았다고 확정합니다.
핵심 규칙0 하나 ⇒ 확실히 없음
모두 1인 경우를 판정한다
다른 key가 비트를 만들었을 수 있으므로 존재 가능성만 말합니다.
핵심 규칙모두 1 ⇒ 있을 가능성
오류 방향을 번역한다
없는 것을 있다고 하는 false positive는 가능하고, 있는 것을 없다고 하는 false negative는 불가능합니다.
핵심 규칙거짓 양성 가능 · 거짓 음성 불가능
A·C를 FN 때문에 제거한다
둘 다 false negative 가능성을 주장하므로 표준형에서 거짓입니다.
\[A=거짓, C=거짓\]A=거짓, C=거짓D를 충돌 반례로 제거한다
\(m=2,k=1\)
m=2,k=1에서 다른 key가 같은 bit로 hash되면 false positive가 생깁니다.\[D=거짓\]D=거짓유일한 선택지를 고른다
오직 false positive만 가능하다는 B가 참입니다.
핵심 규칙정답 B
2. 이 문제를 실제로 끝까지 풀기
Bloom filter의 bit array는 처음 모두 0입니다. x를 삽입하면 k개 hash 위치를 모두 1로 설정합니다. 표준형에서는 그 비트를 다시 0으로 지우지 않습니다.
따라서 실제로 삽입된 x를 조회하면 필요한 모든 위치가 반드시 1입니다. query가 0을 하나 발견해 absent라고 답하는 false negative는 생길 수 없습니다.
하지만 삽입하지 않은 y도 조회 위치가 우연히 모두 1일 수 있습니다. 각 1은 y가 아니라 다른 삽입 원소들이 만든 것일 수 있기 때문입니다. 이때 Bloom filter는 possibly present라고 답하므로 false positive가 됩니다.
A는 false negative만 가능하다고 하므로 방향이 반대입니다. C는 두 오류가 모두 가능하다고 하지만 false negative 부분 때문에 틀립니다. D는 오류가 전혀 없다고 하지만 collision으로 false positive가 가능하므로 틀립니다.
결국 B만 참입니다. 답을 기억하는 가장 짧은 방법은 '0 하나=확실히 없음, 전부 \(1=\)1=아마 있음'입니다. '아마'가 필요한 이유가 바로 false positive입니다.
3. 선택지 A–D를 한 줄도 건너뛰지 않고 판정하기
-
A거짓
삭제 없는 표준형에서는 삽입된 key의 비트가 모두 남으므로 false negative가 없습니다. 가능한 오류 방향을 반대로 적었습니다.
빠른 확인법: insert(x) 직후 x의 모든 hash bit는 1입니다.
-
B참 — 정답 후보
다른 원소들의 collision이 조회 위치를 모두 1로 만들 수 있어 false positive는 가능하지만 false negative는 없습니다.
빠른 확인법: 모두 1은 'possibly', 0 하나는 'definitely not'입니다.
-
C거짓
false positive 부분은 맞지만 false negative도 가능하다는 절반이 틀려 전체 선택지는 거짓입니다.
빠른 확인법: 표준형에서 \(1\to 0\)
1→0변화가 없다는 불변식을 확인하세요. -
D거짓
Bloom filter는 정확한 set가 아니므로 hash collision 때문에 false positive가 가능합니다.
빠른 확인법: \(m=2,k=1\)
m=2,k=1에서 \(h(a)=h(x)=0\)h(a)=h(x)=0인 반례를 만드세요.
4. 초보자가 가장 자주 틀리는 이유
- positive를 '실제로 존재함'으로 읽는다. positive는 자료구조의 답입니다.
- 0 하나와 모두 1의 확실성 수준을 반대로 외운다.
- hash collision이 있어도 오류가 없다고 생각한다.
- 삽입된 원소의 bit를 다른 원소가 공유하면 그 비트가 사라진다고 생각한다.
- 표준형과 counting Bloom filter의 삭제 모델을 섞는다.
- false positive와 hash function collision을 같은 문장으로만 외우고 구체적 bit 반례를 만들지 못한다.
- C처럼 절반만 맞는 결합 명제를 참으로 고른다.
5. 시험 답안 템플릿
표준 Bloom filter에서 insert(x)는 모든 \(h_{i}(x)\)hᵢ(x)위치를 1로 만들고 삭제가 없으므로 \(x\in S\)x∈S이면 조회 위치가 모두 1이다. 따라서 false negative는 없다. 반면 x∉S여도 다른 key들의 collision으로 모든 \(h_{i}(x)\)hᵢ(x)위치가 1일 수 있어 false positive는 가능하다. 그러므로 정답은 B이다.
6. 스스로 이해했는지 확인
조회 위치 중 0이 하나 있으면 무엇을 결론 내리는가?
정답: 그 원소는 확실히 삽입되지 않았습니다.
조회 위치가 모두 1이면 무엇을 결론 내리는가?
정답: 아마 존재할 수 있지만 확정할 수 없습니다.
실제로 없는데 있다고 답하는 오류는?
정답: False positive입니다.
실제로 있는데 없다고 답하는 오류는?
정답: False negative입니다.
표준 Bloom filter에서 불가능한 오류는?
정답: False negative입니다.
I-6의 정답은?
정답: B, only false positives입니다.
근거 자료
AuD Gedächtnisprotokoll SoSe 2025.md· Multiple Choice I.6
복기된 문제 문언과 선택지Vorlesung\05RandomizedDataStructures-wi.pdf· pp. 35-45
Bloom filter 삽입·검색과 false-positive 성질Übung\AuD26_Sheet08-Sol.pdf· pp. 10-12
Bloom filter 공식 연습 해설