블룸 필터

어떤 값이 집합에 들어 있는지를 아주 적은 메모리로 판단하는 자료구조다. 대답은 「아마 있다」 아니면 「확실히 없다」 둘뿐이다. 넣은 적 없는 값을 있다고 잘못 말할 수는 있지만(오탐), 넣은 값을 없다고 말하는 일(누락)은 없다. 넣을수록 잘못 말할 확률이 커지고, 기본형은 넣은 값을 뺄 수 없다.