카운팅 블룸 필터 계산기

표준 블룸 필터는 슬롯마다 비트 1개를 쓰지만, 카운팅 블룸 필터는 작은 카운터를 씁니다. 삽입 시 +1, 삭제 시 −1 하고 조회는 카운터가 0보다 큰지만 봐서, 표준 블룸 필터가 못 하는 삭제를 지원합니다.

완전히 같습니다. 슬롯 수(m)와 최적 해시 개수(k), 오탐률 공식은 표준 블룸 필터와 동일하고, 카운팅 블룸 필터는 그 슬롯 하나하나를 몇 비트짜리 카운터로 바꿀지만 추가로 정합니다.

최적 해시 개수를 쓰면 슬롯 하나가 받는 해시 횟수의 기댓값이 오탐률·원소 수와 무관하게 항상 ln2(약 0.693)로 고정됩니다. 이를 푸아송분포로 근사하면 4비트 카운터(최댓값 15)가 넘칠 확률은 약 10⁻¹⁵ 수준으로 극히 작습니다.

카운터가 표현할 수 있는 최댓값을 넘으면 그 이상 세지 못해 실제보다 적게 세게 됩니다. 확률이 매우 낮긴 하지만, 안전을 더 원하면 카운터 폭을 8비트로 늘리면 오버플로 확률이 기하급수적으로 더 작아집니다.

슬롯 수는 같고 슬롯마다 카운터 폭만큼 비트가 곱해지므로, 전체 메모리는 표준 블룸 필터의 정확히 "카운터 폭"배입니다. 4비트 카운터면 4배입니다.

전송되지 않습니다. 모든 계산은 브라우저 안에서 이뤄지고, 입력값은 이 기기에만 남습니다.