Bloom Filter 는 어떤 멤버가 집합에 속하는 지를 판단할 때 사용하는 자료구조다. Bloom Filter는 확률형 자료구조기 때문에, 집합에 속한 멤버를 확인하려고 할 때 틀린 답을 내뱉을 수 있다. 하지만 없는 멤버를 있다고는 말할 수 있지만(False Positive) / 있는 멤버를 없다고 말하지는 않는다(False Negative). 어떻게 동작할까? Bloom Filter는 0으로 셋팅되어 있는 bit array를 사용한다. 그리고, 두 개의 멤버(star, moon)를 이 Bloom Filter에 넣는다면 k개의 hash function을 사용한 후 modulo 연산을 해서 bit를 1로 채워넣는다. 어떤 문자(mars)가 이 집합에 속하는 지를 확인할 때 이렇게 만들어진 bit..
