布隆过滤器实战：10万车牌0漏判，误判率低至0.0001%

import java.io.PrintStream; import java.util.BitSet; import java.util.HashSet; import java.util.Random; import java.util.Set; /** * 布隆过滤器校验车牌存在性测试零依赖main 直接运行 * 场景实际在用车牌 10 万个放入过滤器校验 500 万次10 万真实 490 万不存在。 * 输出真实车牌漏判率、不存在车牌的实测误判率、理论误判率、内存占用、500 万次查询耗时。 */ public class BloomFilterPlateTest { private static final int REAL_COUNT 100_000; private static final int FAKE_COUNT 4_900_000; private static final int QUERY_COUNT REAL_COUNT FAKE_COUNT; // 车牌后5位字符集不含 I、O接近真实车牌规则 private static final String PLATE_CHARS 0123456789ABCDEFGHJKLMNPQRSTUVWXYZ; public static void main(String[] args) throws Exception { System.setOut(new PrintStream(System.out, true, UTF-8)); System.out.printf(场景布隆过滤器容量 %d 个真实车牌校验 %d 次%d 真实 %d 不存在%n%n, REAL_COUNT, QUERY_COUNT, REAL_COUNT, FAKE_COUNT); // 1. 生成 10 万个唯一真实车牌粤B 5位 Random random new Random(42); SetString realPlates new HashSet(REAL_COUNT * 2); String[] realArray new String[REAL_COUNT]; int i 0; while (i REAL_COUNT) { String plate randomPlate(random, 粤B); if (realPlates.add(plate)) { realArray[i] plate; } } // 2. 生成 490 万个必然不存在的车牌前缀假A与粤B首字符不同绝不落入真实集合 String[] fakeArray new String[FAKE_COUNT]; for (int j 0; j FAKE_COUNT; j) { fakeArray[j] randomPlate(random, 假A); } // 3. 不同误判率档位下测试容量按 10 万、目标误判率建过滤器 double[] fppTargets {0.1, 0.01, 0.001, 0.0001, 0.00001}; System.out.println(目标误判率 | 位数组 | 每元素bit | 哈希个数 | 内存 | 理论误判率 | 实测误判率 | 漏判(应0) | 500万次查询耗时); System.out.println(---------|--------|----------|---------|------|-----------|-----------|-----------|---------------); for (double fpp : fppTargets) { runOnce(fpp, realPlates, realArray, fakeArray); } // 4. 对照HashSet 存 10 万车牌的内存量级String对象约56B 引用/Entry约40B ≈ 每条100B System.out.printf(%n对照HashSet 存 10 万车牌约 %.1f MB布隆过滤器 fpp1%% 时仅 %.0f KB约 1/100%n, REAL_COUNT * 100.0 / 1024 / 1024, realPlates.size() * 9.6 / 8 / 1024); // 5. 新旧实现性能对比fpp0.01先跑一遍预热 JIT 再计时 System.out.printf(%n优化对比目标误判率 1%%预热后计时%n); benchmark(SimpleBloomFilter原版, new SimpleBloomFilter(REAL_COUNT, 0.01), realArray, fakeArray); benchmark(FastBloomFilter优化版, new FastBloomFilter(REAL_COUNT, 0.01), realArray, fakeArray); } interface Bloom { void put(String value); boolean mightContain(String value); } private static void benchmark(String name, Bloom bloom, String[] realArray, String[] fakeArray) { runAll(bloom, realArray, fakeArray); long t0 System.currentTimeMillis(); for (String plate : realArray) { bloom.put(plate); } long t1 System.currentTimeMillis(); int falseNegative 0; for (String plate : realArray) { if (!bloom.mightContain(plate)) { falseNegative; } } int falsePositive 0; for (String fake : fakeArray) { if (bloom.mightContain(fake)) { falsePositive; } } long t2 System.currentTimeMillis(); System.out.printf(%-28s put 10万: %4d ms | 500万次查询: %4d ms | 实测误判率: %.4f%% | 漏判: %d%n, name, t1 - t0, t2 - t1, falsePositive * 100.0 / FAKE_COUNT, falseNegative); } private static long runAll(Bloom bloom, String[] realArray, String[] fakeArray) { long ops 0; for (String plate : realArray) { if (bloom.mightContain(plate)) ops; } for (String fake : fakeArray) { if (bloom.mightContain(fake)) ops; } return ops; } private static void runOnce(double fppTarget, SetString realPlates, String[] realArray, String[] fakeArray) { SimpleBloomFilter bloom new SimpleBloomFilter(REAL_COUNT, fppTarget); long start System.currentTimeMillis(); for (String plate : realArray) { bloom.put(plate); } // 真实车牌 10 万次校验布隆过滤器无漏判理论 100% 判存在 int falseNegative 0; for (String plate : realArray) { if (!bloom.mightContain(plate)) { falseNegative; } } // 不存在车牌 490 万次校验统计误判为存在的数量 int falsePositive 0; long queryStart System.currentTimeMillis(); for (int j 0; j FAKE_COUNT; j) { if (bloom.mightContain(fakeArray[j])) { falsePositive; } } long costMs System.currentTimeMillis() - queryStart; System.out.printf(%.4f | %d | %.1f | %d | %.0f KB | %.4f%% | %.4f%% | %d | %d ms%n, fppTarget, bloom.bitSize(), (double) bloom.bitSize() / REAL_COUNT, bloom.hashCount(), bloom.bitSize() / 8.0 / 1024, bloom.theoryFpp(REAL_COUNT) * 100, falsePositive * 100.0 / FAKE_COUNT, falseNegative, costMs); // 抽样演示误判样本与 HashSet精确容器比对 if (fppTarget 0.01) { int shown 0; for (int j 0; j FAKE_COUNT shown 3; j) { if (bloom.mightContain(fakeArray[j]) !realPlates.contains(fakeArray[j])) { System.out.printf( [误判示例] %s 布隆过滤器判存在实际不存在%n, fakeArray[j]); shown; } } } } private static String randomPlate(Random random, String prefix) { StringBuilder sb new StringBuilder(prefix.length() 5); sb.append(prefix); for (int i 0; i 5; i) { sb.append(PLATE_CHARS.charAt(random.nextInt(PLATE_CHARS.length()))); } return sb.toString(); } /** * 优化版布隆过滤器 * 1) m 取 2 的幂取模用位与 mask替代除法 * 2) 裸 long[] 位图替代 BitSetget/set 直写 * 3) Murmur3 x64_128 单次遍历字符串同时产出 h1/h2替代两次 FNV 全串扫描 * 4) 探测序列用累加替代 i*h2 乘法 * 非线程安全并发读写需换 AtomicLongArray */ static class FastBloomFilter implements Bloom { private static final long SEED 0x9747b28cL; private final long[] words; private final int mask; private final int k; private final long[] scratch new long[2]; FastBloomFilter(long expectedInsertions, double fpp) { double ln2 Math.log(2); long m (long) Math.ceil(-expectedInsertions * Math.log(fpp) / (ln2 * ln2)); int size Integer.highestOneBit((int) Math.max(64, m - 1)) 1; this.mask size - 1; this.k (int) Math.max(1, Math.round((double) size / expectedInsertions * ln2)); this.words new long[size 6]; } Override public void put(String value) { murmur128(value, SEED, scratch); long h1 scratch[0]; long h2 scratch[1] | 1; long combined h1; for (int i 0; i k; i) { combined h2; int idx (int) (combined mask); words[idx 6] | 1L idx; } } Override public boolean mightContain(String value) { murmur128(value, SEED, scratch); long h1 scratch[0]; long h2 scratch[1] | 1; long combined h1; for (int i 0; i k; i) { combined h2; int idx (int) (combined mask); if ((words[idx 6] (1L idx)) 0) { return false; } } return true; } /** Murmur3 x64_128每 16 字节8 个 UTF-16 字符一个块一次产出两个 64 位哈希 */ private static void murmur128(String s, long seed, long[] out) { long h1 seed; long h2 seed; final long c1 0x87c37b91114253d5L; final long c2 0x4cf5ad432745937fL; int len s.length(); int blocks len 3; int i 0; for (int b 0; b blocks; b, i 8) { long k1 pack4(s, i); long k2 pack4(s, i 4); k1 * c1; k1 Long.rotateLeft(k1, 31); k1 * c2; h1 ^ k1; h1 Long.rotateLeft(h1, 27); h1 h2; h1 h1 * 5 0x52dce729; k2 * c2; k2 Long.rotateLeft(k2, 33); k2 * c1; h2 ^ k2; h2 Long.rotateLeft(h2, 31); h2 h1; h2 h2 * 5 0x38495ab5; } long k1 0; long k2 0; int rem len - i; if (rem 4) { k2 packN(s, i 4, rem - 4); k2 * c2; k2 Long.rotateLeft(k2, 33); k2 * c1; h2 ^ k2; } if (rem 0) { k1 packN(s, i, Math.min(rem, 4)); k1 * c1; k1 Long.rotateLeft(k1, 31); k1 * c2; h1 ^ k1; } long lenBits (long) len 1; h1 ^ lenBits; h2 ^ lenBits; h1 h2; h2 h1; h1 fmix64(h1); h2 fmix64(h2); h1 h2; h2 h1; out[0] h1; out[1] h2; } private static long pack4(String s, int pos) { return (long) s.charAt(pos) | ((long) s.charAt(pos 1) 16) | ((long) s.charAt(pos 2) 32) | ((long) s.charAt(pos 3) 48); } private static long packN(String s, int pos, int chars) { long v 0; for (int c 0; c chars; c) { v | (long) s.charAt(pos c) (c 4); } return v; } private static long fmix64(long h) { h ^ h 33; h * 0xff51afd7ed558ccdL; h ^ h 33; h * 0xc4ceb9fe1a85ec53L; h ^ h 33; return h; } } /** * 简易布隆过滤器BitSet 2 个 64 位哈希派生 k 个位Kirsch-Mitzenmacher 技术。 * m -n·ln(p)/(ln2)^2k m/n·ln2 */ static class SimpleBloomFilter implements Bloom { private static final long SEED1 0x9E3779B97F4A7C15L; private static final long SEED2 0xC2B2AE3D27D4EB4FL; private final BitSet bits; private final long m; private final int k; SimpleBloomFilter(long expectedInsertions, double fpp) { double ln2 Math.log(2); this.m (long) Math.ceil(-expectedInsertions * Math.log(fpp) / (ln2 * ln2)); this.k (int) Math.max(1, Math.round((double) m / expectedInsertions * ln2)); this.bits new BitSet((int) m); } public void put(String value) { long h1 hash64(value, SEED1); long h2 hash64(value, SEED2) | 1; for (int i 0; i k; i) { bits.set((int) Math.floorMod(h1 (long) i * h2, m)); } } public boolean mightContain(String value) { long h1 hash64(value, SEED1); long h2 hash64(value, SEED2) | 1; for (int i 0; i k; i) { if (!bits.get((int) Math.floorMod(h1 (long) i * h2, m))) { return false; } } return true; } /** FNV-1a 64 位 Murmur3 fmix64 雪崩字符串分布均匀 */ private static long hash64(String s, long seed) { long h seed; for (int i 0; i s.length(); i) { h ^ s.charAt(i); h * 0x100000001b3L; } h ^ h 33; h * 0xff51afd7ed558ccdL; h ^ h 33; h * 0xc4ceb9fe1a85ec53L; h ^ h 33; return h; } long bitSize() { return m; } int hashCount() { return k; } /** 理论误判率 p ≈ (1 - e^(-k·n/m))^k */ double theoryFpp(long insertions) { return Math.pow(1 - Math.exp(-1.0 * k * insertions / m), k); } } }