具有大文件的 Java CRC (Adler)

Question

我有以下情况：一个包含大文件的目录树（大约 5000 个文件，大小约为 4Gb）。我需要在这棵树中找到重复项。

我尝试使用 Java 内置的 CRC32 和 Adler32 类，但它非常慢（每个文件大约 3-4 分钟）。

代码是这样的：

1) Init map <path, checksum>
2) Create CheckSum instance (CRC32 or Adler32);
3) Read file per block (10-100 bytes);
4) In each iteration call update()
5) Result checksum passed in map <path, summ>
6) Find duplicates

问题：有什么方法可以加快第 3-4 行校验和的收集速度吗？

Answer 1

我会通过以下方式处理这个问题：

1. 尝试使用 Java 8 并行流或类似的东西，以便利用我的多核 CPU 来加快速度。
2. 用所有文件填充地图。
3. 获取所有文件大小。
4. 消除所有具有唯一文件大小的文件。如果您的文件“非常正常”，这很可能已经消除了几个较大的文件。这实际上可以通过使用文件大小作为映射中的键和列表作为值来完成。然后删除列表大小为 1 的所有条目。
5. 获取每个文件的下一个（第一次：第一个）4K 字节的校验和。
6. 消除所有具有唯一校验和的文件。
7. 重复4.和5.，直到校验和不唯一的文件全部读取完毕。
8. 其余文件是重复的文件（如果校验和没有冲突）。
9. 比较重复文件的文件内容，以防发生冲突。

加快校验和的关键是将其分成块并在块之间进行比较。如果第一个字节已经不同，为什么还要查看其余的字节。

加快比较速度的另一个关键可能是反转地图。我会用 aMap<checksum, List<path>>代替Map<path, checksum>. 通过这种方式，您可以非常直接地消除所有具有大小为 1 的列表的条目，而无需任何进一步的查找或比较。

可能还有比这更聪明的方法，只要抛弃我读到该任务时想到的东西即可。

我已经勾画了一个几乎可以执行此操作的小程序。它不会获得碎片中的校验和。原因是，当我对 236670 个文件、总共 6 GB 数据运行时，只花了 7 秒。免责声明：我有一个 SSD。但也许我什至会更新部分校验和的程序。

import java.io.*;
import java.nio.file.*;
import java.nio.file.attribute.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.function.*;
import java.util.stream.*;
import java.util.zip.*;

public class FindDuplicates {
    public static void main(final String... args) throws IOException {
        findDuplicates(argsOrCurrentDirectory(args));
    }

    private static String[] argsOrCurrentDirectory(final String... args) {
        return args.length == 0 ? new String[] {"."} : args;
    }

    private static void findDuplicates(final String... paths) throws IOException {
        final Stream<Path> allFilesInPaths = find(paths);

        final Map<Long, List<Path>> filesBySize = allFilesInPaths.collect(Collectors.groupingByConcurrent(path -> path.toFile().length()));
        final Stream<Path> filesWithNonUniqueSizes = getValueStreamFromDuplicates(filesBySize);

        final Map<Long, List<Path>> filesByChecksum = filesWithNonUniqueSizes.collect(Collectors.groupingBy(FindDuplicates::getChecksum));
        final Stream<Path> filesWithNonUniqueChecksums = getValueStreamFromDuplicates(filesByChecksum);

        filesWithNonUniqueChecksums.forEach(System.out::println);
    }

    private static Stream<Path> toPaths(final String... pathnames) {
        return Arrays.asList(pathnames).parallelStream().map(FileSystems.getDefault()::getPath);
    }

    private static Stream<Path> find(final String... pathnames) {
        return find(toPaths(pathnames));
    }

    private static Stream<Path> find(final Stream<Path> paths) {
        return paths.flatMap(FindDuplicates::findSinglePath);
    }

    private static Stream<Path> findSinglePath(final Path path) {
        try {
            return Files.find(path, 127, ($, attrs) -> attrs.isRegularFile());
        } catch (final IOException e) {
            System.err.format("%s: error: Unable to traverse path: %s%n", path, e.getMessage());
            return Stream.empty();
        }
    }

    public static <V> Stream<V> getValueStreamFromDuplicates(final Map<?, List<V>> original) {
        return original.values().parallelStream().filter(list -> list.size() > 1).flatMap(Collection::parallelStream);
    }

    public static long getChecksum(final Path path) {
        try (final CheckedInputStream in = new CheckedInputStream(new BufferedInputStream(new FileInputStream(path.toFile())), new CRC32())) {
            return tryGetChecksum(in);
        } catch (final IOException e) {
            System.err.format("%s: error: Unable to calculate checksum: %s%n", path, e.getMessage());
            return 0L;
        }
    }

    public static long tryGetChecksum(final CheckedInputStream in) throws IOException {
        final byte[] buf = new byte[4096];
        for (int bytesRead; (bytesRead = in.read(buf)) != -1; );
        return in.getChecksum().getValue();
    }
}