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

我会通过以下方式解决这个问题：

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

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

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

可能还有比这更聪明的方法，只是把我读到这个任务时想到的东西扔掉。

我画了一个几乎可以执行此操作的小程序。它不获取片段中的校验和。这样做的原因是，当我运行在总共 6 GB 数据的 236670 个文件上执行此操作时，只用了 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();
    }
}

Java 大文件 CRC (Adler)

Java CRC (Adler) with large files

java

checksum

large-files