블룸 필터 편집하기 (부분)

=== Java 구현 ===

<syntaxhighlight lang="java">
import java.nio.charset.StandardCharsets;
import java.security.MessageDigest;
import java.security.NoSuchAlgorithmException;
import java.util.BitSet;

public class BloomFilter {
    private final int m;          // 비트 배열 크기
    private final int k;          // 해시 함수 개수
    private final BitSet bitSet;
    private int count;

    public BloomFilter(int n, double fpRate) {
        this.m = optimalM(n, fpRate);
        this.k = optimalK(m, n);
        this.bitSet = new BitSet(m);
        this.count = 0;
        System.out.printf("BloomFilter: m=%d bits, k=%d hash functions%n", m, k);
    }

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

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

    private int[] hashIndices(String item) {
        int[] indices = new int[k];
        try {
            MessageDigest md = MessageDigest.getInstance("SHA-256");
            byte[] digest = md.digest(item.getBytes(StandardCharsets.UTF_8));

            long h1 = bytesToLong(digest, 0);
            long h2 = bytesToLong(digest, 8);

            for (int i = 0; i < k; i++) {
                indices[i] = (int) Math.floorMod(h1 + (long) i * h2, m);
            }
        } catch (NoSuchAlgorithmException e) {
            throw new RuntimeException(e);
        }
        return indices;
    }

    private long bytesToLong(byte[] bytes, int offset) {
        long val = 0;
        for (int i = 0; i < 8; i++) {
            val = (val << 8) | (bytes[offset + i] & 0xFF);
        }
        return val;
    }

    public void add(String item) {
        for (int idx : hashIndices(item)) {
            bitSet.set(idx);
        }
        count++;
    }

    public boolean mightContain(String item) {
        for (int idx : hashIndices(item)) {
            if (!bitSet.get(idx)) return false;
        }
        return true;
    }

    public double estimatedFpRate() {
        return Math.pow(1 - Math.exp(-(double) k * count / m), k);
    }

    // 사용 예시
    public static void main(String[] args) {
        BloomFilter bf = new BloomFilter(1_000_000, 0.01);

        bf.add("hello");
        bf.add("world");
        bf.add("java");

        System.out.println(bf.mightContain("hello")); // true
        System.out.println(bf.mightContain("python")); // false (높은 확률로)
        System.out.printf("추정 오탐률: %.6f%%%n", bf.estimatedFpRate() * 100);
    }
}
</syntaxhighlight>