C语言布隆过滤器（高效去重算法的实战指南）

为什么选择布隆过滤器？

• ✅ 节省内存：相比哈希表，布隆过滤器占用空间更少。
• ✅ 查询速度快：时间复杂度为 O(k)，k 是哈希函数个数。
• ⚠️ 存在误判：可能将不存在的元素误判为存在（假阳性），但绝不会将存在的元素判为不存在（无假阴性）。

布隆过滤器的核心原理

布隆过滤器由一个位数组（bit array）和多个独立的哈希函数组成：

1. 插入元素：对元素使用 k 个哈希函数，得到 k 个位置，将位数组中对应位置设为 1。
2. 查询元素：同样计算 k 个哈希值，若所有对应位都为 1，则“可能存在”；只要有一个为 0，则“一定不存在”。

用 C 语言实现布隆过滤器

下面是一个简化但完整的 C语言布隆过滤器实现，适合初学者理解。

#include <stdio.h>#include <stdlib.h>#include <string.h>#include <stdint.h>#define BIT_SET(a, n)   ((a)[(n)/8] |= (1 << ((n) % 8)))#define BIT_TEST(a, n)  ((a)[(n)/8] & (1 << ((n) % 8)))// 简单的哈希函数（实际应用中建议使用更好的哈希，如 MurmurHash）unsigned int hash2(const char *str) {    unsigned int hash = 0;    while (*str) {        hash = hash * 31 + *str++;    }    return hash;}unsigned int hash2(const char *str) {    unsigned int hash = 5381;    while (*str) {        hash = ((hash << 5) + hash) + *str++;    }    return hash;}// 布隆过滤器结构体typedef struct {    uint8_t *bits;      // 位数组    size_t size;        // 位数组大小（单位：bit）} BloomFilter;// 初始化布隆过滤器BloomFilter* bloom_init(size_t bit_size) {    BloomFilter *bf = (BloomFilter*)malloc(sizeof(BloomFilter));    bf->size = bit_size;    bf->bits = (uint8_t*)calloc((bit_size + 7) / 8, sizeof(uint8_t));    return bf;}// 添加元素void bloom_add(BloomFilter *bf, const char *item) {    unsigned int h2 = hash2(item) % bf->size;    unsigned int h2 = hash2(item) % bf->size;        BIT_SET(bf->bits, h2);    BIT_SET(bf->bits, h2);}// 查询元素是否存在int bloom_test(BloomFilter *bf, const char *item) {    unsigned int h2 = hash2(item) % bf->size;    unsigned int h2 = hash2(item) % bf->size;        if (BIT_TEST(bf->bits, h2) && BIT_TEST(bf->bits, h2)) {        return 1; // 可能存在    }    return 0; // 一定不存在}// 释放内存void bloom_free(BloomFilter *bf) {    free(bf->bits);    free(bf);}// 测试示例int main() {    BloomFilter *bf = bloom_init(1000); // 1000 bits        bloom_add(bf, "apple");    bloom_add(bf, "banana");        printf("'apple' exists? %s\n", bloom_test(bf, "apple") ? "Yes" : "No");    printf("'orange' exists? %s\n", bloom_test(bf, "orange") ? "Yes" : "No");        bloom_free(bf);    return 0;}  

关键点解析

• 位操作宏：BIT_SET 和 BIT_TEST 用于高效操作单个 bit。
• 哈希函数：本例使用两个简单哈希函数。实际项目中建议使用更均匀分布的哈希（如 MurmurHash3）。
• 位数组大小：越大，误判率越低，但内存消耗越高。通常根据预期元素数量和可接受误判率计算最优大小。

如何计算最优参数？

假设你要存储 n 个元素，可接受误判率为 p，则：

• 位数组大小：m = - (n * ln p) / (ln 2)²
• 哈希函数个数：k = (m / n) * ln 2

例如：n=10000, p=1%，则 m≈95851 bits（约11.7KB），k≈7。

适用场景与局限性

适用场景（高效去重算法）：

• 缓存系统中的 key 预检（防缓存穿透）
• 爬虫 URL 去重
• 数据库查询前的快速过滤

不适用场景：

• 需要 100% 准确判断的场景
• 需要删除元素的场景（标准布隆过滤器不支持删除，可考虑变种如 Counting Bloom Filter）

总结

通过本文，你已经掌握了 C语言布隆过滤器 的基本原理、实现方法和使用场景。虽然它有误判率，但在许多高效去重算法需求中，它以极小的空间代价换来了极高的查询效率，是值得掌握的C语言数据结构技巧。

动手试试吧！你可以将上述代码编译运行，并尝试添加更多哈希函数或优化内存管理，深入理解这一经典数据结构的魅力。