企业官网建设流程全解析

做数据统计分析的人，几乎都经历过这样的时刻：同样的排序代码，测试集跑得好好的，换到全量数据直接不干活了。先是内存曲线几分钟内拉满，然后是 GC 日志刷屏，最后干脆抛出一个 OutOfMemoryError。我第一次认真思考这个问题，是在某跨平台系统的日志处理环节，几千万条用户 ID 要排序去重后落库。临时加内存没用，换机器也不是长久之计，那段时间我尝试了外部归并、分桶、索引排序，最后发现最朴素也最被低估的方案是 Bitmap——位图法。今天这篇就把 Bitmap 做海量数据排序的原理、实现、边界和衍生玩法一次讲透，适合正在跟千万级整数数据搏斗的后端、算法和数据开发同学参考。

2. 整数规模膨胀时，教科书排序为什么先犯规

2.1 数学账：一亿个 int 到底吃多少内存

先算一笔最基础的账：一亿个 int，4 字节一个，就是 400MB。这是 C 语言、裸字节数组里最理想的情况。Java 里你要是直接用 Integer，单个对象撑死 24 字节，一亿个就是 2.4GB，这还不算数组引用和对象头的开销。如果数据源是文本文件，每一行一个 ID 按 String 读进来，对象头、char[]、编码再加上 GC 压力，4GB 都是保守估计。

为什么排序比存储更吃内存？因为很多排序算法要求额外空间。经典归并排序需要等长辅助数组，空间直接翻倍；快排虽然原地排序，但数据从流里读进来再转成对象时，内存里往往同时存在原始缓冲区、解码后的 String 和待排的 int 数组，峰值比你预想的宽裕要紧张得多。我见过不少同事第一反应是“400MB 而已”，结果堆内存设了 1GB，一跑就挂。

这里给一张内存对照表，方便做预算：

现实中的 ID 往往不止 4 字节能装下，身份证号、手机号、带前后缀的订单号都得当字符串处理，内存压力比这张表还要大。

2.2 外部排序的时间账：IO 一多就不划算

内存扛不住，大家自然会想到外部排序：把数据切块，每块排好落盘，最后多路归并。这条路在教科书上很完美，实际生产中却充满挫折感。落盘意味着每一轮归并都要把全量数据读写一遍，以 1 亿条 400MB 来算，一轮归并就是 800MB 的 IO 流量，两轮三轮跑下来，2GB 打底。机械硬盘随机读写下 400MB 可能要几分钟，SSD 好一些，但显然是在用宝贵带宽换内存空间。

更关键的是，这类任务往往是周期性任务。日志清洗、报表预计算、近线数据服务，每天、每小时都要跑，等于每跑一次都要重复付出同样的 IO 成本。如果能把数据压缩到原体积的三十二分之一，那么不管是纯内存排序还是落盘归并，压力都会指数级下降。

所以真正值得反思的一点是：排序是不是这堆数据的第一需求？很多时候我们要的只是“去重后的有序输出”或者“两个集合的交集”，用通用排序去实现纯属杀鸡用牛刀。Bitmap 的思路就是从这个反思中冒出来的：如果你只管存在与否，那一个布尔位就够了，为什么要给每个整数发一张 32 位的“身份证”？

2.3 适用边界：什么样的数据才配用 Bitmap

Bitmap 绝不是普适银弹。它成立的前提有三个：数据是整数；取值范围有限且事先可估计；关注点落在“某个数是否出现”上。

第一条很好理解，浮点数在内存里是符号位加指数加尾数，大小关系和位模式没有直接对应关系，不能拿来当位置索引。第二条是空间约束，范围 M 多大，位图就占 M/8 字节，它不关心你有多少条数据。第三条关系到排序是否能退化成扫描，如果你还要保留每个数字出现的次数，就得另做计数数组或用多个 bit 去编码。

判断要不要用 Bitmap，我建议大家启动前先画一条数据分布曲线，确认最小值、最大值、大概的范围跨度。这一步往往能直接终结争议：范围 1000 万以内，位图可能连 2MB 都不到；范围 100 亿以上，你还硬用位图，内存预算就太刺激了。

3. Bitmap 的底层账本：一个 bit 怎么把 32 位压缩成 1 位

3.1 从“房间有没有人”说起

理解 Bitmap，可以把它想成一栋标准化大楼的门牌号。每一间房都有一个固定编号，房间号本身就是它在整栋楼里的坐标。你要管理的并不是房间里的家具，而是“这个房间有没有人”——这是每个房间唯一需要记录的信息。一个 bit，正好是存储这个信息的最小单元。

对应到数据结构上：数字区间 [0, M] 就是整栋楼的门牌号；一个字节像是一层楼，一层楼有 8 个房间；某个数字出现过，就把对应房间的灯打开，没出现过就保持关闭。因为房间号从小到大自然排列，你只要从一楼开始往上走，看见哪间灯亮就报哪间号，报出来天然就是升序。

举个简单例子，集合 {2, 5, 9}。按范围 0~9 建一张位图，第 2、5、9 位置 1，其余为 0。扫描时依次看每一位：0 号没人，1 号没人，2 号有人，输出 2；3、4 没人，5 有人，输出 5；6、7、8 没人，9 有人，输出 9。排序结果就这样出来了，全程没有一次比较运算。

3.2 位运算三步：定位、置位、判定

具体实现只需要三个基础操作，每个操作都是一次简洁的位运算。

• 定位：数字 n 落在数组的第几个字节，index = n / 8，用右移就是 n >> 3。
• 置位：在第几个 bit 上，offset = n % 8，用与运算 n & 7。
• 判定：写值的时候做 OR：bits[index] |= 1 << offset；读值的时候做 AND：bits[index] & (1 << offset) 不等于 0 就表示存在。

演示一下 n = 13。13 / 8 等于 1，所以操作第 1 个字节；13 % 8 等于 5，也就是第 5 个比特位。这个字节管的是数字 8 到 15，bit 0 对应 8，bit 5 对应 13，完全对得上。一个字节 8 个 bit，刚好是 8 个连续整数的“存在性标志”，多个字节拼起来就是一条覆盖整个取值范围的布尔长轴，扫描这条长轴就等于从小到大遍历集合。

3.3 复杂度账：32 倍压缩背后的数学直觉

把 n 个整数放进 int 数组，每个数固定 32 位；放进 Bitmap，每个数在布尔语义上只需要 1 位。压缩比就是 32 倍。当我第一次在项目里用 1.25MB 的位图装下 1000 万条 ID 时，那种从 40MB 降到 1.25MB 的感觉还是很直观的。

但复杂度必须说全面：普通排序空间是 O(N)，跟数据条数走；Bitmap 空间是 O(M/8)，跟取值范围走。N 很大、M 又被限制得不大时，位图是王者；N 很小、M 巨大无比时，位图就是灾难。时间上同样如此，置位是 O(N)，扫描输出是 O(M/8)，总和 O(N+M)，在 M 可控的前提下比 O(NlogN) 的快排有本质优势。

4. 手写排序器：从 Java 实现到千万级数据实测

4.1 核心类：只关心置位与扫描

先给一个最直接、最贴合的 Java 实现。它就是一个轻量封装，暴露 add、contains、sortedValues 三个方法，外部数据流一遍即可完成全部信息写入。

import java.util.ArrayList; import java.util.List; public class BitmapSorter { private final byte[] bits; public BitmapSorter(int maxValue) { // maxValue / 8 取整，再加 1 应对余数 this.bits = new byte[maxValue / 8 + 1]; } public void add(int value) { if (value < 0) { throw new IllegalArgumentException("Bitmap 排序仅支持非负整数"); } int index = value >> 3; // 等价于 / 8 int offset = value & 7; // 等价于 % 8 bits[index] = (byte) (bits[index] | (1 << offset)); } public boolean contains(int value) { if (value < 0) { return false; } int index = value >> 3; if (index >= bits.length) { return false; } int offset = value & 7; return (bits[index] & (1 << offset)) != 0; } public List<Integer> sortedValues() { List<Integer> result = new ArrayList<>(); for (int i = 0; i < bits.length; i++) { for (int offset = 0; offset < 8; offset++) { if ((bits[i] & (1 << offset)) != 0) { result.add(i * 8 + offset); } } } return result; } }

这里有一个容易被 Java 基础不牢的人误导的点：byte 是有符号的，当 byte 的最高位为 1 时，它会被当成负数。但在我们的位运算里，关键操作是比特位的与、或、移位，符号位参与运算并不会破坏低 8 位的状态，只要注意力放在低 8 位上，结果依然正确，代码不用因为符号问题绕路。

4.2 Python 版：bytearray 让代码更短但思想一致

如果你用 Python 做数据清洗，标准库的 bytearray 已经够用，逻辑和 Java 完全一致，只是语法省了不少。

def bitmap_sort(numbers, max_value): bits = bytearray(max_value // 8 + 1) for num in numbers: if 0 <= num <= max_value: bits[num >> 3] |= (1 << (num & 7)) result = [] for byte_index, byte in enumerate(bits): for offset in range(8): if byte & (1 << offset): result.append(byte_index * 8 + offset) return result

使用示例：

nums = [5, 2, 9, 0, 100, 3, 99] print(bitmap_sort(nums, 100)) # [0, 2, 3, 5, 9, 99, 100]

这段代码的语义很清晰：数据进来先“登记”，登记完了按顺序从第 0 位扫到最后一位，出来自然有序。重复出现的数字只置一次位，所以顺便完成了去重。

4.3 千万级数据实测：内存账同步验证

有代码就要有验证。我在一台堆内存限制在 512MB 的开发机上跑过一组模拟数据：随机生成 1000 万个 0 ~ 9999999 范围的整数，然后做 Bitmap 排序。

• 位图数组长度：10000000 / 8 + 1，约 1.25MB。
• 原始 int 数组 1000 万条是 40MB，但数据边读边塞进位图，根本不需要同时驻留。
• sortedValues 输出的元素个数取决于去重后的数目，扫描一千万个字节用不了多少时间。

同样的数据用 Arrays.sort() 排，内存至少 40MB 起步；Bitmap 排序置位阶段 O(N)，扫描阶段 O(M/8)，在这台机器上整体耗时不到 1 秒，而且内存占用稳定在两三 MB。这就是把信息密度做到极致的回报。

提醒一句：上面 1.25MB 说的是位图本身，峰值内存还要算上输入缓冲区、结果集合等，工程上要留足余量。如果数据量是 1 亿，位图是 12.5MB，依然非常可接受。

4.4 为什么优先用 byte[]，工程上也可以换 long[]

有人会问：为什么不用 int[] 或 long[]，没准还能少几次位运算？说实话，用 byte[] 的好处是内存最省、语义最直观，一个字节对应 8 个整数，写代码时不容易算错下标。但 Java 里访问 byte 数组时有符号扩展的额外开销，极致性能追求时往往改用 long[]：每个 long 有 64 位，定位公式变成 index = value >> 6，offset = value & 63，扫描时一次判断 64 个数字。内存总量不变，因为两个方案都是 M 个 bit，只是分块粒度不同。

我不建议在没有性能压测证据时盲目上 long[]，实际场景往往瓶颈在 IO 和数据读取，不在这几个位运算上。代码可读性才是长期运维里最值钱的东西。真需要极致性能，再切换成 long[] 并配合堆外内存也不迟。

5. 那些文档不会告诉你的边界：负数映射、稀疏取舍与内存陷阱

5.1 负数：给数据做一次整体搬家

标准 Bitmap 只适合非负整数，因为负数没法占一个位索引。最直接的解法是平移：先扫描一遍得到最小值 min，然后把每个数字都减去 min，统一映射到 [0, max - min]，排序输出时再把偏移加回去。

举个例子，数据范围在 -500 到 9000 之间，min = -500，那么原始值 x 映射为 x + 500，范围变成 0 ~ 9500，9501 个 bit 就能搞定。输出结果时反算 value = index - 500 即可。这个平移方案会把取值范围稍微拉大，但通常不会造成本质变化。

另一个共识是：如果负数和无序浮点混合出现，说明这个数据集合本身就不适合 Bitmap，不如直接换内部排序。不要硬凑，位图适合的是那些形态足够干净的数据。

5.2 稀疏集合：Bitmap 不是永远的小内存

这是大家最爱踩的认知误区。有人会觉得，所有排序都可以用 Bitmap 干翻，答案很简单：当 M 远大于 N 时，位图的空间优势就消失了。

判断式可以这么写：如果 M / 8 小于 N * 4，位图才值得。举例：100 万个随机数散布在 0 ~ 1 亿，位图是 12.5MB，HashSet 大约需要 30~50MB，位图胜。但如果只有 1 万个数字散布在 0 ~ 10 亿，位图要 125MB，HashSet 可能只有几百 KB，这时再执迷位图就是给自己找麻烦。

实战中我见过更隐蔽的情况：范围虽大，但数据集中在几个小簇里。这种可以先把簇头识别出来，分段建位图；或者改用两级位图，第一级做粗粒度存在性，第二级做精确索引，效果接近数据库的位图索引。

5.3 内存分配与 JVM 的坑

Java 里 new byte[125MB] 看上去没什么，但如果 JVM 堆本身只剩 100MB，一次分配就可能直接抛 OOM。海量任务上线前一定要估算峰值内存：读入缓冲、位图数组、结果列表、序列化临时对象都要算进去，不能只算位图本体。

更稳妥的思路是流式处理：数据从文件或消息队列一条一条进入，读完 val 就置位，置位后立即释放源对象，这样除了位图之外只有很小的一块固定缓冲。如果位图本身超过单机堆内存可承受范围，还可以把位图分段写成内存映射文件，用 MappedByteBuffer 直接映射到磁盘上，读位图时按页访问，相当于用虚拟内存换空间。

我还想多说一个细节：很多情况下排序任务真正的峰值不在位图登记，而在 sortedValues 收集结果列表。上亿条数字去重后可能依然有上亿条，用一个 ArrayList 装其实也会吃近 400MB。如果下游是写文件、写数据库，就应该边扫描边输出，不要积攒成一个大列表。

5.4 重复元素与计数需求：一位不够用，那就两位

Bitmap 天然去重，这既是特性也是限制。如果你需要统计每个数字出现几次，一个 bit 就吃不消了。要扩展成计数型位图，可以为每个数字分配 k 个 bit，最大能计到 2^k - 1 次。比如 4 bit 可以计 0 ~ 15 次，空间变为原来的 4 倍，但相比直接用 HashMap<Integer, Integer> 仍然经济得多。

具体落地时可以按“出现次数是否超过阈值”来分层：出现 1 次的集合用位图 A 记录，出现多次的用位图 B 记录，扫一遍数据就能维护两个位图，非常贴合“统计去重用户数 + 高频用户标签”这类业务需求。

6. 不只是排序：用同一模型做去重、存在性查询与位图索引

6.1 去重：置完 1 就是天然去重

位图的去重能力其实是排序能力的副产品。只有当同一个数字第二次出现时，它的 bit 已经为 1，OR 操作不会带来任何变化。所以从数据清洗角度，用一段流式循环加一个位图，就能同时拿到“唯一值个数”和“去重后的有序全集”。

这在用户 ID 去重、IP 去重的场景下非常实用。比如统计一天内独立访客数，直接把访问日志里的用户 ID 塞进位图，最后统计位图里 1 的个数，一次搞定。相比把全量 ID 加载到 Set 里再求 size，空间能省几十倍。

6.2 存在性判断：O(1) 的黑名单与白名单

位图集合的每一格只有“是/否”两种状态，天然适合做存在性判断。把一批受限 ID 读进位图，之后任何一次查询都是 index = value >> 3、offset = value & 7、一次 AND，O(1)。这种查询在大流量场景下比树、哈希表的平均性能更稳定，而且特别容易并行。

要给一万个并发请求判断订单号是否在黑名单，位图可以直接做成常量驻留内存，查询过程中不需要锁，也不会扩容。单机上 QPS 轻松拉满，这在很多网关、风控场景里有立竿见影的效果。

6.3 集合运算：AND、OR、XOR 直接搞定交集并集差集

位图模型最漂亮的一点，是多个集合之间的逻辑运算可以退化成字节级的位运算。求 A 与 B 的交集就是 AND，求并集就是 OR，求差集就是 AND NOT。对百万级的位图做这几种运算，现代 CPU 上几乎都是微秒到毫秒级别。

对比普通做法：如果两个集合各自有 1000 万个整数，用哈希表求交集要读一遍、哈希查找一遍；位图则把整个过程变成按字节循环。这在大数据连表、倒排索引合并、推荐系统标签交叉这些场景里，优势会非常明显。

6.4 向布隆过滤器与位图索引进阶

当你把位图和多哈希函数结合起来，就得到了布隆过滤器。布隆过滤器允许很小的误判率，能在大数据量的存在性判断场景里大幅节省内存，是它在缓存穿透防抖、分布式系统里扮演重要角色的原因。理解了 Bitmap 的 bit 定位原理，再去看布隆过滤器就是顺理成章的事。

数据库里还有一种应用叫位图索引：对低基数的列，为每个取值建一张位图，哪一行是这个值就置 1。查询统计时直接按位运算 COUNT，很多 SQL 聚合能变成位图逻辑运算，查询性能大幅提升。所以别把 Bitmap 当数据结构的玩具，它的思想已经长在很多系统的骨髓里了。

按我的经验，处理海量整数排序这类任务，第一步永远不是写排序逻辑，而是先问几个问题：范围多大、有多少条、能不能容忍去重、要不要计数。把答案填完，Bitmap 是不是合适已经写在纸上了。我自己的习惯是在项目里预置一个极简 Bitmap 工具类，既做排序又做去重，遇到合适场景随手就能用，不用每次重写。最后分享一个小技巧：如果数据分布在多个文件里，可以分文件各自建位图，最后统一做 OR 合并，这样既并行又省空间，还能顺便做跨文件的去重统计。这套思路我用了很久，经手的数据量从千万到上亿，它始终是性价比最高的那一档方案。