쿠쿠 해싱과 지문 필터

원소마다 자리를 두 개씩 주는 설계 하나로 최악 O(1) 조회와 삭제 지원이 동시에 따라옵니다.

두 자리만 확인하면 끝나는 조회

체이닝 해시 테이블은 조회 비용이 버킷에 매달린 원소 수에 비례합니다. 쿠쿠 해싱은 그 상한을 상수로 못박습니다. 해시 함수 h1, h2와 배열 T1, T2를 두고, 키 k는 T1[h1(k)]와 T2[h2(k)] 중 정확히 한 곳에만 존재하게 합니다. 조회가 슬롯 두 개만 읽으면 되므로 최악의 경우에도 O(1)입니다.

대가는 삽입 쪽에 몰려 있습니다. 넣으려는 자리가 이미 차 있으면 기존 키를 추방(evict)하고 그 자리를 차지합니다. 추방된 키는 자신의 대체 슬롯으로 이동하고, 거기도 차 있으면 그 자리의 키를 다시 추방합니다. 뻐꾸기가 남의 둥지에서 알을 밀어내는 습성에서 이름이 왔습니다.

삽입 A -> T1[h1(A)] 에 B 가 있음   => A 가 B 를 밀어냄
        B -> T2[h2(B)] 에 C 가 있음   => B 가 C 를 밀어냄
          C -> T1[h1(C)] 비어 있음     => 체인 종료

이 체인이 순환을 그리면 삽입이 끝나지 않습니다. 그래서 구현은 최대 이동 횟수(MaxLoop)를 두고, 초과하면 새 해시 함수 쌍으로 전체를 재삽입(rehash)합니다. 순환에 빠질 확률은 부하율(load factor)이 낮을수록 지수적으로 줄어듭니다. 슬롯이 하나뿐인 표준 구성에서 부하율 임계값은 약 50%이고, 그 근처에서 삽입 기댓값은 O(n)에 접근합니다.

해시 함수를 늘리면 생기는 여유

해시 함수를 d개(d ≥ 3)로 늘리면 후보 자리가 d개가 되어 임계값이 크게 올라갑니다. 다만 그 구간에서 삽입 비용이 상수로 유지되는지는 오래 열려 있던 문제였습니다. 2024년 FOCS에 발표된 연구(arXiv:2401.14394)가 임계값 미만의 부하율에서 랜덤 워크 방식 d-ary 쿠쿠 해싱의 삽입 기댓값이 O(1)임을 증명했습니다.

그런데 실제 시스템은 여전히 d=2를 씁니다. 이유는 캐시에 있습니다. 조회 한 번에 확인할 슬롯이 d개로 늘어나고, 그 위치들은 서로 인접하지 않습니다. d=2는 캐시 라인 두 개만 읽으면 되지만 d=4는 비인접 메모리 네 곳을 참조합니다. 임계값 분석이 2024년에야 이론적으로 정리됐다는 점도 채택을 늦춘 요인입니다.

지문만 남기고 키를 버리는 방법

쿠쿠 필터는 같은 킥아웃 구조를 쓰되 원본 키 대신 k비트 지문(fingerprint)만 저장합니다. 여기서 문제가 하나 생깁니다. 추방된 원소를 대체 자리로 옮기려면 그 원소의 두 번째 해시값이 필요한데, 원본 키를 버렸으니 다시 해싱할 수 없습니다.

부분 키 쿠쿠 해싱(partial-key cuckoo hashing)이 이 문제를 XOR의 대칭성으로 풉니다. 두 후보 버킷을 아래 관계로 묶습니다.

b1 = hash(x) mod B
b2 = b1 XOR hash(fingerprint(x)) mod B
 
b2 XOR hash(f) = b1      XOR 을 두 번 적용하면 원래 값으로 돌아온다

지문 f와 현재 버킷 번호만 있으면 상대 버킷이 바로 나옵니다. 원본 키를 보관하지 않고도 킥아웃 체인을 이어갈 수 있다는 뜻입니다. 대신 XOR과 나머지 연산이 어긋나지 않도록 버킷 개수를 2의 거듭제곱으로 두는 제약이 따라옵니다.

삭제는 해당 지문을 찾아 슬롯에서 지우면 끝납니다. 여기에 함정이 둘 있습니다. 같은 키를 두 번 넣었으면 두 번 지워야 하고, 넣은 적 없는 원소의 지문을 지우면 같은 지문을 쓰는 다른 키의 자리를 없앨 수 있습니다. 후자는 거짓 음성(false negative)을 만들어 필터의 기본 계약을 깨뜨립니다.

지문 충돌은 오탐 쪽에서도 같은 뿌리를 갖습니다. fingerprint(x)와 fingerprint(y)가 같으면 y를 넣지 않아도 조회가 참을 반환합니다. 충돌 확률이 지문 길이 k에 대해 1/2^k이므로, 목표 오탐률이 k를 정합니다.

블룸 필터와 갈리는 지점

블룸 필터는 m비트 배열과 k개 해시 함수로 집합 멤버십을 근사 판정합니다. 삽입은 k개 비트를 1로 세우고, 조회는 그 k개 비트가 모두 1인지 확인합니다. 비트 하나를 0으로 되돌리면 그 비트를 공유하는 다른 원소의 흔적까지 지워지므로 삭제가 불가능합니다.

Fan 외(CoNEXT 2014)의 측정에서 두 구조의 공간 우위는 목표 오탐률에서 갈립니다. 오탐률을 낮출수록 블룸 필터는 해시 함수 수를 늘려야 하고, 조회마다 흩어진 비트를 k번 읽는 비용이 커집니다. 쿠쿠 필터는 지문을 1비트 늘리면 오탐률이 절반이 되고 조회는 여전히 버킷 두 개만 읽습니다.

운영 기준은 부하율 상한에서 나옵니다. 킥아웃 체인 길이는 부하율이 임계값에 가까워질수록 급격히 늘어납니다. 실무 구현은 보통 80~85%를 상한으로 두고 초과하면 리사이즈합니다.

버킷을 겹쳐서 줄인 1비트

2025년 논문(arXiv:2505.05847)은 버킷 경계 자체를 바꿉니다. 기존 구조는 슬롯을 겹치지 않는 버킷으로 잘라 쓰는데, 지문 10비트 기준 공간 오버헤드가 1.365배였습니다. 이 논문은 겹치는 윈도우(overlapping window)를 도입했습니다.

기존 버킷    [s0 s1 s2 s3] [s4 s5 s6 s7] [s8 s9 ...]     boundary fixed
window l=2   [s0 s1] [s1 s2] [s2 s3] [s3 s4] ...         overlapped, W = S - l + 1

앞 숫자는 해시 함수 수, 뒷 숫자는 버킷 또는 윈도우의 슬롯 수입니다. 겹침 덕분에 슬롯 하나를 여러 윈도우가 공유하게 되어 같은 슬롯 수로 더 많은 원소를 담습니다. 키당 저장 비트는 지문 k비트에 선택 비트 1개와 윈도우 오프셋 비트 1개를 더한 k+2비트로, 기존 k+3비트에서 1비트 줄었습니다. 논문은 온라인 삽입을 지원하는 필터 가운데 가장 작은 공간을 쓴다고 주장합니다.

비용도 함께 옵니다. 논문 평가에서 조회 속도는 Prefix Filter, VQF와 동등하지만 삽입은 더 느립니다. 윈도우 경계를 계산하는 오버헤드가 삽입 경로에 얹히기 때문입니다.

지문이 이미 최적이었다는 증명

지문 기반 필터를 앞으로 얼마나 더 줄일 수 있는지는 두 편의 이론 논문이 답을 냈습니다.

Kuszmaul과 Walzer(STOC 2024)는 삽입과 삭제를 모두 지원하는 동적 필터가 n log₂(1/ε) + Ω(n) 비트를 써야 함을 증명했습니다. n은 원소 수, ε은 목표 오탐률입니다. 정적 필터의 정보이론적 하한이 n log₂(1/ε)이므로, 동적성 자체가 원소당 상수 비트를 추가로 요구한다는 뜻입니다.

Kuszmaul, Liang, Zhou(FOCS 2025, arXiv:2510.18129)는 그 상수를 확정했습니다. ε이 0으로 갈 때 모든 동적 필터는 n log₂(1/ε) + n log₂e − o(n) 비트를 써야 하며, 1978년 Carter 등이 도입한 지문 기법이 이 하한을 달성합니다. 반세기 가까이 쓰인 기법이 정보이론적으로 더는 개선할 수 없는 해법이었다는 결론입니다.

표에서 눈에 띄는 것은 동적 하한이 블룸 필터보다 작다는 점입니다. 삭제를 지원하려면 공간을 더 써야 한다는 통념과 반대 방향입니다. 지문 기반 설계는 삭제를 제공하면서도 고전 블룸 필터보다 적은 공간으로 하한에 닿습니다. 앞 섹션의 윈도우 쿠쿠 필터는 키당 k+2비트를 쓰고, 동적 하한은 log₂(1/ε) + 1.4427비트입니다. 지문 길이를 log₂(1/ε)에 대응시키면 둘의 차이는 키당 0.6비트 미만입니다.

남은 문제는 크기입니다. 쿠쿠 필터는 초기 용량이 고정이라 데이터가 예상보다 늘면 오탐률이 올라가거나 메모리가 낭비됩니다. Aleph Filter(Dayan, Bercea, Pagh, 2024, arXiv:2404.04703)는 삽입과 조회, 삭제를 모두 O(1)로 유지합니다. 데이터가 무한히 늘어도 메모리와 오탐률이 안정적으로 유지된다는 것을 같은 논문이 보였습니다. 최종 데이터 크기 추정치가 있으면 정적 필터와 같은 공간 효율에 도달합니다.

정리

쿠쿠 해싱은 원소마다 후보 자리를 두 개 주고 킥아웃 체인으로 충돌을 밀어내, 조회 비용을 최악 O(1)로 고정합니다. 쿠쿠 필터는 여기에 지문과 XOR 대칭성을 얹어 원본 키 없이 킥아웃을 이어가고, 그 대가로 삭제 연산과 낮은 오탐률을 얻습니다. 삭제는 넣은 적 없는 원소를 지울 때 거짓 음성을 만들므로 호출자가 삽입 이력을 책임져야 합니다. 2025년 윈도우 구조는 버킷을 겹쳐 키당 1비트를 줄였고, 같은 해 FOCS의 하한 증명은 1978년 지문 기법이 이미 동적 필터의 최적해였음을 밝혔습니다. 집합이 계속 바뀌는 워크로드라면 지문 기반 필터가 기본값이고, 남은 선택은 지문 길이와 부하율 상한을 어디에 둘지입니다.