ChatGPT로 Bloom Filter (블룸 필터) 공부해 보기

Q. 블룸 필터란?

 

A.

블룸 필터는 요소가 집합의 구성원인지 여부를 테스트하는 데 사용되는 공간 효율적인 확률 데이터 구조입니다. 제어 가능한 가양성 비율(세트에 있는 요소를 잘못 보고함)과 함께 "아마도 세트에 있음" 또는 "확실히 세트에 없음"을 반환하지만 가음성은 없음(세트에 없는 것으로 요소를 보고하지 않음) 실제로 있을 때). 맞춤법 검사 및 네트워크 트래픽 필터링과 같은 다양한 응용 프로그램에 사용됩니다.

---

Q. 자바를 사용하는 코드 블룸 필터를 보여주세요.

import java.util.BitSet;

public class BloomFilter {
    private static final int DEFAULT_SIZE = 2 << 24;
    private static final int[] seeds = new int[]{7, 11, 13, 31, 37, 61};
    private BitSet bits = new BitSet(DEFAULT_SIZE);
    private SimpleHash[] func = new SimpleHash[seeds.length];

    public BloomFilter() {
        for (int i = 0; i < seeds.length; i++) {
            func[i] = new SimpleHash(DEFAULT_SIZE, seeds[i]);
        }
    }

    public void add(String value) {
        for (SimpleHash f : func) {
            bits.set(f.hash(value), true);
        }
    }

    public boolean contains(String value) {
        if (value == null) {
            return false;
        }

        boolean ret = true;
        for (SimpleHash f : func) {
            ret = ret && bits.get(f.hash(value));
        }
        return ret;
    }

    public static class SimpleHash {
        private int cap;
        private int seed;

        public SimpleHash(int cap, int seed) {
            this.cap = cap;
            this.seed = seed;
        }

        public int hash(String value) {
            int result = 0;
            int len = value.length();
            for (int i = 0; i < len; i++) {
                result = seed * result + value.charAt(i);
            }
            return (cap - 1) & result;
        }
    }
}​

이 구현은 BitSet데이터 구조를 사용하여 항목 집합을 저장하고 여러 SimpleHash함수를 사용하여 항목을 BitSet. 각 항목은 필터에 모든 해시 함수를 적용하고 에서 해당 비트를 로 설정하여 필터에 추가 BitSet됩니다 true. 항목이 세트에 있는지 확인하기 위해 동일한 해시 함수가 항목에 적용되고 의 비트 BitSet가 확인됩니다. 모든 비트가 설정되면 항목은 "아마도 설정에 포함"됩니다. 그렇지 않으면 "확실히 집합에 포함되지 않음"입니다.

 

 

ps> 오라클에서 Hash Join 시에도 블룸 필터를 사용한다고 공부를 한 적인 있는데, 간단한 소스코드를 보니 블룸 필터 원리를 

       조금 더 쉽게 이해할 수 있네요.