Cuckoo Filter

Cuckoo Filter

Bloom Filter를 개선한 확률적 자료구조로, 삭제 기능을 지원하고 더 나은 공간 효율과 성능을 제공하며 Cuckoo Hashing 기법을 활용하여 항목을 2개 후보 위치에 저장

목적: 집합 멤버십 테스트, 삭제 지원, Bloom Filter 개선, 공간 효율

특징: 삭제 가능, 2개 해시 위치, 낮은 거짓 긍정률, 더 나은 공간 효율

구조: 버킷 배열, 각 버킷은 여러 슬롯(4개), 각 슬롯은 지문(fingerprint) 저장

동작

• •insert(x): ① 지문 f = fingerprint(x) 계산 → ② 2개 후보 위치 i1, i2 계산 → ③ 빈 슬롯에 삽입, 없으면 Cuckoo 교체(한쪽 항목 퇴거→재배치)
• •lookup(x): 2개 후보 위치의 지문 확인 → 존재하면 "있을 수 있음"
• •delete(x): 2개 후보 위치 중 하나에서 지문 제거

Cuckoo Hashing: 삽입 시 충돌 발생 → 기존 항목 퇴거 → 대체 위치로 이동 → 연쇄 재배치 → 최대 500회 재시도

시간 복잡도: lookup O(1), insert·delete 평균 O(1)

공간 복잡도: O(n) - Bloom Filter보다 작음

장점: 삭제 가능, 더 나은 공간 효율, 낮은 거짓 긍정률, 캐시 효율

단점: 삽입 실패 가능(재해싱 필요), 구현 복잡도, 거짓 긍정 여전히 존재

적용사례: 네트워크 라우터, 캐시 시스템, 데이터베이스 필터, 웹 크롤러, 중복 검사

비교: Cuckoo Filter(삭제/작음) vs Bloom Filter(삭제불가/큼) vs 해시 셋(정확/매우큼)

연관: Bloom Filter, Cuckoo Hashing, 확률적 자료구조, 지문