블룸 필터(Bloom Filter)의 동작 원리와 사용 사례를 설명해주세요.

블룸 필터는 어떤 원소가 집합에 속하는지 여부를 검사하는 데 사용되는 확률적인 자료 구조입니다. 핵심 아이디어는 여러 개의 해시 함수를 사용하여 원소를 비트 배열의 여러 위치에 매핑하는 것입니다.

원소를 추가할 때는 각 해시 함수를 통해 얻은 인덱스에 해당하는 비트를 1로 설정합니다. 원소의 존재 여부를 확인할 때는 동일한 해시 함수들을 사용하여 비트 배열의 해당 위치를 확인합니다. 모든 위치의 비트가 1로 설정되어 있다면, 그 원소가 집합에 "아마도" 존재한다고 판단합니다.

블룸 필터는 공간 효율성이 매우 높지만, False Positive(오탐)가 발생할 수 있다는 단점이 있습니다. 즉, 실제로는 집합에 없는 원소를 있다고 판단할 수 있습니다. 하지만 False Negative(미탐)는 발생하지 않습니다.

주요 사용 사례로는 데이터베이스 시스템에서 존재하지 않는 키에 대한 접근을 빠르게 필터링하거나, 네트워크 캐시에서 이미 캐싱된 데이터를 확인하는 데 사용될 수 있습니다. 또한 스팸 필터링이나 악성 URL 검사 등에도 활용됩니다.