#11 블룸 필터

블룸 필터(Bloom Filter)는 확률적인 데이터 구조로, 주어진 요소가 집합에 속해 있는지 여부를 빠르게 확인하는 데 사용되는 자료구조입니다. 블룸 필터는 빠른 조회 속도와 상대적으로 적은 메모리 사용량으로 유명하며, 특히 빅 데이터 환경에서 많이 사용됩니다. 이제 블룸 필터의 작동 원리와 특징에 대해 자세히 설명하겠습니다.

 

블룸 필터의 작동 원리

비트 배열 (Bit Array): 블룸 필터는 먼저 일련의 비트를 갖는 배열을 사용합니다. 이 배열의 길이는 미리 정의되며, 모든 비트는 초기에 0으로 설정됩니다.

해시 함수 (Hash Function): 블룸 필터는 여러 개의 해시 함수를 사용합니다. 각 요소를 필터에 추가할 때, 해당 요소를 여러 번의 해시 함수를 통해 다른 위치에 매핑시킵니다. 이 때, 해시 함수는 임의성(randomness)이 있어야 하며, 각 요소는 독립적으로 해시 함수의 결과에 영향을 줄 수 있어야 합니다.

요소 추가 (Adding Elements): 블룸 필터에 요소를 추가할 때, 해당 요소를 여러 번의 해시 함수를 통해 얻은 위치의 비트를 1로 설정합니다.

요소 조회 (Querying Elements): 요소의 존재 여부를 확인하려면, 해당 요소를 해시 함수를 통해 얻은 위치를 조회하고, 해당 위치의 비트 값이 모두 1인지 확인합니다. 만약 모든 비트가 1이라면 해당 요소가 필터에 있을 가능성이 높으므로 "있을 수도 있음"으로 반환됩니다. 하지만 하나 이상의 비트가 0인 경우, 해당 요소는 필터에 없음으로 판단됩니다.

 

블룸 필터의 특징

확률적 데이터 구조: 블룸 필터는 100% 정확성을 보장하지 않습니다. 추가한 요소의 개수가 증가하면서 다양한 요소들이 해시 충돌로 인해 같은 위치에 매핑될 수 있습니다. 이로 인해 오류가 발생할 수 있습니다.

저용량: 블룸 필터는 다른 데이터 구조에 비해 상대적으로 적은 메모리를 사용합니다. 이는 해시 함수를 사용하여 요소를 여러 위치에 저장하기 때문에 가능합니다.

빠른 조회 속도: 블룸 필터는 해시 함수를 통해 요소의 위치를 바로 알 수 있으므로 조회 속도가 매우 빠릅니다.

요소 삭제 불가능: 블룸 필터는 요소를 삭제할 수 없습니다. 이미 1로 설정된 비트를 0으로 변경하는 것은 불가능하며, 이로 인해 요소의 중복 추가가 발생할 수 있습니다.

적절한 요소 개수와 확률 선택 필요: 블룸 필터의 성능은 배열의 길이와 해시 함수 개수, 필터에 추가된 요소의 개수에 의해 결정됩니다. 적절한 값들을 선택해야 오류 확률을 관리할 수 있습니다.

블룸 필터는 주어진 요소가 집합에 속해 있는지 여부를 확률적으로 빠르게 확인하는 데 유용한 자료구조입니다. 그러나 100% 정확성을 보장하지 않기 때문에 모든 상황에 적합하지는 않을 수 있습니다. 데이터베이스, 캐싱, 네트워크 라우팅 등의 분야에서 널리 사용되며, 자원이 제한된 환경에서 유용하게 활용될 수 있습니다.