小叶-duck个人主页❄️个人专栏《Data-Structure-Learning》《C入门到进阶自我学习过程记录》《Linux系统从入门到实践》《Linux网络从入门到实践》《Qt 方寸极境》 《MySQL》✨未择之路不须回头已择之路纵是荆棘遍野亦作花海遨游目录前言一、引出位图1.1 方案对比分析方案 1暴力遍历方案 2排序 二分查找方案 3位图 BitMap最终方案1.2 位图原理1.3 位图核心 API 实现位运算1.3.1 set (x)将 x 对应的 bit 置 1标记数字存在1.3.2 reset (x)将 x 对应的 bit 置 0标记数字不存在1.3.3 test (x)判断 x 对应的 bit 是否为 1查询数字是否存在1.3.4 bitmap.hpp 代码总览1.3.5 测试代码示例1.4 补充位运算与大小端1.5 位图的优缺点1.6 位图相关面试考题二、布隆过滤器2.1 什么是布隆过滤器2.1.1 背景引入2.1.2 布隆过滤器定义2.1.3 核心思路2.1.4 误判原理说明2.2 数学模型与误判率推导(了解即可)2.3 布隆过滤器代码实现2.3.1 BloomFilter.hpp 代码总览2.3.2 测试代码示例2.4 布隆过滤器删除问题2.5 布隆过滤器应用场景三、海量数据处理问题3.1 问题一方案 1布隆过滤器方案方案 2哈希切分分桶3.2 问题二解题思路哈希切分 局部统计结束语前言在哈希相关内容的学习中我们已经掌握了基础哈希表的底层原理与实现思路。但面对海量数据场景传统哈希结构会暴露出内存占用过高的问题很多面试场景里的大数据算法题也无法直接使用普通哈希表求解。本篇加餐内容就从位图 BitMap 开始对比多种数据查找方案理解如何用单个 bit 位标记数据存在与否并用 C 完成位图的完整代码实现。接着在此基础上延伸学习布隆过滤器理解它的构造思路、误判原理与适用场景。最后结合两道经典海量数据面试题对比布隆过滤器、哈希切分等不同解题方案学会在大数据场景下选择合适的算法。一、引出位图原题给 40 亿个不重复无符号整数未排序。给定一个无符号整数快速判断该数是否存在集合中。1.1 方案对比分析方案 1暴力遍历思路逐个比较复杂度O(N)缺点40 亿数据量速度极慢不可行方案 2排序 二分查找思路先排序再二分查找复杂度排序 O(N log N)单次查找 O(log N)致命问题40 亿 uint 占用空间(40 * 10^8 * 4B 16GB)无法一次性全部载入内存只能放磁盘二分查找只支持内存中连续有序数组磁盘上有序文件无法直接二分方案 3位图 BitMap最终方案核心思想一个整数是否存在只用 1 个 bit 标记存在记 1不存在记 0空间压缩原本 4 字节存 1 个整数 → 1bit 存 1 个整数空间缩小至原来的 1/3240 亿数字所需内存(40 * 10^8 / 8 500MB)可以放入内存1.2 位图原理位图本质直接定址的哈希表整数的值直接映射成 bit 位下标。 C/C 没有单独 bit 类型借用int/uint32_t这类整型数组存储一个uint32_t保存 32 个 bit 标记数组下标i第几个 32 位整型位内偏移j这个整型内部的第几个 bit映射公式i x / 32; // 找到对应数组元素下标 j x % 32; // 在该32位整数内对应的bit位置注意bit 高低位是数值权重和大小端无关。1.3 位图核心 API 实现位运算操作1 j生成掩码左移比特向高位移动低位补 01.3.1 set (x)将 x 对应的 bit 置 1标记数字存在void set(size_t x) { size_t i x / 32; size_t j x % 32; _bs[i] | (1 j); }原理按位或|掩码对应 bit 为 1其余 0或运算只把目标 bit 置 1其他位保持不变。1.3.2 reset (x)将 x 对应的 bit 置 0标记数字不存在void reset(size_t x) { size_t i x / 32; size_t j x % 32; _bs[i] ~(1 j); }原理1 j得到只有第 j 位是 1 的掩码~按位取反 → 掩码只有第 j 位是 0其余全 1按位与目标 bit 和 0 相与变成 0其余 bit 和 1 相与保持不变1.3.3 test (x)判断 x 对应的 bit 是否为 1查询数字是否存在bool test(size_t x) { size_t i x / 32; size_t j x % 32; return _bs[i] (1 j); }原理按位与掩码仅目标 bit 为 1。如果结果非 0说明该 bit 是 1数字存在结果为 0 代表不存在。1.3.4 bitmap.hpp 代码总览#include iostream #include vector namespace bit { templatesize_t N class bitmap { public: bitmap() { _bm.resize(N / 32 1); //相当于每32个树作为一个数一个整形4字节32比特位 } //x的位置映射的比特位标记成1 void set(int n) { int x n / 32; //获取该比特位是在哪个数中 int y n % 32; //获取该比特位是在该数的哪个位置 _bm[x] | (1 y); //按位或(1 y)就可以将对应位置的比特位置成1 } //x的位置映射的比特位标记成0 void reset(int n) { int x n / 32; //获取该比特位是在哪个数中 int y n % 32; //获取该比特位是在该数的哪个位置 _bm[x] (~(1 y)); //按位与(1 y)的取反就可以将对应位置的比特位置成0 } bool test(int n) { int x n / 32; //获取该比特位是在哪个数中 int y n % 32; //获取该比特位是在该数的哪个位置 return _bm[x] (1 y); //返回真对应的比特位为1返回假对应的比特位为0 } private: std::vectorint _bm; }; }1.3.5 测试代码示例int main() { bit::bit_set100 bs; bs.set(32); bs.set(33); bs.reset(33); bs.set(34); cout bs.test(31) endl; // 0 cout bs.test(32) endl; // 1 cout bs.test(33) endl; // 0 cout bs.test(34) endl; // 1 cout bs.test(35) endl; // 0 return 0; }1.4 补充位运算与大小端核心结论移位、位运算本身和大小端无关。移位操作发生在 CPU 寄存器内基于比特权重运算大小端只负责内存与寄存器之间多字节数据的字节排布。大小端作用只改变多字节整数在内存中的字节存放顺序不会反转单个字节内部的 bit 顺序。执行流程内存数据 → CPU 按本机大小端规则组装成寄存器里的整数 → 在寄存器执行移位 / 位运算 → 运算完成后再按大小端拆成字节写回内存。举个例子uint16_t val 0x12340x1234数学上二进制bit15 bit14 ... bit8 | bit7 ... bit0 0001 0010 0011 0100 高位(bit15权重2^15) 低位(bit0权重2^0)bit15权重最大高位bit0权重最小低位✅ 小端机器内存存放内存地址由低→高内存低地址存低字节高地址存高字节(相当于低字节对应低地址高字节对应高地址)内存0x340x12低地址 → 高地址CPU 做读取流程从内存读出两个字节0x34、0x12小端规则组装0x12 8 | 0x34→ 得到寄存器里面的值0x1234在寄存器里这个数就是0001 0010 0011 0100执行val 1寄存器内整体左移得到0x2468二进制0010 0100 0110 1000✅ 大端机器内存存放内存地址由低→高内存低地址存高字节(相当于低字节对应高地址高字节对应低地址)内存0x120x34低地址 → 高地址CPU 读取流程读出两个字节0x12、0x34大端规则组装0x12 8 | 0x34→寄存器里面的值同样是0x1234寄存器里二进制还是0001 0010 0011 0100val 1同样得到0x2468结论不管大端小端val 1的结果完全一样也就是说BitMap 的 set/test 逻辑跨平台结果不变误区纠正不要误以为内存字节顺序反转会改变 bit 的权重编号和移位方向。1.5 位图的优缺点优点极高的空间压缩率用 1bit 标记一个整数相比用 4 字节 uint 存储空间压缩至原来 1/32海量数据场景下内存占用大幅降低能够把几十亿数据的标记信息放进内存。增、删、查时间复杂度 O (1)set、reset、test 都是固定次数的位运算和数据总量无关查找速度极快。天然支持集合运算多个位图之间可以直接用位运算快速求交集、并集|、差集适合大数据集合比对。顺序遍历方便按 bit 顺序遍历可直接拿到所有存在的数字天然有序输出。缺点仅支持整型数据只能对整数做映射浮点数、字符串无法直接使用位图。空间开销取决于数值范围不是数据个数空间由最大数值决定不是元素数量。如果数值范围极大、数据极其稀疏会浪费大量内存。例只有 2 个数字 0 和 42 亿仍然需要 500MB 位图。无法直接存储附加信息基础位图只能标记「存在 / 不存在」如果要统计出现次数需要扩展成多 bit 计数位图。数值偏移问题若存在负数需要做偏移映射增加编码复杂度。1.6 位图相关面试考题题目 1给定 100 亿个整数设计算法找到只出现一次的整数核心前置理解有些人第一眼看到要 100 亿个整数就下意识以为要开辟 100 亿比特位但是我们知道即使无符号全 f 也就 42 亿多。 这 100 亿如何开辟呢其实还是开辟全 f 也就是 42 亿就行了。原因就在于 100 亿个整数并不是值会有 100 亿因为无符号整数的最大值就是 42 亿多。 也就是说 100 亿个整数中一定存在重复的数但是不影响我们只需要开辟 42 亿多个比特位即可开辟空间清楚后如何找到只出现一次的整数提供两种方案1把两个比特位看成一个整体00表示所对应的数没有出现01表示所对应的数出现一次10表示所对应的数出现两次及以上2依旧使用上面的位图但是借助两张位图同样的位置进行判断00表示所对应的数没有出现01表示所对应的数出现一次10表示所对应的数出现两次11表示所对应的数出现两次以上选用第二种方法实现更简单双位图 double bitmap2 个 bit 记录一个数字出现次数筛选出编码为01的数字。templatesize_t N class double_bitmap { public: void set(int n) { bool bit1 _bm1.test(n); bool bit2 _bm2.test(n); if (!bit1 !bit2) { // 00 → 01第一次出现 _bm1.reset(n); _bm2.set(n); } else if (!bit1 bit2) { // 01 → 10第二次出现 _bm1.set(n); _bm2.reset(n); } else { //10 / 11 →11三次及以上 _bm1.set(n); _bm2.set(n); } } int get_count(int n) { bool bit1 _bm1.test(n); bool bit2 _bm2.test(n); if (!bit1 !bit2) return 0; else if (!bit1 bit2) return 1; else if (bit1 !bit2) return 2; else return 3; // 3次 } private: bit::bit_setN _bm1; bit::bit_setN _bm2; }; // 测试代码 int main() { int test[] {1,1,3,4,5,5,6,6,8,10,11,15,19,100,110,110}; bit::double_bitmap200 dbp; for (auto e : test) { dbp.set(e); } for (int i 0; i 200; i) { if (dbp.get_count(i) 1) { std::cout i std::endl; } } return 0; }结果演示题目 2两个文件分别有 100 亿个整数只有 1G 内存如何找到两个文件的交集思路读取第一个文件全部整数存入位图 A读取第二个文件逐个数字去位图 A 中 testtest 返回 true说明该数字在两个文件都存在即为交集。优化也可以构建两个位图两个位图做按位运算结果中 bit1 的就是交集。题目 3一个文件有 100 亿个整数1G 内存找出出现次数不超过 2 次的所有整数思路使用双位图 double_bitmap遍历所有数字完成计数遍历位图筛选出编码为011 次和102 次的数字。二、布隆过滤器2.1 什么是布隆过滤器2.1.1 背景引入位图有一个明显限制只能处理整型数据。如果业务需要对海量字符串、URL 等非整型数据做存在性判断直接使用红黑树、哈希表会占用巨大内存此时就适合使用布隆过滤器。2.1.2 布隆过滤器定义布隆过滤器由 Burton Howard Bloom 在 1970 年提出是紧凑型、概率型的数据结构。核心能力高效完成插入与成员查询查询结论元素一定不存在或者可能存在底层原理利用多个独立哈希函数把原始 key 映射到位图的多个 bit 位上牺牲 “完全精确” 换取极致的空间节省与查询速度。2.1.3 核心思路对 key 做哈希计算转为哈希整数再映射到位图的 bit 下标。如果只用单个哈希函数映射 1 个 bit哈希冲突概率很高。解决方案使用多个不同哈希函数映射到多个 bit 位以此降低冲突概率。和哈希表的本质区别哈希表会存储原始 key能通过比较 key 解决哈希冲突 布隆过滤器不存储原始 key只标记映射对应的 bit 位无法彻底消除冲突只能降低冲突概率。查询语义判断 key不存在结果 100% 准确判断 key存在只是概率性结论存在误判假阳性2.1.4 误判原理说明不同 key 经过哈希映射后有可能恰好命中完全相同的一组 bit 位置。即使某个 key 从来没有插入过滤器若它对应的全部 bit 位都被其他已经插入的元素提前置为 1就会产生误判过滤器会误以为该 key 已经存在。重点多哈希映射只能降低误判概率无法彻底消除误判。2.2 数学模型与误判率推导(了解即可)2.3 布隆过滤器代码实现2.3.1 BloomFilter.hpp 代码总览#pragma once #include bitmap.h #include string #include ctime #include cmath // BKDR哈希仿函数 // 算法在Brian Kernighan与Dennis Ritchie的《The C Programming Language》一书被展示而得名 // 简单快捷的字符串hash算法Java早期字符串Hash思想同源累乘因子选用31 struct HashFuncBKDR { size_t operator()(const std::string s) { size_t hash 0; for (auto ch : s) { hash * 31; hash ch; } return hash; } }; // AP哈希仿函数 // 由Arash Partow发明的hash算法利用位运算奇偶字符做不同的异或移位处理分散hash值 struct HashFuncAP { size_t operator()(const std::string s) { size_t hash 0; for (size_t i 0; i s.size(); i) { if ((i 1) 0) // 偶数位字符 { hash ^ ((hash 7) ^ (s[i]) ^ (hash 3)); } else // 奇数位字符 { hash ^ (~((hash 11) ^ (s[i]) ^ (hash 5))); } } return hash; } }; // DJB哈希仿函数 // Daniel J. Bernstein发明初始值5381乘33异或字符分布效果好经典字符串哈希 struct HashFuncDJB { size_t operator()(const std::string s) { size_t hash 5381; for (auto ch : s) { hash hash * 33 ^ ch; } return hash; } }; /** * brief 布隆过滤器 BloomFilter * 底层依赖位图bitmap利用多个独立哈希函数将key映射到多个bit位置并置1 * 特点 * 1. 判断【不存在】一定是准确的判断【存在】存在误判假阳性 * 2. 不支持删除元素一个bit位会被多个key共享 * tparam N 预估最多插入的元素个数 * tparam X M/N位图总比特数M N * XX越大位图空间越大误判率越低 * tparam K 存储元素类型默认std::string * tparam Hash1 哈希函数1 * tparam Hash2 哈希函数2 * tparam Hash3 哈希函数3 */ templatesize_t N, size_t X 5, class K std::string, class Hash1 HashFuncBKDR, class Hash2 HashFuncAP, class Hash3 HashFuncDJB //相当于k3有三个哈希函数也就需要保证三个映射位置都为1才说明元素是存在的 class BloomFilter { public: void Set(const K key) { // 哈希值对M取模映射到位图的bit下标Hash1()构造临时匿名仿函数对象调用operator() size_t hash1 Hash1()(key) % M; size_t hash2 Hash2()(key) % M; size_t hash3 Hash3()(key) % M; //cout hash1 hash2 hash3 endl; // 将3个映射位置的bit置1 _bs.set(hash1); _bs.set(hash2); _bs.set(hash3); } bool Test(const K key) { size_t hash1 Hash1()(key) % M; if (!_bs.test(hash1)) { return false; } size_t hash2 Hash2()(key) % M; if (!_bs.test(hash2)) { return false; } size_t hash3 Hash3()(key) % M; if (!_bs.test(hash3)) { return false; } return true; // 为true不能说明这个元素就是存在的还是可能存在三个映射正好和其他存在的元素完全重合而产生误判 } // 获取公式计算出的误判率 double getFalseProbability() { double p pow((1.0 - pow(2.71, -3.0 / X)), 3.0); return p; } private: static const size_t M N * X; // 位图总bit数量 预估元素数量 × 比例系数X bit::bitmapM _bs; // 底层位图容器 };原理布隆过滤器底层依赖位图 bitmap核心思想多个独立哈希函数对同一个 key 映射到多个 bit 位。插入 (Set)对 key 使用 3 个不同的哈希函数算出 3 个哈希值对总 bit 数 M 取模得到 3 个位图下标将这 3 个下标对应的 bit 全部置 1。同一个 bit 位会被多个 key 共享。查询 (Test)同样用 3 个哈希函数算出 3 个下标。只要任意一个 bit 为 0这个 key一定不存在结论 100% 准确三个 bit 全部是 1判定大概率存在存在假阳性误判。误判原因可能是多个不同 key刚好把这 3 个 bit 全部置 1并不是当前 key 插入导致。重要限制标准布隆过滤器不支持删除元素。 原因bit 是共享的如果把某个 bit 置 0会影响其他共用该 bit 的 key导致正常 key 被误判不存在。模板参数说明size_t N预估最多插入的元素个数。不是硬限制用于计算位图总比特数 M。size_t X 5系数 \(XM/N\)M N * X。X 越大 → 位图 bit 越多占用内存更大误判率越低X 越小 → 位图更小节省内存误判率越高class K std::string存储元素的类型默认是字符串url、黑名单字符串场景最常用Hash1/Hash2/Hash3三个哈希仿函数要求哈希算法尽量相互独立、哈希分布均匀。BKDR经典字符串哈希Java 字符串 hash 同源乘 31AP基于奇偶字符大量移位异或离散性好DJB初始值 5381乘 33 异或字符冲突少适用场景核心只需要快速判断「元素一定不存在」允许少量误判缓存穿透防护判断请求的 key 是否一定不在数据库不存在直接拦截避免大量无效查询打到数据库。黑名单过滤垃圾邮箱、恶意 URL、违规账号黑名单。海量集合去重预判大数据场景快速预判元素是否已经出现过。分布式系统海量数据集合快速成员判断节省网络传输与内存。不适合场景 需要 100% 精确判断存在需要删除元素需要获取原始 key。优缺点优点空间效率极高只存储 bit不保存原始 key海量数据下内存远小于哈希表、unordered_set、红黑树。插入、查询时间复杂度 O (1)只需要多次哈希 位图位运算速度极快。哈希计算可以并行适合海量高并发场景。缺点假阳性误判判断存在不一定真实存在判断不存在一定正确。不能删除元素标准布隆过滤器无法删除因为 bit 位共享。扩展计数布隆过滤器每 bit 改为计数器可以删除但内存开销会上升。只能做成员存在性判断不能取出原始数据。需要提前预估最大元素数量 N预估不准会影响误判率。2.3.2 测试代码示例简单布隆过滤器测试#define _CRT_SECURE_NO_WARNINGS #includeBloomFilter.h //简单布隆过滤器测试用例少量字符串验证基础功能 void TestBloomFilter1() { BloomFilter10 bf; bf.Set(猪八戒); bf.Set(孙悟空); bf.Set(唐僧); std::cout bf.Test(猪八戒) std::endl; std::cout bf.Test(孙悟空) std::endl; std::cout bf.Test(唐僧) std::endl; std::cout bf.Test(沙僧) std::endl; std::cout bf.Test(猪八戒1) std::endl; std::cout bf.Test(猪戒八) std::endl; } int main() { TestBloomFilter1(); }运行结果演示大规模数据测试统计真实误判率#define _CRT_SECURE_NO_WARNINGS #includeBloomFilter.h //大规模数据测试统计真实误判率对比理论公式误判率 void TestBloomFilter2() { srand(time(0)); const size_t N 1000000; BloomFilterN bf; // X3MN*3位图更小误判率会比X5更高 //BloomFilterN, 3 bf; // X10MN*10位图更大误判率会比X5更低 //BloomFilterN, 10 bf; std::vectorstd::string v1; //std::string url https://www.cnblogs.com/-clq/archive/2012/05/31/2528153.html; //std::string url https://www.baidu.com/s?ieutf-8f8rsv_bp1rsv_idx1tn65081411_1_oem_dgwdln2fenlei256rsv_pq0x8d9962630072789frsv_tceda1rulSdBxDLjBdX4484KaopD%2BzBFgV1uZn4271RV0PonRFJm0i5xAJ%2FDorqlangenrsv_enter1rsv_dlibrsv_sug33rsv_sug12rsv_sug7100rsv_sug20rsv_btypeiinputT330rsv_sug42535; std::string url 猪八戒; for (size_t i 0; i N; i) { v1.push_back(url std::to_string(i)); } for (auto str : v1) { bf.Set(str); } // v2跟v1是相似字符串集前缀一样但是后缀不一样 v1.clear(); for (size_t i 0; i N; i) { std::string urlstr url; urlstr std::to_string(9999999 i); v1.push_back(urlstr); } size_t n2 0; for (auto str : v1) { if (bf.Test(str)) // 误判 { n2; } } std::cout 相似字符串误判率: (double)n2 / (double)N std::endl; // 不相似字符串集 前缀后缀都不一样 v1.clear(); for (size_t i 0; i N; i) { //string url zhihu.com; std::string url 孙悟空; url std::to_string(i rand()); v1.push_back(url); } size_t n3 0; for (auto str : v1) { if (bf.Test(str)) { n3; } } std::cout 不相似字符串误判率: (double)n3 / (double)N std::endl; std::cout 公式计算出的误判率: bf.getFalseProbability() std::endl; } int main() { TestBloomFilter2(); }运行结果演示比率 X 5 的结果比率 X 3 的结果比率 X 10 的结果2.4 布隆过滤器删除问题标准布隆过滤器一般不支持删除操作存在两个核心原因会误删其他有效元素布隆过滤器的 bit 位是多个 key 共享的。当删除一个元素时如果把它对应的 bit 置 0而这些 bit 位同时被别的元素共用。就会导致其他还存在的 key在查询时因为 bit 被置 0被错误判定为不存在。示例删除猪八戒把共享 bit 置 0导致孙悟空对应的三个映射位不全为 1查询孙悟空时误判为不存在。无法处理假阳性带来的误删除风险即使引入计数布隆过滤器给每个 bit 增加计数器也只能解决大部分场景无法根除极端情况。假阳性场景某个根本没有插入过的 key它的全部哈希映射位置刚好被其他已插入元素全部置 1查询时会误判存在。此时如果基于这个误判结果执行删除会错误地去递减计数器造成脏数据。补充将单个 bit 改为计数器插入时计数 1删除时计数 - 1计数器归 0 时才把 bit 置 0。可以支持删除但会显著增加内存开销并且依然无法解决上面提到的极端假阳性误删场景。2.5 布隆过滤器应用场景回顾优缺点优点查询、插入效率高空间占用极小位图只能处理整数布隆过滤器可以处理字符串、URL 等任意类型 key缺点存在假阳性误判判定 “存在” 不一定真实存在判定 “不存在” 一定正确原生版本不支持删除元素实际业务场景1. 爬虫系统 URL 去重爬虫抓取网页时使用布隆过滤器保存已经爬取过的 URL。新 URL 先进入布隆过滤器判断如果判定已存在直接跳过避免重复发起网络请求减少重复抓取。2. 垃圾邮件过滤将已知垃圾邮件的特征存入布隆过滤器。新邮件到来时快速判断特征是否匹配黑名单快速过滤垃圾邮件提升过滤效率。3. 分布式缓存预防缓存穿透缓存穿透大量请求查询数据库不存在的数据缓存不命中直接打到数据库压垮 DB。请求先经过布隆过滤器过滤器判定不存在 → 直接返回不访问缓存、数据库过滤器判定存在 → 再去查询缓存缓存未命中再访问数据库。4. 数据库查询加速用于前置预判减少无效数据库查询。 例APP 快速判断手机号是否注册。手机号先过布隆过滤器判定不存在直接返回不查数据库判定存在再去数据库二次确认。三、海量数据处理问题核心背景内存有限文件超大无法一次性把全部数据加载进内存这类海量数据题目常用两种思路布隆过滤器、哈希切分分桶。3.1 问题一问题给两个文件分别有100亿个query我们只有1G内存如何找到两个文件交集?题目分析假设每个 query 字符串平均 50Byte100 亿个 query 总数据量约 500GB远大于 1G 内存。 直接把全部数据加载进哈希表 / 红黑树完全不可行。方案 1布隆过滤器方案将文件 A 全部 query 构建布隆过滤器加载到内存。遍历文件 B 的每一条 query调用布隆过滤器判断是否存在。布隆返回存在 → 认为是交集返回不存在 → 一定不是交集。缺点布隆过滤器存在假阳性误判。有可能某个元素只存在于 B哈希映射刚好命中 A 布隆的全部置 1bit被误判成交集。结论只能得到交集的候选集合结果不准确会多出来假的交集元素。方案 2哈希切分分桶核心思想不能按顺序平均拆分文件要用哈希函数做分桶。公式i HashFunc(query) % NN 是拆分后的小文件总数。相同 query 经过同一个哈希函数取模后得到相同的桶编号一定会进入编号相同的小文件。文件 A 切分成 ( A0A1...A(N-1) )文件 B 切分成 ( B0B1...B(N-1) )。只需要对编号相同的一对小文件 ( AiBi ) 求交集跨桶之间不存在相同 query不需要跨桶比对时间复杂度大幅下降。错误思路如果直接按文件前后顺序平均切分同一个 query 可能被分到 A 的头部桶、B 的尾部桶需要全部桶两两暴力比对复杂度( O(N^2) )效率极低。哈希切分遇到的问题小文件大小不均匀哈希取模不是均匀分配会出现某个分桶后的小文件过大超出内存限制分两种情况情况 1小文件内部大量重复 query大量重复相同字符串。放入 set 自动去重后实际内存占用很小可以直接加载进内存求交集不需要二次切分。情况 2小文件内部大量不同 query 发生哈希冲突导致单桶过大桶内元素几乎全部不重复数据量超出内存。此时更换另一个哈希函数做二次哈希切分继续分桶。判断触发二次切分的方法尝试把小文件数据插入哈希表。如果内存分配抛异常bad_alloc说明内存放不下属于情况 2启动二次哈希切分。3.2 问题二问题给一个超过100G大小的logfile,log中存着ip地址设计算法找到出现次数最多的ip地址查找出现次数前10的ip地址解题思路哈希切分 局部统计哈希分桶读取日志里每一条 IP执行i HashFunc(IP) % N根据哈希值分到对应编号小文件。同一个 IP 一定会被分到同一个小文件。分桶内局部统计依次读取每个小文件加载进内存使用unordered_map/红黑树map统计每个 IP 的出现次数。求次数最多 IP每个桶统计完成后记录当前全局最大值。求 Top10维护一个大小为 10 的小根堆遍历每个桶不断更新堆内 Top10 候选。处理完一个小文件后清空 map / 堆释放内存继续处理下一个分桶文件。本质把超大文件拆成多个小文件把全局统计问题转化为多个局部小文件的内存内统计。结束语到这里位图与布隆过滤器的原理、代码实现以及海量数据的解题思路就全部讲解完毕。位图借助位运算用极小的空间完成数字标记是处理整数集合的高效方案而布隆过滤器作为位图的延伸牺牲一定的准确性换取巨大的内存节省适合做存在性预判。我们也看到面对海量数据问题不能直接套用常规哈希表哈希切分、分桶等思路是解决内存不足的常用手段。这些算法在 Redis、数据库、缓存拦截等工程场景广泛使用也是算法面试的高频考点。掌握这部分内容之后我们对哈希体系的理解会更加完整。后续我们继续回到 C 哈希相关的其他知识点进一步夯实底层数据结构基础。