一、什么是布隆过滤器
1、简介
布隆过滤器是一个很长的二进制向量和一系列随机映射函数。可以用于检索一个元素是否在一个集合中。。理解为SET集合。
布隆过滤器其内部维护了一个全为 0 的 bit 数组，需要说明的是，布隆过滤器有一个误判的概念，误判率越低，则数组越长，所占空间越大。误判率越高则数组越小，所占的空间多少。（关于误判后面会讲到）
布隆过滤器的优点：
时间复杂度低，增加和查询元素的时间复杂为O(N)，（N为哈希函数的个数，通常情况比较小）
保密性强，布隆过滤器不存储元素本身
存储空间小，如果允许存在一定的误判，布隆过滤器是非常节省空间的（相比其他数据结构如Set集合）
布隆过滤器的缺点：
有点一定的误判率，但是可以通过调整参数来降低
无法获取元素本身
很难删除元素
2、使用场景
1. 数据去重：
场景描述： 在一些需要对大量数据进行去重的场景，例如用户提交表单、数据同步等，布隆过滤器可以迅速判断某个数据是否已存在，避免重复插入。
应用实例： 在用户提交表单时，使用布隆过滤器判断该用户是否已经提交过相同的数据，从而防止重复提交。
2. 缓存穿透问题的解决：
场景描述：当缓存中不存在某个数据，而用户频繁查询该数据时，可能导致缓存穿透问题。布隆过滤器可以在缓存层之前迅速过滤掉不存在的数据，减轻数据库的压力。
应用实例： 在缓存中存储热门商品的ID列表，并使用布隆过滤器判断某个商品ID是否存在于列表中，从而决定是否查询数据库获取数据。
3. 爬虫数据去重：
场景描述： 在爬虫应用中，避免重复抓取相同的数据是一项关键任务。布隆过滤器可以帮助爬虫快速判断某个URL是否已经被抓取过。
应用实例： 在爬虫系统中，使用布隆过滤器存储已抓取的URL，以避免重复请求同一URL。
4. 安全黑名单：
场景描述： 在需要防范恶意攻击或恶意请求的场景中，布隆过滤器可以用于快速判断某个IP地址或请求是否在黑名单中。
应用实例： 在Web应用中，使用布隆过滤器维护一份IP黑名单，快速拦截恶意请求。
5. URL访问记录：
场景描述： 对于某些需要记录用户访问记录的应用，布隆过滤器可以用于判断某个URL是否已经被记录，避免重复记录。
应用实例： 在网站访问日志记录中，使用布隆过滤器判断某个URL是否已经被记录，防止访问记录过于庞大。
6. 缓存预热：
场景描述： 在系统启动时，通过布隆过滤器判断某些热门数据是否在缓存中，可以加速系统的启动过程。
应用实例： 在SpringBoot应用启动时，使用布隆过滤器判断热门商品的ID是否在缓存中，并提前加载到缓存中，减少冷启动时的缓存穿透问题。
3、布隆过滤器的原理
3.1 数据结构
以Redis中的布隆过滤器实现为例，Redis中的布隆过滤器底层是一个大型位数组（二进制数组）+多个无偏hash函数。
一个大型位数组（二进制数组）：
多个无偏hash函数：无偏hash函数就是能把元素的hash值计算的比较均匀的hash函数，能使得计算后的元素下标比较均匀的映射到位数组中。
3.2 增加元素
往布隆过滤器增加元素，添加的key需要根据k个无偏hash函数计算得到多个hash值，然后对数组长度进行取模得到数组下标的位置，然后将对应数组下标的位置的值置为1
通过k个无偏hash函数计算得到k个hash值
依次取模数组长度，得到数组索引
将计算得到的数组索引下标位置数据修改为1
例如，key = Liziba，无偏hash函数的个数k=3，分别为hash1、hash2、hash3。三个hash函数计算后得到三个数组下标值，并将其值修改为1.
如图所示：
3.3 查询元素
布隆过滤器最大的用处就在于判断某样东西一定不存在或者可能存在，而这个就是查询元素的结果。其查询元素的过程如下：
通过k个无偏hash函数计算得到k个hash值
依次取模数组长度，得到数组索引
判断索引处的值是否全部为1，如果全部为1则存在（这种存在可能是误判），如果存在一个0则必定不存在
4、关于误判
假设，根据误判率，我们生成一个 10 位的 bit 数组，以及 2 个 hash 函数 f1 和 f2，如下图所示：生成的数组的位数 和 hash 函数的数量。这里我们不用去关心如何生成的，因为有数学论文进行验证。
然后我们输入一个集合，集合中包含 N1 和 N2，我们通过计算 f1(N1) = 2，f2(N1) = 5，则将数组下标为 2 和下标为 5 的位置设置成 1，就得到了下图。
同理，我们再次进行计算 N2的值， f1(N2) = 3，f2(N2) = 6。得到如下所示的图
这个时候，假设我们有第三个数 N3 过来了，需要判断 N3 是否在集合 [N1,N2] 中，需要做的操作就是，使用 f1 和 f2 计算出数组中的地址
若值恰巧都位于上图的红色位置，我们认为 N3在集合 [N1,N2] 中
-若值有一个不位于上图的红色部分，我们认为N3不在集合 [N1,N2] 中
这就是布隆过滤器的计算原理。
代码实现
#include <stdlib.h> #include <string.h> #include <math.h> #include <stdint.h> #include <stddef.h> // 布隆过滤器结构体 typedef struct { uint8_t* bit_array; // 位数组 size_t bit_array_size; // 位数组大小（字节数） size_t num_bits; // 总位数 int num_hash_funcs; // 哈希函数数量 size_t element_count; // 已插入元素数量 } BloomFilter; // 函数声明 BloomFilter* bloom_create(size_t num_bits, int num_hash_funcs); void bloom_destroy(BloomFilter* filter); int bloom_add(BloomFilter* filter, const char* element); int bloom_contains(const BloomFilter* filter, const char* element); size_t bloom_count(const BloomFilter* filter); void bloom_reset(BloomFilter* filter); double bloom_false_positive_rate(const BloomFilter* filter, size_t expected_elements); // 辅助哈希函数1 - FNV-1a static uint32_t hash1(const char* str) { uint32_t hash = 2166136261u; while (*str) { hash ^= (uint8_t)(*str); hash *= 16777619u; str++; } return hash; } // 辅助哈希函数2 - DJB2 static uint32_t hash2(const char* str) { uint32_t hash = 5381; while (*str) { hash = ((hash << 5) + hash) + (uint8_t)(*str); // hash * 33 + c str++; } return hash; } // 使用双哈希法生成k个哈希值 static uint32_t get_hash(const char* str, int i, uint32_t max_bits) { uint32_t h1 = hash1(str); uint32_t h2 = hash2(str); uint32_t combined = h1 + i * h2;// 双哈希：h1 + i * h2 // 取模确保在范围内 return combined % max_bits; } // 创建布隆过滤器 BloomFilter* bloom_create(size_t num_bits, int num_hash_funcs) { if (num_bits == 0 || num_hash_funcs <= 0) { return NULL; } BloomFilter* filter = (BloomFilter*)malloc(sizeof(BloomFilter)); if (!filter) { return NULL; } // 计算需要的字节数（向上取整） size_t byte_size = (num_bits + 7) / 8; filter->bit_array = (uint8_t*)calloc(byte_size, sizeof(uint8_t)); if (!filter->bit_array) { free(filter); return NULL; } filter->bit_array_size = byte_size; filter->num_bits = num_bits; filter->num_hash_funcs = num_hash_funcs; filter->element_count = 0; return filter; } // 销毁布隆过滤器 void bloom_destroy(BloomFilter* filter) { if (filter) { if (filter->bit_array) { free(filter->bit_array); } free(filter); } } // 添加元素到布隆过滤器 int bloom_add(BloomFilter* filter, const char* element) { if (!filter || !element) { return 0; } size_t len = strlen(element); if (len == 0) { return 0; } // 对每个哈希函数设置相应的位 for (int i = 0; i < filter->num_hash_funcs; i++) { uint32_t hash = get_hash(element, i, filter->num_bits); // 计算字节位置和位偏移 size_t byte_pos = hash / 8; uint8_t bit_pos = hash % 8; // 设置位 filter->bit_array[byte_pos] |= (1 << bit_pos); } filter->element_count++; return 1; } // 检查元素是否可能在布隆过滤器中 int bloom_contains(const BloomFilter* filter, const char* element) { if (!filter || !element) { return 0; } size_t len = strlen(element); if (len == 0) { return 0; } // 检查所有哈希函数对应的位是否都被设置 for (int i = 0; i < filter->num_hash_funcs; i++) { uint32_t hash = get_hash(element, i, filter->num_bits); // 计算字节位置和位偏移 size_t byte_pos = hash / 8; uint8_t bit_pos = hash % 8; // 检查位是否被设置 if (!(filter->bit_array[byte_pos] & (1 << bit_pos))) { return 0; // 有任何一位没设置，肯定不存在 } } return 1; // 所有位都被设置，可能存在（可能误判） } // 获取已插入元素数量（估算） size_t bloom_count(const BloomFilter* filter) { return filter ? filter->element_count : 0; } // 重置布隆过滤器（清空所有位） void bloom_reset(BloomFilter* filter) { if (filter && filter->bit_array) { size_t byte_size = filter->bit_array_size; memset(filter->bit_array, 0, byte_size); filter->element_count = 0; } } // 计算理论误判率 double bloom_false_positive_rate(const BloomFilter* filter, size_t expected_elements) { if (!filter || expected_elements == 0) { return 1.0; } double k = filter->num_hash_funcs; double m = filter->num_bits; double n = expected_elements; // 误判率公式: (1 - e^(-k*n/m))^k double exponent = -k * n / m; return pow(1 - exp(exponent), k); }
