블룸필터와 하이퍼로그로그

집합 내에서 새로운 항목이 들어왔을 때, 이 항목이 이미 집합에 있는지 없는지를 확인하는 경우. 해시 테이블을 사용한다면 평균 탐색 시간이 O(1)이기 때문에 상수시간으로 확인할 수 있다. 하지만 해당 집합이 크다면 해시 테이블도 커져서 많은 저장공간을 필요로 하게 된다.

블룸 필터 (bloom filter)

확률론적인 자료구조이다. 거의 대부분 옳은 답을 주기는 하지만 항상 그렇지는 않다.

• 틀린 답을 맞다고 할 수도 있다.
• 하지만 맞는 답을 틀렸다고 하지는 않는다.
• 저장 공간을 아주 적게 차지한다.

하이퍼로그로그 (HyperLogLog)

집합에 있는 똑같은 원소의 개수를 대략적으로 셀 수 있다. 정확한 값을 주지는 않지만 정확한 값을 주기 위해 필요한 메모리의 아주 일부분만 사용해 근사값을 제공한다. 사용자의 검색로그에서 특정 검색어에 대한 횟수 카운트나 쇼핑몰에서 특정 상품을 몇번 봤는지 확인하는 등에 사용된다. (로그를 저장하는 데에는 엄청나게 많은 저장 공간이 필요할 것이다.)

reference

도서 : Hello Coding 그림으로 개념을 이해하는 알고리즘