外部K路归并迭代器异常：输出文件大小不符且提前终止

核心问题梳理 #

• 基于1024字节随机整数输入文件的外部K路归并排序实现，将输入分割为256字节的已排序小文件块后，通过Stream<Integer>与迭代器归并，输出文件大小仅为400-500字节（远小于输入）；仅当输入文件≤32字节时可正常运行
• 两种迭代器实现（TreeSetMergedIterator、MergedIterator）均存在hasNext()意外返回false的问题，导致算法提前终止，仍有未处理数据残留
• 已确认字节与整数的转换逻辑无异常

可能的根因分析 #

1. 迭代器hasNext()逻辑缺陷 #

• 若迭代器依赖的块Stream未正确维护状态，比如某个块文件流被提前关闭，或Stream在元素耗尽后未自动加载下一个块的内容，会导致hasNext()误判为无后续元素
• 对于TreeSetMergedIterator，若取出最小元素后未及时从对应块Stream中加载下一个元素补充到TreeSet，或者TreeSet耗尽时未检查剩余块是否还有未处理数据，就会触发提前终止

2. 块分割与读取的边界错误 #

• 256字节块对应64个整数（每个int占4字节），若分割逻辑仅按固定256字节截断文件，会忽略输入文件末尾不足256字节的剩余数据，直接丢失这部分整数
• 读取块文件时，若未循环读取到流末尾（比如仅调用一次read()方法），会导致部分整数未被加载到Stream中，最终归并时元素数量不足

3. 归并过程的元素丢失 #

• 若使用TreeSet作为候选元素容器，其天然的去重特性会过滤掉输入中的重复随机整数，导致输出元素数量减少
• 归并时若取出最小元素后，未从对应块的迭代器中获取下一个元素补充到候选集合，会导致候选集合耗尽后无法继续处理后续块的数据

修复建议 #

迭代器逻辑修复 #

• 针对TreeSetMergedIterator：每次从TreeSet取出最小元素后，立即从对应块的Stream中读取下一个元素并加入TreeSet；当某个块的Stream耗尽时，移除该块的迭代器标记，只有当所有块的Stream都耗尽且TreeSet为空时，hasNext()才返回false
• 确保所有块文件的输入流在整个归并过程中保持打开状态，避免Stream被提前关闭导致数据读取中断

块分割与读取优化 #

• 分割文件前先计算总整数数量（总字节数 ÷ 4），再按每块64个整数（256字节）分割，最后一个块即使不足64个整数也要完整保留
• 读取块文件时，循环读取所有字节确保无遗漏，示例代码：

  List<Integer> blockData = new ArrayList<>();
  try (DataInputStream dis = new DataInputStream(new FileInputStream(blockFile))) {
      // 循环读取直到流末尾，确保所有整数被加载
      while (true) {
          try {
              blockData.add(dis.readInt());
          } catch (EOFException e) {
              break;
          }
      }
  }
  Stream<Integer> blockStream = blockData.stream();
  

归并完整性校验 #

• 归并前统计所有块的元素总数，归并后统计输出的元素总数，对比两者定位元素丢失的环节
• 若需要保留重复元素，替换TreeSet为优先级队列（PriorityQueue），存储包含元素和对应块迭代器的自定义对象，确保重复元素被正确处理

内容的提问来源于stack exchange，提问作者RocketMan