블룸 필터는 집합에 원소가 존재하는지 빠르게 확인하는 확률적 자료구조입니다. 여러 해시 함수를 사용해서 공간 효율을 극대화합니다.
블룸 필터 원리
비트 배열과 여러 해시 함수로 구성됩니다. 원소를 추가할 때 각 해시 함수로 인덱스를 계산하고 해당 비트를 1로 설정합니다.
조회할 때 같은 해시 함수로 인덱스를 계산하고 모든 비트가 1이면 "아마도 존재"입니다. 하나라도 0이면 "확실히 없음"입니다.
False Positive
없는 원소를 있다고 할 수 있지만, 있는 원소를 없다고 하지는 않습니다. 해시 생성기에서 다른 입력이 같은 해시를 만들 수 있는 것과 관련됩니다.
활용 사례
캐시 확인, 스팸 필터, 데이터베이스 쿼리 최적화 등에 사용됩니다. 온라인 해시 도구로 해시의 기본을 이해하면 이런 고급 자료구조도 이해할 수 있습니다.
개발 환경에서의 해시 활용
개발자라면 해시 생성기를 다양한 상황에서 활용할 수 있습니다. API 테스트 시 요청 서명을 검증하거나, 캐시 키를 생성하거나, 파일 업로드 전 중복 체크를 할 때 유용합니다. 특히 디버깅할 때 "내가 계산한 해시가 맞는지" 빠르게 확인하는 용도로 좋습니다. 코드에서 계산한 값과 온라인 도구의 결과가 다르면 인코딩이나 입력 처리에 문제가 있다는 뜻이니까요.
해시 결과 비교 방법
두 해시값을 비교할 때는 대소문자를 통일해야 합니다. 일부 도구는 대문자로, 일부는 소문자로 출력합니다. 프로그래밍에서는 대소문자 무시 비교를 하거나, 양쪽 다 소문자로 변환 후 비교하는 게 안전합니다. 또한 해시 비교는 항상 상수 시간 비교 함수를 사용해야 타이밍 공격을 방지할 수 있습니다.