⭐ 题目日期：

小红书 - 2024/11/11

题目描述：

如果有一个大文件里面有很多字符串，单节点你内存不够（反正装不下），如何进行去重？我提到用哈希、bitMap的方式来解决。面试官说必须100%去重，bitMap布隆过滤有误判风险。说其实想问的是MapReduce。

📝 题解：

这是一个典型的海量数据去重问题，在内存受限且要求 100% 准确性的场景下，MapReduce 的分而治之思想可以完美解决。以下是完整的解决方案思路：

---

核心思路：分片处理 + 全局合并

通过 MapReduce 将大文件拆分成多个片段，分批次处理，最终合并结果。既能突破单机内存限制，又能保证准确性。

---

具体步骤

1. 分片（Split）

• 操作：将大文件分割为多个小文件（分片），每个分片大小应适配单机内存限制（例如 1GB/片）。
• 关键：分片时不要求内容有序，但需保证相同字符串在后续步骤中能被分配到同一个处理节点。

---

2. Map 阶段：生成唯一标识

• 输入：每个分片作为一个 Map 任务的输入。
• 处理：
  • 逐行读取分片中的字符串。
  • 对每个字符串计算哈希值（如 MD5/SHA-1），生成 <Hash, String> 键值对。
  • 哈希值作为 Key，原始字符串作为 Value。
• 输出：所有 <Hash, String> 键值对。

---

3. Shuffle 阶段：按哈希值分区

• 关键操作：
  • 将 Map 输出的键值对按照哈希值（Key）进行排序和分区。
  • 确保相同哈希值的字符串被分配到同一个 Reduce 节点。
• 目的：
  • 相同字符串必然有相同哈希值，因此一定能进入同一个 Reduce 任务。
  • 不同字符串的哈希值可能冲突，但最终合并时会二次验证（见 Reduce 阶段）。

---

4. Reduce 阶段：精确去重

• 输入：同一哈希值对应的所有字符串集合。
• 处理：
  1. 内存去重：在 Reduce 任务的内存中，对相同哈希值的字符串集合进行精确比对（逐字符比较）。
     • 若哈希冲突（不同字符串哈希值相同），通过比对排除伪重复。
  2. 输出唯一值：每个哈希值对应的所有唯一字符串输出到最终结果文件。
• 关键：Reduce 任务的输入数据量受哈希值分布控制，需保证单个 Reduce 任务处理的数据量不超过内存限制。

---

5. 合并结果

• 操作：将所有 Reduce 任务的输出文件合并，即为全局唯一的结果。
• 优化：若结果需保持原始顺序，可在 Reduce 阶段额外记录位置信息。

---

为什么 MapReduce 能保证 100% 去重？

1. 哈希预分组：相同字符串必然进入同一 Reduce 任务。
2. 精确比对：Reduce 阶段在内存中逐字符比对，避免哈希冲突导致的误判。
3. 分布式扩展性：通过增加 Reduce 任务数，可处理任意规模的数据。

---

对比其他方案

方案	优点	缺点
MapReduce	100% 准确，可扩展性强	需要分布式框架支持
单机哈希分片	简单	需手动管理分片，易出错
布隆过滤器	内存效率高	有误判，不满足 100% 准确

---

补充：单机场景的替代方案

如果必须单机处理且数据无法全部加载到内存，可采用基于磁盘的外部排序-合并去重：

1. 将大文件按哈希值排序后写入磁盘。
2. 逐批读取排序后的数据，去重后合并。

但 MapReduce 仍是更优雅、更高效的分布式解决方案。