Bloom Filter 개요

Bloom Filter는 1970년 Burton Howard Bloom이 제안한 데이터 구조로, O(k) 시간 복잡도를 가지며, 키-값 쌍을 저장하는 맵과는 다르게 오탐(false positive)과 미탐(false negative) 문제를 다룬다.

주요 특징

• 메모리 효율적이며, 주로 웹 캐시, 네트워크 패킷 분석 등에 사용된다.

• 오탐 확률을 조절하여 성능을 최적화할 수 있다.

• Counting Bloom Filter를 통해 데이터 삭제가 가능하다.

결론

Bloom Filter는 메모리 사용과 성능 간의 trade-off를 고려하여 설계되어야 하며, 특정 상황에서 매우 유용하다.