临沂市平邑县建设局网站东莞市研发网站建设公司

临沂市平邑县建设局网站,东莞市研发网站建设公司,wordpress style不更新,高端网站服务范围一、布隆过滤器 1. 什么是布隆过滤器#xff1f; 布隆过滤器是一种空间效率极高的概率型数据结构#xff0c;核心作用是快速判断「一个元素是否存在于集合中」。它的特点可以总结为#xff1a; 说「元素不在」→ 100%准确#xff08;绝对没在集合里#xff09;#xff1b…一、布隆过滤器1. 什么是布隆过滤器布隆过滤器是一种空间效率极高的概率型数据结构核心作用是快速判断「一个元素是否存在于集合中」。它的特点可以总结为说「元素不在」→ 100%准确绝对没在集合里说「元素在」→ 可能误判有小概率其实不在极致省空间比传统Set/哈希表省几个数量级。2. 解决什么问题举两个典型场景缓存穿透用户查Redis中不存在的key请求会直接打到数据库拖垮数据库。用布隆过滤器先判如果布隆说“不存在”直接返回只有说“存在”才查Redis/数据库。爬虫去重爬10亿URL用Set存需要几十GB空间布隆过滤器只需要几百MB就能快速判断URL是否已爬过。3. 工作原理类比想象一个「空白笔记本」位数组每页只有0/1初始全0再准备3个「盖章器」哈希函数插入元素比如URLhttps://test.com用3个盖章器分别盖这个URL得到3个页码比如10、25、48把笔记本的10、25、48页都标为1查询元素同样用3个盖章器盖URL得到3个页码只要有一页是0 → 这个URL肯定没插过全是1 → 可能插过其他URL的盖章可能刚好覆盖这3页。二、布隆过滤器 原理详解1. 核心组件位数组Bit Array长度为m每个位只有0/1是布隆过滤器的核心存储k个独立哈希函数每个哈希函数能把任意输入如字符串映射到[0, m-1]的整数下标。2. 核心流程操作步骤插入1. 对元素调用k个哈希函数得到k个下标2. 把位数组对应下标位设为1查询1. 对元素调用k个哈希函数得到k个下标2. 检查所有下标位- 有一个0 → 元素不存在- 全1 → 元素可能存在3. 关键参数决定误判率n预期要插入的元素总数p期望的误判率比如0.011%m位数组长度m -n * ln(p) / (ln2)²n越大、p越小m越大k最优哈希函数数k (m/n) * ln2 ≈ 0.693*m/nk太大/太小都会升高误判率。4. 局限性无法删除元素位数组的位是共享的删除会影响其他元素存在误判只能降低无法消除需提前预估n和p预估不准会导致误判率升高或空间浪费。三、C实现布隆过滤器一步一步步骤1头文件与基础准备先引入必要的头文件定义辅助函数计算对数、哈希函数#includeiostream#includevector#includecmath#includestring#includealgorithm// ceil、round// 哈希函数1BKDR哈希经典字符串哈希staticuint64_tBKDRHash(conststd::stringstr){uint64_thash0;for(charc:str){hashhash*131c;// 131是常用质数可替换为31/13131等}returnhash;}// 哈希函数2AP哈希staticuint64_tAPHash(conststd::stringstr){uint64_thash0;for(size_t i0;istr.size();i){if(i%20){hash^(hash7)^c^(hash3);}else{hash^(~((hash11)^c^(hash5)));}}returnhash;}步骤2设计布隆过滤器类核心成员位数组、位数组长度m、哈希函数个数k核心方法构造函数计算m/k、插入、查询。classBloomFilter{private:std::vectorboolbits_;// 位数组vectorbool是特化类型省空间size_t bit_size_;// 位数组长度msize_t hash_num_;// 哈希函数个数kpublic:// 构造函数传入预期元素数n、期望误判率pBloomFilter(size_t expected_n,doublefalse_positive_p){// 步骤1计算最优的m位数组长度doubleln2log(2);bit_size_static_castsize_t(ceil(-expected_n*log(false_positive_p)/(ln2*ln2)));// 步骤2计算最优的k哈希函数个数hash_num_static_castsize_t(round((bit_size_/expected_n)*ln2));// 步骤3初始化位数组初始全0bits_.resize(bit_size_,false);// 打印参数方便调试std::cout布隆过滤器初始化完成std::endl;std::cout预期元素数expected_nstd::endl;std::cout期望误判率false_positive_pstd::endl;std::cout位数组长度mbit_size_std::endl;std::cout哈希函数个数khash_num_std::endl;}// 插入元素字符串类型voidinsert(conststd::stringkey){// 先计算两个基础哈希值组合出k个哈希值uint64_th1BKDRHash(key);uint64_th2APHash(key);// 循环k次计算每个哈希下标并置1for(size_t i0;ihash_num_;i){// 组合公式h h1 i*h2避免哈希函数重复uint64_tpos(h1i*h2)%bit_size_;bits_[pos]true;}}// 查询元素是否存在返回true可能存在false绝对不存在boolcontains(conststd::stringkey){uint64_th1BKDRHash(key);uint64_th2APHash(key);for(size_t i0;ihash_num_;i){uint64_tpos(h1i*h2)%bit_size_;// 只要有一个位是0说明绝对不存在if(!bits_[pos]){returnfalse;}}// 全1说明可能存在returntrue;}};步骤3测试代码验证插入、查询的效果观察误判/准确的情况intmain(){// 初始化布隆过滤器预期插入100个元素期望误判率1%BloomFilterbf(100,0.01);// 插入一批URLstd::vectorstd::stringurls{https://www.baidu.com,https://www.google.com,https://www.github.com,https://www.bilibili.com,https://www.zhihu.com};for(constautourl:urls){bf.insert(url);}// 测试1查询已插入的元素应该返回truestd::cout\n 查询已插入的元素 std::endl;for(constautourl:urls){std::couturl → (bf.contains(url)?可能存在:绝对不存在)std::endl;}// 测试2查询未插入的元素应该返回false或小概率误判为truestd::cout\n 查询未插入的元素 std::endl;std::vectorstd::stringnon_urls{https://www.tiktok.com,// 未插入https://www.taobao.com,// 未插入https://www.jd.com// 未插入};for(constautourl:non_urls){std::couturl → (bf.contains(url)?可能存在误判:绝对不存在)std::endl;}return0;}步骤4运行结果解释示例输出参数和结果可能略有差异布隆过滤器初始化完成 预期元素数100 期望误判率0.01 位数组长度m959 哈希函数个数k7 查询已插入的元素 https://www.baidu.com → 可能存在 https://www.google.com → 可能存在 https://www.github.com → 可能存在 https://www.bilibili.com → 可能存在 https://www.zhihu.com → 可能存在 查询未插入的元素 https://www.tiktok.com → 绝对不存在 https://www.taobao.com → 绝对不存在 https://www.jd.com → 绝对不存在已插入的元素全部返回「可能存在」符合预期未插入的元素全部返回「绝对不存在」无误会误判率低若未插入的元素返回「可能存在」就是误判调整m/k可降低概率。四、关键说明哈希函数选择示例用了BKDRAP哈希组合出k个哈希值也可以用其他哈希函数如DJB、SDBM核心是哈希函数要「均匀分布」避免哈希碰撞集中。vector的替代vector是比特级存储省空间但效率略低。如果追求性能可改用std::bitset编译期确定大小或手动管理字节数组如char[]按位操作。误判率优化若误判率过高可增大m位数组长度或调整k哈希函数个数或降低期望误判率p。通用化扩展示例只支持字符串可模板化类template typename T并为不同类型int、double等实现哈希函数。总结布隆过滤器的核心是「用空间换时间概率妥协」适合「允许小概率误判、追求极致空间效率」的场景。C实现的关键是按公式计算最优的m和k实现均匀分布的哈希函数对位数组进行高效的置1/检查操作。