企业员工电脑监控软件中的Java布隆过滤器算法实践

import com.google.common.hash.HashFunction;
import com.google.common.hash.Hashing;
import java.util.BitSet;
/**
 * 企业员工电脑监控软件日志去重布隆过滤器
 * 适配日志ID的快速插入与重复判断
 */
public class LogBloomFilter {
    // 二进制位数组，存储哈希映射结果
    private final BitSet bitSet;
    // 位数组长度
    private final int bitSetSize;
    // 哈希函数个数
    private final int hashFunctionCount;
    // 采用Guava的多种哈希函数保证分布均匀
    private final HashFunction[] hashFunctions = {
            Hashing.md5(),
            Hashing.sha1(),
            Hashing.sha256(),
            Hashing.sha512(),
            Hashing.adler32(),
            Hashing.crc32(),
            Hashing.crc32c(),
            Hashing.murmur3_32(),
            Hashing.murmur3_128(),
            Hashing.sipHash24()
    };
    /**
     * 构造方法：根据预期数据量和误判率初始化参数
     * @param expectedDataSize 预期插入的日志ID数量
     * @param falsePositiveRate 可接受的误判率
     */
    public LogBloomFilter(int expectedDataSize, double falsePositiveRate) {
        // 计算最优位数组长度
        this.bitSetSize = calculateBitSetSize(expectedDataSize, falsePositiveRate);
        // 计算最优哈希函数个数
        this.hashFunctionCount = calculateHashFunctionCount(bitSetSize, expectedDataSize);
        // 初始化位数组
        this.bitSet = new BitSet(bitSetSize);
    }
    /**
     * 计算最优位数组长度：m = -n * ln(p) / (ln2)^2
     */
    private int calculateBitSetSize(int n, double p) {
        if (p <= 0 || p >= 1) {
            throw new IllegalArgumentException("误判率必须介于(0,1)之间");
        }
        int m = (int) (-n * Math.log(p) / (Math.log(2) * Math.log(2)));
        return Math.max(m, 1); // 确保长度至少为1
    }
    /**
     * 计算最优哈希函数个数：k = (m/n) * ln2
     */
    private int calculateHashFunctionCount(int m, int n) {
        int k = (int) (m * Math.log(2) / n);
        return Math.max(Math.min(k, hashFunctions.length), 1); // 限制在可用哈希函数范围内
    }
    /**
     * 插入日志ID：将日志ID通过k个哈希函数映射到位数组
     * @param logId 企业员工电脑监控软件的日志唯一标识
     */
    public void put(String logId) {
        if (logId == null || logId.isEmpty()) {
            throw new IllegalArgumentException("日志ID不能为空");
        }
        // 生成k个不同的哈希索引并置1
        for (int i = 0; i < hashFunctionCount; i++) {
            long hashValue = hashFunctions[i].hashUnencodedChars(logId).asLong();
            // 确保索引为非负数且在位数组范围内
            int index = (int) (Math.abs(hashValue) % bitSetSize);
            bitSet.set(index);
        }
    }
    /**
     * 判断日志ID是否存在：存在返回true（可能误判），不存在返回false（绝对准确）
     * @param logId 待判断的日志唯一标识
     * @return 存在性判断结果
     */
    public boolean mightContain(String logId) {
        if (logId == null || logId.isEmpty()) {
            return false;
        }
        for (int i = 0; i < hashFunctionCount; i++) {
            long hashValue = hashFunctions[i].hashUnencodedChars(logId).asLong();
            int index = (int) (Math.abs(hashValue) % bitSetSize);
            // 任意一位为0则一定不存在
            if (!bitSet.get(index)) {
                return false;
            }
        }
        return true;
    }
    // 清空位数组（用于日志周期清理）
    public void clear() {
        bitSet.clear();
    }
}

import java.util.Random;
/**
 * 企业员工电脑监控软件日志去重测试
 */
public class BloomFilterTest {
    public static void main(String[] args) {
        // 配置：预期日均日志100万条，误判率0.0001
        LogBloomFilter logFilter = new LogBloomFilter(1_000_000, 0.0001);
        Random random = new Random();
        int testCount = 1_200_000; // 测试数据量（包含20万重复数据）
        int duplicateCount = 0;
        int falsePositiveCount = 0;
        // 第一步：插入100万条唯一日志ID
        for (int i = 0; i < 1_000_000; i++) {
            String logId = "EMP_LOG_" + i + "_" + random.nextInt(1000000);
            logFilter.put(logId);
        }
        // 第二步：测试120万条数据（包含原有100万条+20万条新数据）
        for (int i = 0; i < testCount; i++) {
            String logId = i < 1_000_000 ? "EMP_LOG_" + i + "_" + random.nextInt(1000000) : "NEW_LOG_" + i;
            boolean exists = logFilter.mightContain(logId);
            
            // 统计重复数据和误判数据
            if (i < 1_000_000) {
                if (exists) duplicateCount++;
            } else {
                if (exists) falsePositiveCount++;
            }
        }
        // 输出测试结果
        System.out.println("企业员工电脑监控软件日志去重测试结果：");
        System.out.println("实际重复日志数：1000000，识别重复数：" + duplicateCount);
        System.out.println("新日志数：200000，误判数：" + falsePositiveCount);
        System.out.println("实际误判率：" + (double) falsePositiveCount / 200000);
    }
}