더북(TheBook)

  8. 지금까지 작성한 코드를 수행하면 다음과 같은 출력이 나타납니다.

100을(를) 삽입: 1 0 1 0 0 0 0
54을(를) 삽입: 1 0 1 0 1 1 0
82을(를) 삽입: 1 0 1 0 1 1 0
5: 있을 수 있음
50: 절대 없음
20: 절대 없음
54: 있을 수 있음

출력 결과를 보면 거짓-긍정이 발견되지만, 거짓-부정은 나타나지 않는 것을 확인할 수 있습니다.

main() 함수와 bloom_filter 클래스 생성자 코드를 보면 이 프로그램에서 필요한 정보를 저장하기 위해 겨우 7비트만을 사용했습니다. 필터 크기를 좀 더 크게 설정하고 해시 함수를 보완하면 훨씬 더 나은 성능을 얻을 수 있습니다. 예를 들어 배열 크기를 소수인 1023으로 늘려도 실제로는 130바이트보다 작은 메모리를 사용하는 것이며, 이는 다른 방법보다는 훨씬 작은 메모리만 사용하는 것입니다. 해시 테이블 크기를 1023으로 늘렸다면 해시 함수도 hash(x) = x % 1023 같은 형태로 사용할 수 있고, 이 경우 더 나은 숫자들의 분포와 결과를 얻을 수 있습니다.

블룸 필터는 컨테이너에 실제 데이터를 저장하지 않기 때문에 다양한 타입의 데이터에 대해서도 사용할 수 있습니다. 해시 함수를 충분히 잘 만들었다면 하나의 블룸 필터에 정수, 문자열, 실수 등의 데이터를 섞어서 삽입할 수도 있습니다.

신간 소식 구독하기
뉴스레터에 가입하시고 이메일로 신간 소식을 받아 보세요.