Bloom filter (블룸 필터) 란?

블룸 필터 (Bloom filter) 는 집합안에 들어있지 않은, 원소를 걸러내기 위해 사용됩니다.
하지만 100% 걸러낼 수 는 없습니다.

예를 들어, 집합에 N개의 원소가 있고, bloom filter를 만드는데, M개의 hash function을 사용한다고 합시다.

1. N 사이즈의 bitmap을 정의합니다 (bitmap은 1 아니면 0, 데이터 사이즈 작음)
2. 각 원소는 각 hash function을 거쳐 M개의 해시 값, bitmap index 를 리턴합니다.
3. bitmap의 M 개의 위치에 1로 업데이트 해줍니다.
    -> 그럼, 총 M*N번 업데이트하게 됩니다.
    이 때, 다른/같은 원소가 다른/같은 hash function을 통해 이미 1로 표시된 중복된 index 위치를 return할 수 있습니다.
       (e.g H1(E1) == H2(E3)) 
4. 랜덤 원소가 집합안에 속해 있는지 검사하는 방법은
   M개의 hash 값으로 만들어낸 temporary bitmap과 집합에 대한 정보를 담고 있는 bitmap의 And(&) operation으로 알아낼 수 있습니다.

하지만 3번의 해시 값 중복 문제 때문에, 이는 랜덤 원소가 집합안에 속해 있는지 검사할 때, 집합이 아닌 원소의 M개의 해시 값이 우연히 bitmap에 1로 표시되어 있는 케이스가 있게 되고, False Postive의 경우를 만들어냅니다.
(그래서 100% 걸러 낼 수 없습니다.)

블룸 필터는 어디에 사용될 수 있을까요?

예시는, 아래 임지홍님의 글에서 확인하실 수 있습니다!
https://meetup.toast.com/posts/192

BloomFilter는 언제 쓰나요? : NHN Cloud Meetup