Java Comparar lote de arquivos via hash

[marcel.mc]

Olá pessoal, criei um sisteminha para comparar arquivos com finalidade de economizar algum espaço apagando os duplicados. A ideia é bem simples: dado um caminho para um diretório, percorro todos os subdiretórios e calculo o hash para cada arquivo encontrado. Depois saio comparando hash por hash, verificando se são iguais e mostrando o resultado.

 

Funciona, porém as interações de I/O estão gargalando de forma que fica inviável o processo. Fiz o teste com 3 mil arquivos e está gastando cerca de 4 a 5 minutos, acontece que a pasta que mais me interessa verificar tem mais de 91 mil arquivos. Já fiz testes usando essa pasta que demoraram mais 1 hora sem serem concluídos e de longe não chegavam a metade, outros travaram por estourar a heap. Acho que threads com I/O não vão melhorar o desempenho.

 

Eis uma das versões do código (estou usando algumas bibliotecas Apache commons só para evitar a fadiga):

 

 private Map<String, String> fileMap;
 private List<File> fileList;
 private File filePath;
   
 public void geraFileMap(){
        fileMap = new HashMap<>();
        fileList = new ArrayList<>(FileUtils.listFiles(filePath, 
                TrueFileFilter.INSTANCE, TrueFileFilter.INSTANCE));
     
        int count=0;
        for(File f: fileList){
            fileMap.put(f.getAbsolutePath(), calculaHash(f));
            System.out.println(count);
            count++;
        }
    }
   
   public String calculaHash(File f) {
        byte[] fArray = null;
        String hash = null;
        try {
            fArray = Files.readAllBytes(f.toPath());
            hash = DigestUtils.md5Hex(fArray);
        } catch (IOException ex) {
            Logger.getLogger(Comparador.class.getName()).log(Level.SEVERE, null, ex);
        }
        return hash;
    }
   
    public void comparar(){
        
        geraFileMap();
        int count = 0, size = fileMap.size();
        List<String> stringList = new ArrayList<>(fileMap.keySet());
        
        System.out.println(size);
        for (int i = 0; i < size; i++) {
            for (int j = i + 1; j < size; j++) {
                if(stringList.get(i).equals(stringList.get(j))){
                    System.out.println(stringList.get(i) +" = "+ stringList.get(j));
                }
                count++;
            }
        }
        System.out.println(count);
    }

Se alguém puder me sugerir alguma forma de melhorar o gargalo, agradeço.

 

Muito obrigado.

[psykotico]

Pelo que entendi, você quer apenas verificar duplicidade, sem de fato executar a deleção ou algo assim ... bem, eu faria invertido.
O hash é o seu identificador único. É por ele que você identifica que não existe um outro "arquivo idêntico". (está entre aspas porque você está usando hash MD5. O MD5 tem um problema principalmente com arquivos muito grandes, gerando hashes semelhantes para arquivos diferentes. Dependendo do caso, o SHA1 pode servir melhor a você, mas não é algo extremo. Raramente acontece, mas acontece)

Sendo assim, eu usarioa um Map<String, String> mas usando o Hash como key, e o valor sendo o Path. Então eu faria algo como:

 

    Map<String, String> fileMap = new HashMap<String, String>();
    List<File> fileList = new ArrayList<File>(FileUtils.listFiles(filePath, TrueFileFilter.INSTANCE, TrueFileFilter.INSTANCE));
    for (File file : fileList) {
        String hash = calculaHash(file);
        //verifica se já existe algum arquivo com a mesma hash
        if (fileMap.containsKey(hash)) {
            //Indica que já existe um arquivo
            System.out.println("O arquivo " + file.getAbsolutePath() + " já foi encontrado no caminho "
                    + filemap.get(hash));
        } else {
            //Inclui o arquivo na lista
            fileMap.put(hash, file.getAbsolutePath());
        }
    }

 

Assim eu percorro a lista de arquivos apenas uma vez, já verificando os arquivos durante o processo.

[HwapX]

Se o gargalo está no acesso ao disco para a leitura dos arquivos o melhor que você pode fazer é tentar evitá-las, caso os arquivos possuam tamanhos variados um meio de fazer isso seria não calcular o hash dos arquivos que possuem um tamanho único.

 

Exemplo:

Arquivo1.dat | 1mb

Arquivo2.dat | 2mb

Arquivo3.dat | 1mb

 

No exemplo não é necessário calcular o hash do Arquivo2.dat pois nenhum outro pode ser igual a ele devido a seu tamanho único, porém para isso fazer diferença uma quantidade significativa dos arquivos precisariam ter tamanhos únicos.

 

Outras ideias semelhantes também poderiam ser aplicadas sozinhas ou em conjunto.

• Desconsiderar os arquivos que tenham os 8 bytes(ou qualquer outra pequena quantidade) iniciais ou finais únicas.
• Desconsiderar os arquivos com nas extensões únicas porém ao contrário do tamanho nesse caso você precisaria ter certeza que o mesmo arquivo não pode existir com uma extensão diferente.

Quais podem ser aplicadas dependem do conteúdo dos arquivos pois todas dependem de que uma característica seja única em uma quantidade considerável dos arquivos.

 

Agora independente do problema ser no processamento ou não a ideia do @psykotico é valida, a troca do algorítimo de hash por um mais eficiente e a verificação se o arquivo é repetido imediatamente após o calculo do hash irá melhorar o desempenho.

[marcel.mc]

Olá pessoal, desculpem a demora em responder. Deixei o projeto em hiato pois não havia conseguido resolver o problema do gargalo. Gostei da proposta do @psykotico, e acabei utilizando como podem ver abaixo, porém somente isso não  resolve o problema.

 

Embora a ideia de como resolver não tenha sido tirada do posto do @HwapX , ele menciona a mesma forma. Fico grato do mesmo jeito. 

Abaixo vou postar os dois métodos e dar uma pequena explicada em como funcionam para eventuais consultas de alguém com problema semelhante:

 

public void percorreDiretoriosCalculaHashRec(File path) {
        fileMap = new HashMap<>();

        for (File f : path.listFiles()) {
            if (f.isDirectory() && f.canRead()) {                
                percorreDiretoriosCalculaHashRec(f);
            } else {
                String hash = calculaHash(f);
                if (fileMap.containsKey(hash)) {
                    System.out.println("O arquivo: " + f.getPath()
                            + " é igual a " + fileMap.get(hash).getPath());
                } else {
                    fileMap.put(hash, f);
                }
            }
        }
}

Nesse método uso exatamente a ideia proposta pelo @psykotico , percorro a árvore de diretórios recursivamente, calculo o hash de cada arquivo e insiro num map. Se aquele hash já estiver no map, imprimo os arquivos correspondentes.

 

public String calculaHash(File f) {
        byte[] fArray = null;
        String hash = null;

        try {
            if (f.length() > 1048576) {
                fArray = new byte[1048576];
                RandomAccessFile raf = new RandomAccessFile(f, "r");
                raf.read(fArray, 0, 524288);
                raf.seek(f.length() - 524288);
                raf.read(fArray, 524288, 524288);
                raf.close();
            } else {
                fArray = Files.readAllBytes(f.toPath());
            }

            hash = DigestUtils.md5Hex(fArray);
        } catch (IOException ex) {
            Logger.getLogger(Comparador.class.getName()).log(Level.SEVERE, null, ex);
        }
        return hash;
}

Nesse método, uso uma das ideias propostas pelo @HwapX. Se o arquivo tem tamanho menor ou igual 1 MB, calcula-se o hash diretamente. Se maior, uso um array de bytes que pega os primeiros 512KB e concatena com os últimos 512KB. Desse array, calculo o hash.

 

Para uma base com mais de 91K arquivos consegui que o programa fosse executado em cerca de 20 minutos. Vou marcar o tópico como encerrado, mas sintam-se a vontade para postar novas ideias ou dúvidas. Muito obrigado aos dois que responderam, suas respostas foram muito úteis.