블룸 필터는 빠르고 메모리 효율적인 방식으로 집합에서 요소의 존재를 식별하도록 설계된 데이터 구조로 정의됩니다.
확률적 데이터 구조라는 특정 데이터 구조 블룸 필터로 구현됩니다. 이 데이터 구조는 요소가 집합에 있는지 여부를 식별하는 데 도움이 됩니다.
비트 벡터는 기본 데이터 구조로 구현됩니다. 다음은 설명하는 데 사용할 작은 것입니다.
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
해당 테이블의 각 빈 셀은 비트와 그 아래의 숫자를 인덱스 또는 위치로 지정합니다. 블룸 필터에 요소를 추가하려면 간단히 몇 번 해시하고 해당 해시의 위치 또는 인덱스에 있는 비트 벡터의 비트를 1로 설정합니다.
블룸 필터의 정교한 구현은 다음에서 논의됩니다.
블룸 필터는 처음에는 개체를 추가하고 개체를 추적하고 다음에는 개체가 이전에 본 적이 있는지 확인하는 두 가지 작업을 지원합니다.
블룸 필터에 개체 추가
- 추가할 개체의 해시 값을 계산합니다.
- 우리는 이러한 해시 값을 구현하여 Bloom 필터 상태에서 특정 비트를 설정합니다(해시 값은 설정할 비트의 위치).
블룸 필터에 개체가 포함되어 있는지 확인하기 -
- 추가할 개체의 해시 값을 계산합니다.
- 다음으로 이러한 해시 값으로 인덱싱된 비트가 블룸 필터 상태로 설정되었는지 확인합니다.
객체의 해시 값이 블룸 필터 상태에 직접 추가되지 않는다는 점을 명심해야 합니다. 각 해시 함수는 단순히 설정하거나 확인할 비트를 결정합니다. 예:해시 함수를 하나만 사용하는 경우 1비트만 확인하거나 확인합니다.