7. Bloom Filters

1) Bloom Filters란 무엇인가?

블룸 필터는 데이터가 존재하는지 빠르게 확인할 수 있는 메모리 효율적인 자료 구조입니다. 이 필터는 여러 해시 함수로 데이터를 비트 배열에 매핑하여 사용됩니다. 결과적으로, 필터가 "데이터가 존재하지 않는다"고 말하면 확실하게 없다는 의미이고, "존재한다"고 말하면 실제로 존재하지 않을 가능성도 일부 존재합니다(오탐). 이는 정확도보다는 속도와 메모리 효율성이 중요한 상황에서 유용합니다.

2) Bloom Filters을 다룰 수 있는 주요 메서드

1. insert(item): 블룸 필터에 새로운 항목을 추가합니다. 선택한 해시 함수들을 사용해 항목을 해시하고, 그에 해당하는 비트를 필터에서 설정합니다.

2. contains(item): 특정 항목이 블룸 필터에 존재하는지 확인합니다. 모든 해시 함수가 반환하는 비트가 설정되어 있는지 확인하며, 설정된 경우에만 필터가 항목을 포함한다고 판단합니다.

3. clear(): 블룸 필터를 초기화하여 모든 비트를 0으로 재설정합니다.

4. merge(other_bloom_filter): 두 블룸 필터를 병합합니다. 두 필터의 각 비트를 OR 연산으로 결합해 새로운 필터를 만듭니다.

3) 예제코드

use std::collections::hash_map::DefaultHasher;
use std::hash::{Hash, Hasher};

// BloomFilter 구조체 정의 - 비트 배열과 해시 함수 개수를 포함
struct BloomFilter {
    bit_array: Vec<bool>,
    num_hashes: usize,
}

// BloomFilter 메서드 구현
impl BloomFilter {
    // 새로운 BloomFilter 생성자
    fn new(size: usize, num_hashes: usize) -> Self {
        BloomFilter {
            bit_array: vec![false; size],
            num_hashes,
        }
    }

    // 해시 인덱스 생성 메서드
    fn hash<T: Hash>(&self, item: &T, i: usize) -> usize {
        let mut hasher = DefaultHasher::new();
        item.hash(&mut hasher);
        hasher.write_usize(i);
        (hasher.finish() % self.bit_array.len() as u64) as usize
    }

    // BloomFilter에 항목을 삽입하는 메서드
    fn insert<T: Hash>(&mut self, item: T) {
        for i in 0..self.num_hashes {
            let index = self.hash(&item, i);
            self.bit_array[index] = true;
        }
    }

    // 항목이 BloomFilter에 존재하는지 확인하는 메서드
    fn contains<T: Hash>(&self, item: T) -> bool {
        for i in 0..self.num_hashes {
            let index = self.hash(&item, i);
            if !self.bit_array[index] {
                return false;
            }
        }
        true
    }

    // BloomFilter를 초기화하는 메서드
    fn clear(&mut self) {
        for i in 0..self.bit_array.len() {
            self.bit_array[i] = false;
        }
    }
}

// BloomFilter 사용 예제
fn main() {
    let mut bloom_filter = BloomFilter::new(100, 3); // 100비트 배열, 3개의 해시 함수 사용

    let items = vec!["apple", "banana", "orange"];
    for item in &items {
        bloom_filter.insert(item);
    }

    // 항목의 존재 여부 확인
    println!("Contains 'apple': {}", bloom_filter.contains("apple")); // true
    println!("Contains 'grape': {}", bloom_filter.contains("grape")); // false

    // 필터 초기화
    bloom_filter.clear();
    println!("Contains 'apple' after clearing: {}", bloom_filter.contains("apple")); // false
}

4) 상세 설명

use std::collections::hash_map::DefaultHasher;
use std::hash::{Hash, Hasher};

• 이 부분에서는 DefaultHasher와 Hasher 트레이트를 사용하기 위해 std::collections::hash_map과 std::hash 모듈을 가져옵니다. DefaultHasher는 해시 함수를 구현하는 데 사용되며, Hash와 Hasher 트레이트는 해시 가능한 데이터를 다루기 위해 필요합니다.

struct BloomFilter {
    bit_array: Vec<bool>,
    num_hashes: usize,
}

• BloomFilter라는 구조체를 정의합니다. 이 구조체는 bit_array와 num_hashes라는 두 개의 필드를 가지고 있습니다.
  • bit_array: 블룸 필터의 비트 배열로, 데이터의 존재 여부를 나타냅니다.
  • num_hashes: 해시 함수의 개수를 나타내며, 블룸 필터에서 데이터 삽입 및 검사를 위해 사용됩니다.

impl BloomFilter {
    fn new(size: usize, num_hashes: usize) -> Self {
        BloomFilter {
            bit_array: vec![false; size],
            num_hashes,
        }
    }

• BloomFilter 구조체의 메서드를 구현하는 부분입니다. new 메서드는 새로운 BloomFilter 인스턴스를 생성합니다.
  • size: 비트 배열의 크기를 지정합니다.
  • num_hashes: 사용할 해시 함수의 개수를 지정합니다.
  • 반환 값은 초기화된 BloomFilter 인스턴스입니다.

fn hash<T: Hash>(&self, item: &T, i: usize) -> usize {
    let mut hasher = DefaultHasher::new();
    item.hash(&mut hasher);
    hasher.write_usize(i);
    (hasher.finish() % self.bit_array.len() as u64) as usize
}

• hash 메서드는 주어진 항목과 인덱스를 사용하여 해시 값을 계산합니다.
  • item: 해시할 항목.
  • i: 해시 함수의 인덱스.
  • 반환 값은 비트 배열 내의 인덱스입니다.

fn insert<T: Hash>(&mut self, item: T) {
    for i in 0..self.num_hashes {
        let index = self.hash(&item, i);
        self.bit_array[index] = true;
    }
}

• insert 메서드는 항목을 블룸 필터에 삽입합니다.
  • 항목을 해시하고, 해당 해시 값에 해당하는 비트를 true로 설정합니다.

fn contains<T: Hash>(&self, item: T) -> bool {
    for i in 0..self.num_hashes {
        let index = self.hash(&item, i);
        if !self.bit_array[index] {
            return false;
        }
    }
    true
}

• contains 메서드는 항목이 블룸 필터에 존재할 가능성이 있는지 확인합니다.
  • 만약 해시된 비트 중 하나라도 false이면, 항목은 블룸 필터에 존재하지 않음을 의미합니다.

fn clear(&mut self) {
    for i in 0..self.bit_array.len() {
        self.bit_array[i] = false;
    }
}

• clear 메서드는 블룸 필터의 모든 비트를 초기화하여 비어 있는 상태로 만듭니다.

fn main() {
    let mut bloom_filter = BloomFilter::new(100, 3); // 100비트 배열, 3개의 해시 함수 사용

• main 함수는 블룸 필터의 사용 예제를 보여줍니다.
  • 비트 배열 크기를 100으로 하고, 3개의 해시 함수를 사용하는 블룸 필터를 생성합니다.

let items = vec!["apple", "banana", "orange"];
for item in &items {
    bloom_filter.insert(item);
}

• 몇 개의 항목을 블룸 필터에 삽입합니다.
  • "apple", "banana", "orange" 항목을 필터에 삽입합니다.

println!("Contains 'apple': {}", bloom_filter.contains("apple")); // true
println!("Contains 'grape': {}", bloom_filter.contains("grape")); // false

• 삽입된 항목과 삽입되지 않은 항목이 필터에 있는지 확인합니다.
  • "apple"은 삽입되었으므로 true를 반환하고, "grape"는 삽입되지 않았으므로 false를 반환합니다.

bloom_filter.clear();
println!("Contains 'apple' after clearing: {}", bloom_filter.contains("apple")); // false
}

• 블룸 필터를 초기화한 후 "apple"의 존재 여부를 다시 확인합니다.
  • 초기화 후에는 "apple"도 false를 반환합니다.