쿼션트 필터 크기·오탐률 계산기
키 개수·나머지 비트수·목표 적재율로 쿼션트 필터의 슬롯 개수와 오탐률, 예상 메모리 크기를 계산합니다.
비트
관용적으로 0.8 안팎을 권장합니다
예상 메모리 크기
2.75 MB
슬롯 2,097,152개
몫(quotient) 비트수 q21비트
슬롯 개수 (2^q)2,097,152개
실제 적재율47.7%
오탐률 (≈2⁻ʳ)0.3906%
슬롯당 비트수11비트 (나머지 8 + 메타 3)
전체 크기2.75 MB
슬롯 하나당 비트수는 나머지(remainder) r비트에 메타비트 3개(is_occupied·is_continuation· is_shifted)를 더한 값입니다. 블룸 필터와 달리 이 메타비트 덕분에 원소를 삭제해도 연쇄가 끊기지 않습니다.
적재율이 높을수록 몫이 충돌하는 연쇄가 길어져 조회·삽입이 느려집니다. 실제 슬롯 개수는 목표 적재율을 만족하도록 2의 거듭제곱으로 올림해 정하므로, 실제 적재율은 목표보다 같거나 낮게 나옵니다.
사용 방법
- 1저장할 키(원소) 개수를 입력합니다.
- 2나머지(remainder) 비트수를 입력합니다 — 오탐률을 결정합니다.
- 3목표 적재율(관용적으로 0.8 안팎)을 입력합니다.
- 4필요한 슬롯 개수와 오탐률, 예상 메모리 크기를 확인합니다.
자주 묻는 질문
원소의 해시값을 몫(quotient)과 나머지(remainder)로 나눠, 몫을 슬롯 인덱스로 쓰고 나머지만 그 슬롯에 저장하는 확률적 멤버십 자료구조입니다. 블룸 필터와 달리 원소 삭제를 지원합니다.
블룸 필터는 비트만 세워 삭제를 지원하지 않지만, 쿼션트 필터는 슬롯마다 메타비트 3개(is_occupied·is_continuation·is_shifted)를 더 둬 삭제해도 연쇄가 끊기지 않게 관리합니다.
오탐률은 ε ≈ 2⁻ʳ(r은 나머지 비트수)로 결정됩니다. 슬롯 하나당 비트수는 r+3(메타비트)이고, 슬롯 개수는 목표 적재율을 만족하도록 2의 거듭제곱으로 올림해 정합니다.
쿼션트 필터는 열린 주소법 해시 테이블과 비슷하게 작동해, 적재율이 높을수록 몫이 충돌하는 연쇄가 길어져 조회·삽입이 느려집니다. 그래서 적재율 100%에 가깝게 채우지 않고 80% 안팎에서 운용하는 것이 관용적입니다.
알아두면 좋은 점
- Bender 외(2012) "Don't Thrash: How to Cache Your Hash" 원 논문과 System Design 자료를 WebSearch로 교차 확인했습니다(2026-09-05). 메타비트 3개 구성과 오탐률 ε≈2⁻ʳ 공식이 일치합니다.
- 실제 슬롯 개수는 필요한 슬롯 수(키 개수÷목표 적재율)를 2의 거듭제곱으로 올림해 정하므로, 실제 적재율은 목표보다 같거나 낮게 나옵니다.
- 실제 구현체(해시 함수 선택, 연쇄 이동 비용 등)에 따라 성능은 달라질 수 있습니다. 이 계산기는 이론적인 크기와 오탐률만 다룹니다.
함께 보면 좋은 도구
블룸 필터원소 수와 목표 오탐률을 넣으면 필요한 비트 배열 크기와 해시 함수 개수를 계산합니다.쿠쿠 필터원소 수와 목표 오탐률에서 지문 비트 수와 필요한 메모리를 구하고 블룸 필터와 견줍니다.XOR 필터 크기키 개수와 지문 비트수(xor8·xor16)로 XOR 필터의 예상 메모리 크기와 오탐률을 계산합니다.gitignore 판정.gitignore 규칙과 경로를 넣으면 그 파일이 무시되는지, 어느 줄이 마지막으로 이겼는지 알려줍니다.울프람 규칙규칙 번호 0~255를 8비트로 풀어 세 칸 이웃에 대응시키고 세대를 쌓아 무늬를 그립니다.
마지막 검증: 2026년 9월 5일 · 결과는 참고용 추정치입니다.