램값이 비쌀 때 쓰는 자료구조

블룸 필터란?

블룸 필터는 데이터를 효율적으로 저장하고 검색할 수 있게 돕는 자료 구조에요. 일반적인 DB와는 다르게, 블룸 필터는 데이터를 메모리에 압축하여 저장하기 때문에 메모리 사용량이 적고, 검색 속도가 빠르죠. 아주 많은 양의 데이터를 처리할 때 유용하게 사용할 수 있어요.

예를 들어, 좋아하는 포켓몬의 이름을 블룸 필터에 저장한다고 해볼게요. 이때 데이터는 0과 1로 변환되어 저장되며, 비트 배열에 겹쳐서 기록되죠. 이렇게 하면 메모리 용량을 대폭 줄일 수 있어요. 블룸 필터는 특히 유저 수가 많은 웹사이트, 예를 들어 소셜 미디어 플랫폼에서 많이 사용되죠.

블룸 필터는 '오류 가능성'이 있다는 점도 기억해두세요. 데이터 검색 시, 비트가 일치한다고 해서 반드시 그 데이터가 존재하는 것은 아니에요. 이처럼 블룸 필터는 메모리 절약과 빠른 검색 속도를 제공하지만, 정확도와의 트레이드오프가 있어요.

블룸 필터의 동작 원리

블룸 필터의 작동 원리는 아주 간단해요. 먼저 해시 함수를 사용해 데이터를 숫자로 변환하고, 이 숫자에 따라 비트 배열의 특정 위치를 1로 마킹해요. 예를 들어 포켓몬 이름을 해시 함수에 넣으면, 여러 개의 숫자가 출력되죠. 이 숫자에 해당하는 비트 배열의 위치를 1로 설정하면 되는 거예요.

이후에 새로운 데이터를 추가할 때도 같은 방식으로 진행해요. 이미 마킹된 비트가 있다면 그냥 덮어쓰는 식이죠. 이렇게 하면 메모리 사용량이 줄어들고, 검색 속도도 빨라져요.

데이터 검색 시에는 동일한 해시 함수를 사용해 비트 배열을 확인해요. 여기서 모든 위치의 비트가 1이라면 데이터를 포함하고 있을 가능성이 높지만, 반드시 존재한다고 보장할 수는 없어요. 이 때문에 블룸 필터의 정확도는 해시 함수의 개수와 비트 배열의 크기에 따라 달라지죠.

블룸 필터 활용 사례와 주의사항

블룸 필터는 여러 분야에서 유용하게 사용되고 있어요. 예를 들어, 회원 가입 시 아이디가 이미 존재하는지 확인하는 데 쓰일 수 있어요. 블룸 필터에 전체 아이디를 저장해두고, 새로운 아이디가 있는지 확인할 때 빠르게 검색할 수 있죠. 이 과정에서 DB를 직접 조회해야 하는 경우를 줄일 수 있어, 시스템의 성능을 향상시킬 수 있어요.

또한, 웹 브라우저인 크롬은 악성 사이트 URL을 필터링할 때 블룸 필터를 사용하고 있어요. 이처럼 블룸 필터는 메모리 용량을 절약하고, 검색 속도를 높이는 데 큰 도움이 되죠.

하지만 블룸 필터의 단점도 잊지 말아야 해요. 오류가 발생할 수 있기 때문에, 중요한 데이터에 대해서는 검증이 필요해요. 예를 들어, 블룸 필터가 '존재한다'고 판단한 데이터가 실제로는 없을 수도 있죠. 따라서, 블룸 필터를 사용할 때는 이러한 한계를 인지하고 활용해야 해요.

블룸 필터를 도입할 때는 비트의 수와 해시 함수의 개수를 조정하여 정확도를 조절할 수 있어요. 하지만 정확도가 높아질수록 메모리 사용량도 증가한다는 점을 유의해야 해요.