11、位操作与哈希：用位运算实现简单的布隆过滤器

布隆过滤器，这个名字听起来挺唬人的。说白了，它就是一个用位数组 + 多个哈希函数实现的「快速判断某个元素是否在集合里」的数据结构。

我最早接触布隆过滤器是在做嵌入式日志关键词过滤的时候。那时候内存只有几十KB，却要快速判断一条日志是否包含敏感词。用哈希表？存不下。用字符串匹配？太慢。后来我想到布隆过滤器——用位操作和哈希，完美解决。

布隆过滤器的核心思想

布隆过滤器不存数据本身，只存数据的「指纹」。它用多个哈希函数把数据映射到位数组的多个位上。判断时，只要检查这些位是否全为1。

• 优点：空间效率极高，查询速度极快（O(k)，k是哈希函数个数）
• 缺点：有误判率（可能把不在集合中的元素误判为存在），且不能删除元素

用位运算实现布隆过滤器

嵌入式环境里，我们通常用 unsigned char 数组来模拟位数组。每个字节8个位，用位操作来置位和检测。

先定义基本结构：

#include <stdint.h>
#include <string.h>

#define BLOOM_SIZE  256   // 位数组大小（字节）
#define HASH_NUM    3     // 哈希函数个数

typedef struct {
    unsigned char bits[BLOOM_SIZE];
} BloomFilter;

这里 BLOOM_SIZE 是256字节，也就是2048个位。你可以根据实际内存调整。

位操作的核心函数

我们需要两个基本操作：置位和检测。这两个操作完全依赖位运算。

// 将第 n 位置1
static inline void set_bit(unsigned char *bits, int n) {
    bits[n >> 3] |= (1 << (n & 7));
}

// 检测第 n 位是否为1
static inline int test_bit(unsigned char *bits, int n) {
    return (bits[n >> 3] >> (n & 7)) & 1;
}

这里 n >> 3 相当于 n / 8，找到字节索引。n & 7 相当于 n % 8，找到位偏移。用移位代替乘除，效率更高。

哈希函数的选择

布隆过滤器需要多个哈希函数。但实际工程中，我们通常用同一个哈希函数 + 不同的种子来模拟多个哈希函数。

我推荐使用 Jenkins 的 one-at-a-time 哈希，简单且分布均匀：

// Jenkins one-at-a-time 哈希
static uint32_t hash_jenkins(const char *key, size_t len, uint32_t seed) {
    uint32_t hash = seed;
    for (size_t i = 0; i < len; i++) {
        hash += key[i];
        hash += (hash << 10);
        hash ^= (hash >> 6);
    }
    hash += (hash << 3);
    hash ^= (hash >> 11);
    hash += (hash << 15);
    return hash;
}

用不同的 seed 值（比如 0, 1, 2）调用这个函数，就得到了3个不同的哈希值。

插入与查询

插入操作：对每个哈希函数计算位置，然后置位。

void bloom_insert(BloomFilter *bf, const char *data, size_t len) {
    for (int i = 0; i < HASH_NUM; i++) {
        uint32_t h = hash_jenkins(data, len, i * 73 + 17);
        int bit_pos = h % (BLOOM_SIZE * 8);
        set_bit(bf->bits, bit_pos);
    }
}

查询操作：对每个哈希函数检测位置，只要有一个为0就返回0（不存在）。

int bloom_check(BloomFilter *bf, const char *data, size_t len) {
    for (int i = 0; i < HASH_NUM; i++) {
        uint32_t h = hash_jenkins(data, len, i * 73 + 17);
        int bit_pos = h % (BLOOM_SIZE * 8);
        if (!test_bit(bf->bits, bit_pos)) {
            return 0;  // 一定不存在
        }
    }
    return 1;  // 可能存在（有误判风险）
}

完整示例：过滤重复的传感器ID

我在一个物联网项目中用过这个。传感器每隔几秒上报数据，数据包里有设备ID。我们需要过滤掉已经处理过的ID，避免重复处理。

#include <stdio.h>

int main() {
    BloomFilter bf;
    memset(&bf, 0, sizeof(bf));

    // 模拟一批设备ID
    const char *ids[] = {
        "sensor_001", "sensor_002", "sensor_003",
        "sensor_001",  // 重复的
        "sensor_004", "sensor_002"   // 重复的
    };
    int n = sizeof(ids) / sizeof(ids[0]);

    for (int i = 0; i < n; i++) {
        if (bloom_check(&bf, ids[i], strlen(ids[i]))) {
            printf("跳过重复ID: %s\n", ids[i]);
        } else {
            printf("处理新ID: %s\n", ids[i]);
            bloom_insert(&bf, ids[i], strlen(ids[i]));
        }
    }
    return 0;
}

输出结果：

处理新ID: sensor_001
处理新ID: sensor_002
处理新ID: sensor_003
跳过重复ID: sensor_001
处理新ID: sensor_004
跳过重复ID: sensor_002

布隆过滤器的参数选择

参数选不好，误判率会很高。我踩过这个坑。有一次我把位数组设得太小，结果误判率飙到30%，排查了半天才发现是参数问题。

这里给出经验公式：

参数	含义	推荐值
m	位数组大小（位数）	m = -n * ln(p) / (ln2)^2
k	哈希函数个数	k = (m/n) * ln2
n	预期插入元素数量	根据业务估算
p	期望误判率	通常 0.01 ~ 0.001

举个例子：如果预期插入1000个元素，希望误判率1%，那么：

• m ≈ -1000 * ln(0.01) / (0.48) ≈ 9585 位 ≈ 1198 字节
• k ≈ (9585/1000) * 0.693 ≈ 6.6，取整为7个哈希函数

布隆过滤器的局限性

布隆过滤器不是万能的。它有两个硬伤：

1. 不能删除元素：因为多个元素可能共享同一个位，清零会导致误判。如果要支持删除，需要用 Counting Bloom Filter（每个位变成计数器）。
2. 有误判率：这是空间换精度的代价。如果业务要求零误判，布隆过滤器不适合。

另外，布隆过滤器对哈希函数的质量要求很高。如果哈希函数分布不均匀，位数组很快就会被填满，误判率飙升。

SVG流程图：布隆过滤器工作原理

总结

布隆过滤器是位操作和哈希结合的经典案例。它用极小的内存代价，换来了极快的查询速度。在嵌入式场景中，它特别适合做：

• 重复数据过滤（如传感器ID去重）
• 缓存穿透防护（先判断数据是否在缓存中）
• 恶意URL过滤（先快速判断是否在黑名单中）

嗯，布隆过滤器就讲到这里。记住：参数要算，哈希要选好，位操作要写对。这三个点做到位，你的布隆过滤器就能稳定运行很久。