在 40 亿整数中捕获“恰恰出现两次”的数字
继承深入探索海量数据处理的奥秘。之前我们讨论过如安在有限内存下查找重复元素或缺失元素，今天我们来增加一点难度：挑战是： 有一个包罗 40 亿个非负 32 位整数的文件。利用最多 1GB 的内存，找出全部恰恰出现了两次的数。
留意关键词：恰恰两次。这意味着出现一次、三次或更多次的数，我们都不关心。
一、回顾与升级：为何简朴 BitMap 不敷用？
[*] 挑战分析：
[*]数据范围：0 到 232 - 1 (约 42.9 亿)。
[*]数据量：40 亿。
[*]内存限制：1 GB。
[*] 标准 HashMap？ 不可行。我们之前算过，最坏环境下需要远超 1GB 的内存。
[*] 底子 BitMap (1 比特/数)？ 我们用它成功解决了“查找重复元素”和“查找缺失元素”的题目。它能告诉我们一个数字是否存在 (1) 或 不存在 (0)。实现它大约需要 512MB 内存。
[*]局限性： 它无法区分一个数字是出现了一次，还是两次，还是很多次。一旦某个数字对应的比特位被设为 1，它就永久是 1 了。我们丢失了频率信息。
类比： 简朴的 BitMap 就像一个开关，只能表现“开”（出现过）或“关”（没出现过）。但如今我们需要一个能计数到“两次”的计数器。
二、解决方案：2-Bit Map - 用两位编码频率
既然 1 个比特不敷表达所需的状态（未出现、出现一次、出现两次、出现多次），我们就需要更多的比特位。
[*] 焦点头脑： 为每个可能的非负整数（0 到 232 - 1）分配两个比特位。这两个比特位组合起来可以表现四种状态，正好满足我们的需求。
[*] 状态编码： 我们可以如许定义 2 个比特位的寄义：
[*]00：表现这个数字还未出现过。
[*]01：表现这个数字出现过一次。
[*]10：表现这个数字出现过两次。
[*]11：表现这个数字出现过三次或更多次。（一旦达到这个状态，就不再改变，由于我们只关心恰恰两次的环境）
[*] 内存占用计算：
[*]我们需要为 232 个可能的数字，每个数字分配 2 个比特。
[*]总比特数：2^32 * 2 bits。
[*]总字节数：(2^32 * 2) / 8 Bytes = 2^32 / 4 Bytes = 2^30 Bytes。
[*]换算：2^30 Bytes = 1 Gigabyte (GB)。
[*] 结论： 理论上，利用 2-Bit Map 需要 1GB 的内存，正好符合题目要求！（在现实工程中，需要精确实现以避免微小的额外开销导致超限）。
类比： 如今我们给每个数字配了一个能表现 0, 1, 2, 3+ 的迷你计数器（用两位二进制 00, 01, 10, 11 表现），而不是简朴的开关。
三、算法步骤：两遍扫描定乾坤
[*] 初始化 (构建 2-Bit Map):
[*]申请一块 1GB 大小的内存空间（例如，byte[] bitMap = new byte; 大概用 int[] 或 long[]）。
[*]将这 1GB 内存的全部比特位初始化为 0。如许，每个数字的初始状态都是 00（未出现）。
[*] 第一遍扫描 (计数与状态更新):
[*] 逐个读取文件中的 40 亿个非负整数 num。
[*] 对于每个 num：
[*] 定位： 找到 num 对应的两个比特位在内存块中的位置。起始位索引大约是 base_index = num * 2。
[*] 读取当前状态： 通过位运算，读取 base_index 和 base_index + 1 这两个比特位的值，得到当前的状态（00, 01, 10, or 11）。
[*] 更新状态： 根据读取到的当前状态，应用状态转换规则：
[*]如果当前是 00，则将其更新为 01。
[*]如果当前是 01，则将其更新为 10。
[*]如果当前是 10，则将其更新为 11。
[*]如果当前是 11，则保持 11 稳定。
[*] 写回新状态： 通过位运算，将更新后的两个比特位写回到内存块中的相应位置。
[*] 第二遍扫描 (查找结果):
[*] 处理完全部 40 亿个输入数字后，开始遍历全部可能的非负整数 i，从 0 到 232 - 1。
[*] 对于每个 i：
[*]定位： 找到 i 对应的两个比特位的位置 base_index = i * 2。
[*]读取最终状态： 通过位运算，读取这两个比特位的最终状态。
[*]判断： 如果这两个比特位表现的状态恰恰是 10（二进制的 2），那么就说明数字 i 在输入文件中正好出现了两次。
[*]输出： 将 i 输出或添加到结果列表中。
四、实现细节提示 (位运算是关键)
要在 byte[] 或 int[] 数组上精确操作两个比特位，需要一些位运算本领：
[*]定位字节/整数： byteIndex = (num * 2) / 8 或 intIndex = (num * 2) / 32。
[*]定位位内偏移： bitOffset = (num * 2) % 8 或 (num * 2) % 32。
[*]读取 2 位状态： 可能需要读取包罗这两个比特的整个字节/整数，然后用位移 >> 和位与 & 操作符提取出目标两位。例如，要读取 bitOffset 和 bitOffset + 1 位，可以 (byteValue >> bitOffset) & 0x03 (0x03 是二进制的 00000011)。
[*]写入 2 位状态： 先用位与 & 清零目标两位（例如 byteValue & ~(0x03 << bitOffset)），然后用位或 | 将新状态写入（例如 byteValue | (newState << bitOffset)）。
（详细实现会比这个形貌更复杂，需要细致处理界限和字节/整数内的比特分列）
五、知识要点梳理
[*]BitMap 扩展： 标准 BitMap 用 1 位表现存在性，可以通过增加每个元素占用的位数（如 2-Bit Map）来存储更复杂的状态或计数（有限范围内）。
[*]状态机头脑： 2-Bit Map 的状态转换（00 -> 01 -> 10 -> 11）现实上是一个简朴的状态机。
[*]精确内存控制： 解决内存受限题目的关键在于精确计算所需空间，并选择能满足空间要求的数据结构。
[*]位运算： 在低级别内存操作和优化空间利用时，位运算是不可或缺的工具。
通过将 BitMap 从 1 位扩展到 2 位，我们奥妙地在 1GB 内存限制内，实现了对 40 亿整数出现频率的精确统计（至少统计到“两次”这一关键状态）。这再次证明了理解题目本质、灵活运用底子数据结构和位运算对于解决海量数据题目的重要性。
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！ 更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]