쿠쿠 필터 크기 계산기

삭제가 됩니다. 블룸 필터는 여러 원소가 같은 비트를 공유해서 비트를 0으로 되돌리면 다른 원소까지 지워지지만, 쿠쿠 필터는 원소마다 지문 한 덩어리가 통째로 들어 있어 그 덩어리만 빼면 됩니다. 이것이 이 자료구조의 존재 이유입니다.

f ≈ ⌈log₂(2b/ε)⌉입니다. b는 버킷당 칸 수, ε은 목표 오탐률입니다. 오탐은 찾는 지문과 같은 지문이 두 버킷 2b칸 어딘가에 우연히 들어 있는 경우이고, 지문이 f비트면 한 칸이 우연히 맞을 확률이 2^−f이므로 ε ≈ 2b/2^f가 됩니다. b=4에 ε=1%면 10비트입니다.

어느 선 이상 채우면 삽입이 실패한다는 뜻입니다. 넣을 자리가 둘 다 차 있으면 기존 지문을 쫓아내 그 지문의 다른 자리로 미는데, 이 밀어내기가 끝없이 이어질 수 있어 시도 횟수에 상한을 둡니다. 그 상한에 걸리면 넣지 못합니다. 버킷당 칸이 1개면 약 50%, 2개면 84%, 4개면 95%, 8개면 98%까지 찹니다.

아닙니다. 블룸 필터는 아무리 넣어도 삽입이 실패하지 않고 오탐률만 서서히 나빠집니다. 쿠쿠 필터는 어느 선을 넘으면 아예 넣지 못하므로, 담을 원소 수를 미리 알고 칸을 넉넉히 잡아야 합니다. 그 여유분이 곧 메모리 낭비이며, 이 계산기가 원소 수를 적재율로 나눠 칸 수를 잡는 이유입니다.

오탐률이 아주 낮을 때입니다. 블룸은 원소당 1.44·log₂(1/ε)비트가 들고 쿠쿠는 (log₂(2b)+log₂(1/ε))/α비트가 드는데, ε이 작아질수록 계수 1.44와 1/α ≈ 1.05의 차이가 상수항 log₂(2b)를 이깁니다. b=4일 때 교차점이 대략 0.08% 언저리이고, b=1은 적재율이 50%밖에 안 되어 어떤 오탐률에서도 블룸을 이기지 못합니다.

두 번째 자리를 「첫 자리 XOR 지문해시」로 구하기 때문입니다. 이 XOR 결과가 버킷 범위 안에 떨어지려면 버킷 수가 2의 거듭제곱이어야 합니다. 그래서 실제로 잡는 칸 수는 계산값을 2의 거듭제곱으로 올린 값이고, 원소 수가 어디에 걸리느냐에 따라 이 올림이 거의 두 배까지 됩니다. 이 계산기는 이론 크기와 실제 할당을 따로 냅니다.

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