블룸 필터 — 있을 수도 있다는 대답의 가치

해시 함수 3개, 비트 배열 크기 10

추가: "apple"
  h1("apple") = 2, h2("apple") = 5, h3("apple") = 8
  비트 배열: [0, 0, 1, 0, 0, 1, 0, 0, 1, 0]

추가: "banana"
  h1("banana") = 1, h2("banana") = 5, h3("banana") = 7
  비트 배열: [0, 1, 1, 0, 0, 1, 0, 1, 1, 0]

조회: "cherry"
  h1("cherry") = 2, h2("cherry") = 5, h3("cherry") = 3
  비트 배열[3] = 0 → "확실히 없다" ✓

조회: "grape"
  h1("grape") = 1, h2("grape") = 5, h3("grape") = 8
  모두 1 → "있을 수도 있다" (실제로는 없지만 false positive!)

public class BloomFilter {
    private BitSet bitSet;
    private int size;          // 비트 배열 크기
    private int hashCount;     // 해시 함수 개수

    public BloomFilter(int expectedElements, double falsePositiveRate) {
        // 최적 비트 배열 크기: m = -(n × ln(p)) / (ln2)²
        this.size = optimalSize(expectedElements, falsePositiveRate);
        // 최적 해시 함수 개수: k = (m/n) × ln2
        this.hashCount = optimalHashCount(size, expectedElements);
        this.bitSet = new BitSet(size);
    }

    public void add(String element) {
        for (int i = 0; i < hashCount; i++) {
            int hash = hash(element, i);
            bitSet.set(hash);
        }
    }

    public boolean mightContain(String element) {
        for (int i = 0; i < hashCount; i++) {
            int hash = hash(element, i);
            if (!bitSet.get(hash)) {
                return false; // 확실히 없다
            }
        }
        return true; // 있을 수도 있다
    }

    // 이중 해싱으로 k개의 해시 함수 생성
    private int hash(String element, int i) {
        int hash1 = element.hashCode();
        int hash2 = hash1 >>> 16; // 상위 비트 활용
        long combined = (hash1 & 0xFFFFFFFFL) + (long) i * (hash2 & 0xFFFFFFFFL);
        return (int) (Math.abs(combined) % size);
    }

    private static int optimalSize(int n, double p) {
        return (int) Math.ceil(-n * Math.log(p) / (Math.log(2) * Math.log(2)));
    }

    private static int optimalHashCount(int m, int n) {
        return Math.max(1, (int) Math.round((double) m / n * Math.log(2)));
    }
}

p ≈ (1 - e^(-kn/m))^k

m: 비트 배열 크기
n: 삽입된 원소 수
k: 해시 함수 수

public class CountingBloomFilter {
    private int[] counters;
    private int size;
    private int hashCount;

    public void add(String element) {
        for (int i = 0; i < hashCount; i++) {
            counters[hash(element, i)]++;
        }
    }

    public void remove(String element) {
        // 먼저 존재 여부 확인
        if (!mightContain(element)) return;
        for (int i = 0; i < hashCount; i++) {
            int idx = hash(element, i);
            if (counters[idx] > 0) counters[idx]--;
        }
    }

    public boolean mightContain(String element) {
        for (int i = 0; i < hashCount; i++) {
            if (counters[hash(element, i)] == 0) return false;
        }
        return true;
    }
}

@Service
public class UserService {
    private final BloomFilter bloomFilter;
    private final UserRepository repository;

    public User findByEmail(String email) {
        // 블룸 필터로 빠른 판별
        if (!bloomFilter.mightContain(email)) {
            return null; // 확실히 없음 — DB 조회 스킵
        }

        // "있을 수도 있다" → DB에서 확인
        return repository.findByEmail(email).orElse(null);
    }
}

BF.RESERVE myfilter 0.01 1000000   # FP 1%, 100만 원소
BF.ADD myfilter "user@example.com"
BF.EXISTS myfilter "user@example.com"  # → 1 (있을 수도 있다)
BF.EXISTS myfilter "unknown@test.com"  # → 0 (확실히 없다)