Sto per sviluppare un programma che rileva i file duplicati e mi chiedevo quale sarebbe il metodo migliore / più veloce per farlo? Sono più interessato a quale sarebbe il miglior algoritmo di hash per fare questo? Ad esempio, stavo pensando di ottenere l'hash di ogni contenuto di file e quindi raggruppare gli hash uguali. Inoltre, dovrebbe esserci un limite per ciò che può essere la dimensione massima del file o c'è un hash adatto per file di grandi dimensioni?
Il modo più veloce è solo per confrontare il codice hash di file con le stesse dimensioni.
Questa è l'idea di questa risposta su SO (vedi la seconda riga di comando e le sue spiegazioni).
Non ci sono problemi di sicurezza durante il rilevamento di file duplicati, quindi consiglierei un codice di hashing veloce. Ad esempio il progetto ccache utilizza MD4:
ccache uses MD4, a very fast cryptographic hash algorithm, for the hashing. (MD4 is nowadays too weak to be useful in cryptographic contexts, but it should be safe enough to be used to identify recompilations.)
Se due file hanno le stesse dimensioni e lo stesso codice hash, probabilmente sono uguali. Ma ci sarà ancora una piccola possibilità che questi due file siano diversi (eccetto se la dimensione del file è inferiore alla dimensione del codice hash).
Come suggerisci nella tua domanda, i falsi positivi possono accadere più frequentemente in quanto le dimensioni del file sono maggiori.
Ci sono due opzioni per risolvere il problema dei file di grandi dimensioni:
Il limite per considerare un file sufficientemente grande da richiedere un secondo controllo dipende da quanto è critica l'applicazione.
Infine, il modo più sicuro di procedere è:
Se stai ottimizzando il tempo dello sviluppatore , sei sulla buona strada; se si sceglie un algoritmo di hash abbastanza accettabile, le collisioni dovrebbero essere estremamente improbabili (vedere il collegamento di Yanis, ma a parte quelle, in genere si usa MD5 o SHA1 per gli hash, sebbene MD5 non sia raccomandato se si è consapevoli della sicurezza). Vorrei andare con qualcosa che è pronto all'uso nel tuo ambiente di programmazione, dal momento che l'implementazione e il mantenimento di un algoritmo di hashing potrebbero non valere la pena.
Se sei preoccupato delle prestazioni di runtime , ci sono alcune cose che puoi fare per ottimizzare il processo. Ci sono probabilmente due aree lente: la lettura di tutti i dati e il processo di hashing vero e proprio. Per darti un'idea, la maggior parte degli algoritmi di hash (anche quelli più lenti e crittografici) possono tipicamente passare attraverso un poche centinaia di MB al secondo . Quindi, a meno che non si stia utilizzando un SSD (molto veloce), il collo di bottiglia è più probabile che sia un disco IO, quindi dovresti provare a ridurlo al minimo.
Un'idea sarebbe quella di raggruppare prima i file per dimensione ed escludere qualsiasi file con dimensioni univoche. Quindi hash i primi kB di ogni file rimanente e utilizzarlo per produrre un elenco di potenziali corrispondenze (di nuovo, solo confrontare con file della stessa identica dimensione). Dovresti quindi solo ottenere l'hash completo di queste potenziali corrispondenze, a differenza di ogni file sul disco. A seconda delle esatte caratteristiche del disco, questo può essere più veloce della semplice lettura di tutto (a meno che non ci sia un numero molto elevato di duplicati e stiamo perdendo il nostro tempo cercando di escluderli - un peggio caso specifico). Questo dovrebbe funzionare abbastanza bene per carichi di lavoro tipici, con una maggiore conoscenza sull'ambiente reale, potresti probabilmente regolarlo molto di più.
Leggi altre domande sui tag algorithms file-systems hashing search