도구스개발

XOR 필터 크기·오탐률 계산기

키 개수와 지문 비트수(xor8·xor16)로 XOR 필터의 예상 메모리 크기와 오탐률을 계산합니다. 블룸 필터보다 작고 조회가 빠른 대안입니다.

비트

예상 필터 크기

1.17 MB

오탐률 약 0.3906%, 원소당 9.84비트

오탐률 (2⁻ʳ)0.3906%
원소당 비트수 (1.23r)9.84비트
전체 크기9,840,000비트 = 1.17 MB
원소 하나당 비트수는 키 개수와 무관하게 r로만 정해집니다. 지문 비트수를 1비트 늘릴 때마다 오탐률은 정확히 절반으로 줄고, 크기는 1.23비트만 늘어납니다.
XOR 필터는 3개의 해시 위치를 XOR로 합쳐 지문과 비교하는 구조라 블룸 필터보다 조회가 빠르지만, 한 번 지은 뒤 원소를 뺄 수 없는 정적 자료구조입니다. 원소 추가·삭제가 잦다면 카운팅 블룸 필터나 쿠쿠 필터를 검토하는 편이 낫습니다.

사용 방법

  1. 1xor8 또는 xor16 중 하나를 고르거나, 지문 비트수를 직접 입력합니다.
  2. 2저장할 키(원소) 개수를 입력합니다.
  3. 3오탐률과 예상 메모리 크기(비트·바이트)를 확인합니다.

자주 묻는 질문

블룸 필터는 여러 개의 비트를 세워 오탐률을 조절하지만, XOR 필터는 원소마다 r비트짜리 지문(fingerprint) 하나를 3개의 해시 위치에 XOR 관계로 저장합니다. 조회는 3개 위치를 XOR로 합쳐 지문과 비교하는 것뿐이라 블룸 필터보다 빠르고, 같은 오탐률 기준으로 더 적은 메모리를 씁니다.

원소 하나당 비트수 ≈ 1.23 × r(r은 지문 비트수)입니다. xor8(r=8)은 원소당 약 9.84비트, xor16(r=16)은 약 19.68비트를 씁니다. 여기에 저장할 키 개수를 곱하면 전체 필터 크기가 나옵니다.

오탐률 ≈ 2⁻ʳ입니다. xor8은 2⁻⁸ ≈ 0.39%, xor16은 2⁻¹⁶ ≈ 0.0015%입니다. r을 1비트 늘릴 때마다 오탐률이 정확히 절반으로 줄어듭니다.

아닙니다. XOR 필터는 한 번 지은 뒤 원소를 뺄 수 없는 정적(static) 자료구조입니다. 원소가 바뀌면 필터를 통째로 다시 지어야 합니다. 원소 추가·삭제가 잦다면 카운팅 블룸 필터나 쿠쿠 필터가 더 맞습니다.

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

알아두면 좋은 점

  • 오탐률 2⁻ʳ와 원소당 비트수 1.23r 공식은 FastFilter/xorfilter(GitHub) 공식 문서와 원 논문(Xor Filters: Faster and Smaller Than Bloom and Cuckoo Filters, arXiv 1912.08258, VLDB 2020)의 수치(xor8 <10비트·오탐률<0.4%, xor16 <20비트·오탐률<0.002%)와 일치하는 것을 WebSearch로 확인했습니다(2026-09-05).
  • r을 1비트 늘리면 오탐률이 정확히 절반이 되는 것, 전체 크기가 키 개수에 정비례하는 것을 테스트로 고정했습니다.
  • XOR 필터는 정적 자료구조라 원소를 뺄 수 없고, 아주 드물게 해시 시드를 바꿔 다시 지어야 하는 경우가 있어(peeling 실패) 실제 구현체는 1.23배의 여유 슬롯을 확보해 둡니다.

함께 보면 좋은 도구

블룸 필터원소 수와 목표 오탐률을 넣으면 필요한 비트 배열 크기와 해시 함수 개수를 계산합니다.쿠쿠 필터원소 수와 목표 오탐률에서 지문 비트 수와 필요한 메모리를 구하고 블룸 필터와 견줍니다.카운트민 스케치허용 오차 ε와 실패확률 δ를 넣으면 카운트-민 스케치의 폭·깊이와 메모리를 계산합니다.HyperLogLog정밀도 p에서 HyperLogLog의 레지스터 수·표준오차·메모리를 계산하고, 목표 오차에 필요한 p를 거꾸로 찾습니다.gitignore 판정.gitignore 규칙과 경로를 넣으면 그 파일이 무시되는지, 어느 줄이 마지막으로 이겼는지 알려줍니다.

마지막 검증: 2026년 9월 5일 · 결과는 참고용 추정치입니다.