企业官网建设流程全解析

微信平台与微网站开发,宁波北仑做公司网站,建什么网站,域名备案的价格一、什么是布隆过滤器 1、简介 布隆过滤器是一个很长的二进制向量和一系列随机映射函数。可以用于检索一个元素是否在一个集合中。。理解为SET集合。 布隆过滤器其内部维护了一个全为 0 的 bit 数组#xff0c;需要说明的是#xff0c;布隆过滤器有一个误判的概念#xff0…一、什么是布隆过滤器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函数的个数k3分别为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) 2f2(N1) 5则将数组下标为 2 和下标为 5 的位置设置成 1就得到了下图。同理我们再次进行计算 N2的值 f1(N2) 3f2(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); }