布隆过滤器 & HyperLogLog

布隆过滤器（Bloom Filter）

由 m 位的位数组和 k 个独立哈希函数组成。插入时置位 k 个位置；查询时检查所有 k 个位。不存在假阴性；假阳性率 ε ≈ (1 - e^(-kn/m))^k，最优哈希函数数 k = (m/n) ln 2。

算法

1. 初始化：m 位全为 0 的位数组
2. insert(x)：计算 k 个哈希值 h1(x)…hk(x)，将 bits[hi(x) % m] 置 1
3. query(x)：计算相同的 k 个哈希；若所有对应位均为 1 返回 true，任一为 0 返回 false
4. 假阳性：k 个位恰好被其他元素置 1
5. 不支持删除：位一旦置 1 无法复原（需删除时改用计数布隆过滤器）

空间计算

• 最优哈希函数数：k = (m/n) × ln2 ≈ 0.693 × (m/n)
• 假阳性率：ε ≈ (1 - e^(-kn/m))^k
• 1% FPR 所需空间：m/n ≈ 9.6 bits（哈希表每指针 64 bits）
• 0.1% FPR 所需空间：m/n ≈ 14.4 bits

// Simple Bloom Filter with k hash functions using salted std::hash
class BloomFilter {
    vector<bool> bits;
    int m, k;
    vector<size_t> seeds;

    size_t hashAt(const string& s, size_t seed) const {
        size_t h = seed;
        for (char c : s) h = h * 31 + c;
        return h % m;
    }
public:
    BloomFilter(int m, int k) : bits(m, false), m(m), k(k) {
        for (int i = 0; i < k; i++) seeds.push_back(i * 2654435761ULL + 1);
    }
    void insert(const string& s) {
        for (int i = 0; i < k; i++) bits[hashAt(s, seeds[i])] = true;
    }
    bool query(const string& s) const {
        for (int i = 0; i < k; i++) if (!bits[hashAt(s, seeds[i])]) return false;
        return true; // possibly in set
    }
};

应用场景

• Apache Cassandra——查询前先查布隆过滤器，避免不必要的 SSTable 磁盘 I/O
• HBase——每个 HFile 一个布隆过滤器，get 时跳过无关 block
• Chrome 安全浏览——本地 URL 黑名单判断，无需请求服务器
• PostgreSQL amcheck——检测堆元组损坏

无法删除：标准布隆过滤器不支持删除。计数布隆过滤器将位替换为计数器（插入自增，删除自减）；Cuckoo Filter 支持删除且实际假阳性率更低。

HyperLogLog

用 O(m) 内存（m 个寄存器）估算大规模流中不同元素的数量（基数）。精度：±1.04/sqrt(m)。Redis PFCOUNT 仅用 12 KB 即可以 ±0.81% 误差估算任意规模的基数。

算法

1. 对每个元素计算 b 位哈希。用前 log2(m) 位作为寄存器下标 j
2. 统计剩余位的前导零个数：p = 第一个 1 的位置
3. 更新 register[j] = max(register[j], p)
4. 估算：E = alpha_m × m^2 × harmonic_mean(2^(-register[i]))

// Simplified HyperLogLog cardinality estimator
// Uses m=16 registers (4-bit index), counts leading zeros in hash
class HyperLogLog {
    static const int M = 16; // 2^4 registers
    int regs[M];
    double alpha = 0.673; // alpha_16

    // Simple hash: FNV-1a
    uint32_t fnv(uint32_t x) const {
        uint32_t h = 2166136261u;
        for (int i = 0; i < 4; i++) { h ^= (x & 0xFF); h *= 16777619u; x >>= 8; }
        return h;
    }
    int leadingZeros(uint32_t x, int bits) const {
        int cnt = 0;
        for (int i = bits-1; i >= 0; i--) { if ((x >> i) & 1) break; cnt++; }
        return cnt + 1;
    }
public:
    HyperLogLog() { fill(regs, regs + M, 0); }
    void add(uint32_t val) {
        uint32_t h = fnv(val);
        int j = h & (M - 1);        // lower 4 bits = register index
        uint32_t w = h >> 4;        // remaining 28 bits
        regs[j] = max(regs[j], leadingZeros(w, 28));
    }
    long long estimate() const {
        double sum = 0;
        for (int i = 0; i < M; i++) sum += pow(2.0, -regs[i]);
        double E = alpha * M * M / sum;
        return (long long)round(E);
    }
};

应用场景

• Redis PFADD / PFCOUNT——每个 HLL key 仅 12 KB，与基数无关
• Google BigQuery COUNT(DISTINCT ...)——使用改进版 HLL++
• Apache Spark approxCountDistinct
• 高流量网页的独立访客计数

精度 vs 内存：m=1024 个寄存器时标准误差约 3.25%。Redis 使用 m=16384 寄存器，精度 0.81%，仅需 12 KB——远少于存储数十亿元素所需的哈希集合。