Bloom Filter가 뭔데?
3
AI 요약
이 글은 AI가 원문을 분석하여 핵심 내용을 요약한 것입니다.
Bloom Filter 개요
Bloom Filter는 1970년 Burton Howard Bloom이 제안한 데이터 구조로, O(k) 시간 복잡도를 가지며, 키-값 쌍을 저장하는 맵과는 다르게 오탐(false positive)과 미탐(false negative) 문제를 다룬다.
주요 특징
메모리 효율적이며, 주로 웹 캐시, 네트워크 패킷 분석 등에 사용된다.
오탐 확률을 조절하여 성능을 최적화할 수 있다.
Counting Bloom Filter를 통해 데이터 삭제가 가능하다.
결론
Bloom Filter는 메모리 사용과 성능 간의 trade-off를 고려하여 설계되어야 하며, 특정 상황에서 매우 유용하다.