블룸 필터 계산기: 크기·해시 수·오탐률

블룸 필터는 '이걸 본 적 있나?'에 고정된 비트 수로 답하며, 가끔 거짓 양성이 있지만 거짓 음성은 없습니다. 동작은 비트 수 m, 해시 함수 수 k, 넣은 항목 수 n 세 값으로 정해지며, 이 계산기는 빠진 값을 구합니다. 목표 오탐률에서 n개를 담는 가장 작은 필터, 주어진 크기의 필터가 갖게 될 오탐률, 오탐률을 넘기 전까지 들어가는 항목 수입니다. 오탐률은 표준식 (1 − e^(−kn/m))^k이며 1e-300 같은 작은 목표에서도 정밀도를 유지하도록 계산합니다. 대부분의 계산기는 연속식 −n·ln p / ln²2로 크기를 정한 뒤 k를 정수로 반올림해 목표를 살짝 넘깁니다. 4,000개를 1e-7로 잡으면 134,191비트, 해시 23개, 실제 오탐률 1.0006e-7이 됩니다. 이 도구는 최적 정수 k로 실제 목표를 만족하는 가장 작은 m(여기서는 134,196비트)을 찾고, 통상적인 답이 모자라면 알려 줍니다. k를 비우면 최적 정수 값을 쓰고, 고정하면 구현의 해시 수가 치르는 비용을 볼 수 있습니다. 적재 표는 설계 용량을 넘어 채울 때 오탐률이 어떻게 오르는지 보여 줍니다. 1% 필터를 설계치의 두 배로 채우면 16%에 가까워집니다. 이 식은 독립적이고 균일한 해시 함수를 가정합니다. h1 + i·h2로 두 해시를 조합하는 방식(Kirsch–Mitzenmacher)은 실제로 충분히 가깝지만, 약한 해시나 상관된 키는 여기 수치보다 나쁩니다. 표시되는 메모리는 비트 배열만이며 특정 라이브러리의 부가 구조는 포함하지 않습니다. 카운팅·확장형 블룸 필터는 더 많이 필요합니다.