教程【免费下载链接】Learn-Algorithms算法学习笔记项目地址https://gitcode.com/gh_mirrors/le/Learn-Algorithms点击查看免费下载导读在 Learn-Algorithms 仓库的「91 Algorithms In Big Data」目录中Bitmap.md 记录了海量数据处理中最基础也最实用的一类技巧——位图法Bitmap用 1 个或几个bit 位来标记某个元素对应的 value从而以极小内存解决「元素是否存在」「无重复数排序」「统计不同元素个数」等问题。本文以该文档为主体结合仓库中 海量数据处理.md、双层桶划分.md 与 Bloomfilter.md 的源码级笔记完整讲解 Bitmap 的核心原理、位运算映射、C 语言实现以及它在海量数据场景下的实战方案。读完本文你将能独立完成电话号码去重统计、大文件整数排序、找出缺失整数等经典海量数据题目的位图法设计与编码。一、什么是 Bitmap用 bit 位标记元素Bitmap位图的核心思想非常朴素用 1 个或几个bit 位来标记某个元素对应的 value。如果是1-bitmap每个元素只占用 1 个 bitbit 为1表示元素存在为0表示不存在因此只能表达「元素是否存在」如果是x-bitmap如 2-bitmap、4-bitmap每个元素占用 x 个 bit除了存在性之外还可以记录元素出现的次数等更多信息例如 2-bitmap 用00/01/10表达未出现、出现 1 次、出现多次。使用 bit 位存储信息在存储空间方面可以大大节省——这正是 Bitmap 在海量数据处理中立足的根本。仓库 91 Algorithms In Big Data/README.md 中把海量数据处理归纳为两类手段针对「时间」用巧妙算法搭配合适数据结构bitmap / 堆 / trie 树等针对「空间」用大而化小、分而治之hash 映射。Bitmap 属于前者是典型的时间换空间、空间换内存的利器。二、核心应用场景原文档 Bitmap.md 明确指出 Bitmap 的两大经典应用场景判断某个元素是否存在——如统计文件中不同电话号码的数量、判断整数是否出现过排序——注意前提如果是 1-bitmap只能对无重复的数排序因为每个数只有 1 个 bit 位无法表达「该数出现了几次」。下文将以一个具体的电话号码例子引出完整的映射与编码实现。三、实战案例统计 8 位电话号码中不同号码的个数3.1 问题与空间分析某文件中有若干 8 位数字的电话号码要求统计一共有多少个不同的电话号码。分析8 位数字最大为99 999 999即取值范围是0 ~ 99 999 999共约 1 亿个可能的号码。如果1 Byte8 bit表示 1 个号码是否存在需要100 000 000 Byte ≈ 95MB空间如果1 bit 表示 1 个号码是否存在则只需要95 / 8 ≈ 12MB空间。8 倍的压缩比正是位图的价值所在内存受限例如面试题中常见的 512MB、1GB 限制时这往往是「能不能装进内存」的分水岭。3.2 数字 k 与 bit 位的映射关系需要把数字k取值范围0 ~ 99 999 999映射到 12MB 位图数组中的某一个 bit 上。映射规则是字节定位k / 8决定 k 落在第几个字节位内定位k % 8决定在该字节内的第几位。原文档给出了完整的 C 语言骨架#define SIZE 15*1024*1024 char a[SIZE]; memset(a,0,SIZE); // a[k/8] 这个字节中的 k%8 位命中置为1 // 这里要注意 big-endian 和 little-endian 的问题假设这里是 big-endian a[k/8] a[k/8] | (0x01 (k%8))要点拆解SIZE取15*1024*1024约 15MB对应约 1.2 亿个 bit覆盖0 ~ 99 999 999全部号码域留有余量memset(a, 0, SIZE)将位图全部初始化为 0所有号码初始视为「不存在」a[k/8] | (0x01 (k%8))用按位或把对应位写成 1而不会影响同一字节内其他位的状态文档特别提醒k%8位移方向左移还是右移与大端big-endian/ 小端little-endian字节序有关跨平台实现时需注意统一约定。3.3 完整流程分配 15MB 位图并清零逐个读取文件中的电话号码k按上述映射把对应 bit 置 1重复号码只置一次位天然去重统计完成后遍历整个位图统计值为 1 的 bit 个数即为不同电话号码的总数。时间复杂度 O(n)n 为文件记录数空间固定约 12~15MB与号码数量无关。四、位图法的通用位运算置位与取位仓库 海量数据处理.md 在「求出这个文件里的整数里不包含的一个整数」一节中给出了位图法更通用的置位 / 取位写法可直接作为工程化实现模板// 写入指定位 bytepos i / 8; // 等价于 i 3 bitpos i % 8; // 等价于 i 0x07注意原笔记写的是 0x1F8 位内取模应为 0x07 // 置为 1arr[bytepos] | (1 bitpos) // 置为 0arr[bytepos] ~(1 bitpos) void setbit(int *bitmap, int i) { bitmap[i 3] | (1 (i 0x07)); } // 读指定位 int getbit(int *bitmap, int i) { return bitmap[i 3] (1 (i 0x07)); }这套setbit / getbit原语可以复用到底层的读位与写位是后续所有 Bitmap 变体2-bitmap、Bloom Filter的基础。仓库原文同时强调位图法适用于大规模数据通常用来判断某个数据存不存在。五、应用一判断元素是否存在——找出缺失的整数经典题目见 海量数据处理.md一个文件中有 40 亿个整数每个整数为四个字节内存为 1GB写出一个算法求出这个文件里的整数里不包含的一个整数。思路分析直接存储40亿 * 4Byte 15GB远超 1GB 内存限制不可能全部载入4 字节整数共有2^32个可能取值使用位图法分配2^29 * 2^3 512MB的内存空间每个 bit 代表一个整数全部初始化为 0读入一个数把对应的 bit 位置为 1。例如读入312312 / 8 39、312 % 8 0写入第 40 个字节的 0 号 bit处理完 40 亿数据后遍历 512MB 内存找到第一个 bit 为 0 的位置该位置对应的整数就是文件中不包含的整数。只需 512MB甚至更小取决于扫描方式就把 15GB 的问题压缩进了内存这是 1-bitmap「存在性判断」的典型胜利。六、应用二位图法排序无重复整数另一个经典题目同样出自 海量数据处理.md假设一个文件中有 9 亿条不重复的 9 位整数现在要求对这个文件进行排序。思路一位图法排序计算需要内存9 位整数最多表示 10 亿条不重复整数无符号9亿 / 8 / 1024 / 1024 120MB全部初始化为 0分段读取文件中的数据将数据对应的 bit 位置 1遍历整个 bit 空间将 bit 为 1 的依次存入文件。由于遍历顺序天然是从小到大的整数域顺序bit 为 1 即意味着该数存在按序遍历即可直接得到有序输出——排序的同时完成了去重。时间复杂度近似 O(n)无需比较与交换。注意适用前提1-bitmap 排序要求数据无重复。若存在重复数字1 个 bit 无法表达出现次数需要升级为 2-bitmap见下文。七、进阶2-bitmap——在存在性之上记录出现次数原文档开头提到的「x-bitmap 还可以是元素出现的次数等信息」在仓库中有具体落地。仓库 海量数据处理.md 与 双层桶划分.md 都记录了 2-bitmap 的用法在 2.5 亿个整数中找出不重复的整数内存不足以容纳这 2.5 亿个整数。方案采用 2-Bitmap每个数分配 2 bit00表示不存在01表示出现一次10表示出现多次两次及以上11无意义保留。处理流程扫描这 2.5 亿个整数查看 Bitmap 中对应位原来是00则改为01原来是01则改为10原来是10保持不变。扫描结束后查看 bitmap把对应位为01的整数输出即可——这些就是「只出现一次」的整数。内存估算见 双层桶划分.md每个数占 2 bit则2^32个数的完整位图约2^32 / 4 2^30 Byte 1GB若先按 hash 分桶到 256 个文件每个文件约2^24个数单文件位图仅约 64MB可配合流式读取处理。这也是「双层桶划分分而治之 Bitmap」组合拳的经典案例仓库在 双层桶划分.md 中明确指出其适用领域是top-k、中位数、不重复或重复的数字。八、Bitmap 与 Bloom Filter从 1 个 hash 到 k 个 hashBitmap 是位图思想的最简形态而布隆过滤器Bloom Filter可以看作是对 bitmap 的扩展——使用多个 hash 映射函数从而降低单个 hash 发生冲突的概率见 Bloomfilter.md创建 m 位的 bitset初始化为 0选中 k 个不同的哈希函数第 i 个 hash 函数对字符串 str 哈希的结果记为h(i, str)范围(0, m-1)写入对 str 分别计算h(1,str), h(2,str), ..., h(k,str)将这 k 个位置全部置 1——一个 str 被映射到 bitset 的 k 个二进制位查询对 str 再计算 k 个哈希值检查对应位若任何一位不为 1 则 str 一定没有被记录过若全部位都是 1 则「认为」str 存在但存在**误判false positive**的可能该字符串对应的 bit 恰好都被其他字符串置位删除字符串一旦加入就不能删除因为删除会影响其他字符串确实需要删除时可改用Counting Bloom FilterCBF。布隆过滤器的设计要点同样在 Bloomfilter.md 中有公式支撑当k (ln2) * (m/n)时错误率最小n 为元素个数m 为 bit 位数例如错误率 0.01 时m 约为 n 的 13 倍k 约为 8 个。两者关系一句话总结Bitmap 用 1 个哈希映射、1 个 bit 位标记元素Bloom Filter 用 k 个哈希映射、k 个 bit 位标记元素后者牺牲更多 bit 位换取更低的冲突/误判率适用于 URL 去重、爬虫防重复抓取、缓存穿透防护等场景。Bloom Filter 的完整算法与实现示例详见 Bloomfilter.md。九、局限性与适用边界结合原文档与仓库笔记使用 Bitmap 时需明确以下边界1-bitmap 无法处理重复只能表达存在与否排序场景要求数据无重复需要计数信息时必须升级为 2-bitmap 或更大粒度的 x-bitmap值域必须可枚举、密度足够位图的大小取决于值域范围而非数据量。若值域极大如几十位随机 ID位图反而浪费空间——此时应转向 hash 分桶或 Bloom Filter 等方案不可逆位图只保存「是否出现」信息无法恢复原始数据端序敏感位内位移方向与字节序big-endian / little-endian相关原文档 Bitmap.md 明确提示了这一跨平台陷阱。十、总结Bitmap 以「一个 bit 一个元素」的朴素思想在海量数据场景下提供了数量级的空间压缩场景传统方案Bitmap 方案1 亿个 8 位电话号码去重统计1 Byte/号码 ≈ 95MB1 bit/号码 ≈ 12MB40 亿整数找缺失值直接存储 15GB位图 512MB9 亿个 9 位整数排序3.4GB 内存排序位图 120MB边遍历边输出2.5 亿整数找不重复hash_map 内存不足2-bitmap00/01/10本文所有代码与方案均源自仓库文档Bitmap.md映射与置位、海量数据处理.mdsetbit/getbit 原语、找缺失整数、位图排序、2-bitmap 找不重复整数、双层桶划分.md分桶 2-bitmap 的内存估算、Bloomfilter.md多哈希扩展。读者可将这些片段组合直接应用于面试题解答与真实海量数据的去重、存在性判断与排序任务。赞分享教程【免费下载链接】Learn-Algorithms算法学习笔记项目地址https://gitcode.com/gh_mirrors/le/Learn-Algorithms点击查看免费下载相关推荐iCloud照片下载器完整指南一次配好7个场景iCloud照片下载器完整指南一次配好7个场景 照片视频都堆在 iCloud本地硬盘上却没有一份完整备份icloud_photos_downloaderCLIAdvanced Java 项目解析海量数据中高效判断数字存在的位图法Advanced Java 项目解析海量数据中高效判断数字存在的位图法 问题背景 在现代大数据应用中我们经常需要处理海量的数据集合。一个典型的问题是如何在文档教程知识库后端advanced-java 海量数据处理如何用位图法在 40 亿个 unsigned int 中快速判断一个数是否存在advanced java 海量数据处理如何用位图法在 40 亿个 unsigned int 中快速判断一个数是否存在 导读 本文来自 advanced j文档教程知识库后端上一篇Anemone高效灵活的网页爬虫框架下一篇Mongomapper: MongoDB 的 ORM 库创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考