file - huella - ¿Cuál es el algoritmo hash más rápido para verificar si dos archivos son iguales?
huella hash (11)
¿Cuál es la forma más rápida de crear una función hash que se usará para verificar si dos archivos son iguales?
La seguridad no es muy importante.
Editar: estoy enviando un archivo a través de una conexión de red, y me aseguraré de que el archivo en ambos lados sea igual
¿Por qué quieres hash?
Si desea asegurarse de que dos archivos son iguales, entonces por definición, tendrá que leer todo el archivo (a menos que sean literalmente el mismo archivo, en cuyo caso puede verlo mirando los metadatos en el sistema de archivos). De todos modos, no hay razón para hacer hash, simplemente lea sobre ellos y vea si son iguales. Hashing lo hará menos eficiente. E incluso si los hashes coinciden, aún no está seguro de si los archivos son realmente iguales.
Editar: esta respuesta se publicó antes de que la pregunta especificara algo sobre una red. Solo preguntó acerca de comparar dos archivos. Ahora que sé que hay un salto de red entre los archivos, diría que simplemente use un hash MD5 y termine con eso.
A menos que esté utilizando un hash realmente complicado o lento, cargar los datos del disco llevará mucho más tiempo que calcular el hash (a menos que use discos RAM o SSD de gama alta).
Entonces, para comparar dos archivos, use este algoritmo:
- Comparar tallas
- Compare las fechas (tenga cuidado aquí: esto le puede dar la respuesta incorrecta, debe probar si este es el caso para usted o no)
- Compara los hashes
Esto permite un error rápido (si los tamaños son diferentes, usted sabe que los archivos son diferentes).
Para hacer las cosas aún más rápido, puede calcular el hash una vez y guardarlo junto con el archivo. Guarde también la fecha y el tamaño del archivo en este archivo adicional, para que sepa rápidamente cuándo debe volver a calcular el hash o eliminar el archivo hash cuando cambie el archivo principal.
El siguiente es el código para encontrar archivos duplicados de mi proyecto personal para ordenar las imágenes que también elimina los duplicados. Según mi experiencia, usar algoritmos rápidos como CRC32 y MD5 o SHA1 fue aún más lento y no mejoró porque la mayoría de los archivos con el mismo tamaño eran duplicados, por lo que ejecutar hash dos veces era más costoso desde la perspectiva de tiempo de la CPU , este enfoque puede no ser correcto para todo tipo de proyectos, pero definitivamente es cierto para los archivos de imagen. Aquí estoy haciendo hash MD5 o SHA1 solo en los archivos con el mismo tamaño.
PD: depende del códec de Apache commons para generar hash de manera eficiente.
Uso de muestra: nuevo DuplicateFileFinder ("MD5"). FindDuplicateFilesList (filesList);
import java.io.File;
import java.io.FileInputStream;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Collection;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import org.apache.commons.codec.digest.DigestUtils;
/**
* Finds the duplicate files using md5/sha1 hashing, which is used only for the sizes which are of same size.
*
* @author HemantSingh
*
*/
public class DuplicateFileFinder {
private HashProvider hashProvider;
// Used only for logging purpose.
private String hashingAlgo;
public DuplicateFileFinder(String hashingAlgo) {
this.hashingAlgo = hashingAlgo;
if ("SHA1".equalsIgnoreCase(hashingAlgo)) {
hashProvider = new Sha1HashProvider();
} else if ("MD5".equalsIgnoreCase(hashingAlgo)) {
hashProvider = new Md5HashProvider();
} else {
throw new RuntimeException("Unsupported hashing algorithm:" + hashingAlgo + " Please use either SHA1 or MD5.");
}
}
/**
* This API returns the list of duplicate files reference.
*
* @param files
* - List of all the files which we need to check for duplicates.
* @return It returns the list which contains list of duplicate files for
* e.g. if a file a.JPG have 3 copies then first element in the list
* will be list with three references of File reference.
*/
public List<List<File>> findDuplicateFilesList(List<File> files) {
// First create the map for the file size and file reference in the array list.
Map<Long, List<File>> fileSizeMap = new HashMap<Long, List<File>>();
List<Long> potDuplicateFilesSize = new ArrayList<Long>();
for (Iterator<File> iterator = files.iterator(); iterator.hasNext();) {
File file = (File) iterator.next();
Long fileLength = new Long(file.length());
List<File> filesOfSameLength = fileSizeMap.get(fileLength);
if (filesOfSameLength == null) {
filesOfSameLength = new ArrayList<File>();
fileSizeMap.put(fileLength, filesOfSameLength);
} else {
potDuplicateFilesSize.add(fileLength);
}
filesOfSameLength.add(file);
}
// If we don''t have any potential duplicates then skip further processing.
if (potDuplicateFilesSize.size() == 0) {
return null;
}
System.out.println(potDuplicateFilesSize.size() + " files will go thru " + hashingAlgo + " hash check to verify if they are duplicate.");
// Now we will scan the potential duplicate files, and eliminate false positives using md5 hash check.
List<List<File>> finalListOfDuplicates = new ArrayList<List<File>>();
for (Iterator<Long> potDuplicatesFileSizeIterator = potDuplicateFilesSize
.iterator(); potDuplicatesFileSizeIterator.hasNext();) {
Long fileSize = (Long) potDuplicatesFileSizeIterator.next();
List<File> potDupFiles = fileSizeMap.get(fileSize);
Map<String, List<File>> trueDuplicateFiles = new HashMap<String, List<File>>();
for (Iterator<File> potDuplicateFilesIterator = potDupFiles.iterator(); potDuplicateFilesIterator
.hasNext();) {
File file = (File) potDuplicateFilesIterator.next();
try {
String md5Hex = hashProvider.getHashHex(file);
List<File> listOfDuplicatesOfAFile = trueDuplicateFiles.get(md5Hex);
if (listOfDuplicatesOfAFile == null) {
listOfDuplicatesOfAFile = new ArrayList<File>();
trueDuplicateFiles.put(md5Hex, listOfDuplicatesOfAFile);
}
listOfDuplicatesOfAFile.add(file);
} catch (IOException e) {
e.printStackTrace();
}
}
Collection<List<File>> dupsOfSameSizeList = trueDuplicateFiles.values();
for (Iterator<List<File>> dupsOfSameSizeListIterator = dupsOfSameSizeList.iterator(); dupsOfSameSizeListIterator
.hasNext();) {
List<File> list = (List<File>) dupsOfSameSizeListIterator.next();
// It will be duplicate only if we have more then one copy of it.
if (list.size() > 1) {
finalListOfDuplicates.add(list);
System.out.println("Duplicate sets found: " + finalListOfDuplicates.size());
}
}
}
return finalListOfDuplicates;
}
abstract class HashProvider {
abstract String getHashHex(File file) throws IOException ;
}
class Md5HashProvider extends HashProvider {
String getHashHex(File file) throws IOException {
return DigestUtils.md5Hex(new FileInputStream(file));
}
}
class Sha1HashProvider extends HashProvider {
String getHashHex(File file) throws IOException {
return DigestUtils.sha1Hex(new FileInputStream(file));
}
}
}
En cualquier caso, debe leer cada archivo por completo (excepto en caso de que los tamaños no coincidan), de modo que solo lea ambos archivos y compare el bloque con el bloque.
Usar hash solo gana uso de CPU y nada más. Como no escribe nada, la memoria caché del sistema operativo eliminará de manera efectiva los datos que lea, por lo tanto, en Linux, solo use la herramienta cmp
Lo que estamos optimizando aquí es el tiempo dedicado a una tarea. Desafortunadamente, no sabemos lo suficiente sobre la tarea que nos ocupa para saber cuál debería ser la solución óptima.
¿Es para una comparación de una sola vez de 2 archivos arbitrarios? Luego compare el tamaño, y luego simplemente compare los archivos, byte por byte (o mb por mb) si eso es mejor para su IO.
Si es para 2 conjuntos grandes de archivos o muchos conjuntos de archivos, y no es un ejercicio de una sola vez. pero algo que sucederá con frecuencia, entonces uno debería almacenar hashes para cada archivo. Un hash nunca es único, pero un hash con una cantidad de digamos 9 dígitos (32 bits) sería bueno para una combinación de unos 4 mil millones, y un número de 64 bits sería lo suficientemente bueno para distinguir entre 16 * 10 ^ 18 archivos de Quintillion diferentes .
Un compromiso decente sería generar 2 hashes de 32 bits para cada archivo, uno para los primeros 8k, otro para 1MB + 8k, colóquelos juntos como un solo número de 64 bits. La catalogación de todos los archivos existentes en un DB debe ser bastante rápida, y buscar un archivo candidato en este DB también debe ser muy rápido. Una vez que hay una coincidencia, la única forma de determinar si son iguales es comparar los archivos completos.
Creo en dar a las personas lo que necesitan, que no siempre es lo que creen que necesitan o lo que quieren.
Para este tipo de aplicación, Adler32 es probablemente el algoritmo más rápido, con un nivel razonable de seguridad. Para archivos más grandes, puede calcular múltiples valores de hash, por ejemplo, uno por bloque de 5 Mb del archivo, por lo tanto, disminuyendo las posibilidades de errores (es decir, de casos en que los hash son iguales, pero el contenido del archivo difiere). Además, esta configuración de valores de hash múltiple puede permitir que el cálculo del hash se implemente de forma multitramo.
Editar : (siguiendo la observación de Steven Sudit)
¡Una palabra de advertencia si los archivos son pequeños!
Las propiedades "criptográficas" de Adler32, o más bien sus debilidades, son bien conocidas especialmente para los mensajes cortos. Por esta razón, la solución propuesta debe evitarse para archivos de menos de unos pocos kilobytes.
Sin embargo, en la pregunta, el OP explícitamente busca un algoritmo rápido y renuncia a las preocupaciones sobre la seguridad . Además, la búsqueda de la velocidad puede implicar plausiblemente que uno está tratando con archivos "grandes" en lugar de pequeños. En este contexto, Adler32, posiblemente aplicado en paralelo para archivos de fragmentos de 5Mb, sigue siendo una respuesta muy válida. Alder32 tiene fama por su simplicidad y velocidad. Además, su fiabilidad, sin dejar de ser inferior a la de los CRC de la misma longitud, es bastante aceptable para mensajes de más de 4000 bytes.
Puede ver el algoritmo que utilizan los desarrolladores samba / rsync. No lo he analizado en profundidad, pero lo veo mencionado todo el tiempo. aparentemente es bastante bueno
Puedes probar MurmurHash , que fue diseñado específicamente para ser rápido, y es bastante simple de codificar. Es posible que desee y un segundo hash más seguro si MurmurHash devuelve una coincidencia, solo para estar seguro.
Si es solo uno, dado que tendrá que leer ambos archivos para generar un hash de ambos, ¿por qué no simplemente leer una pequeña cantidad de cada uno y comparar?
En su defecto, CRC es un algoritmo muy simple.
Un enfoque podría ser usar un algoritmo CRC-32 simple, y solo si los valores CRC son iguales, vuelva a ejecutar el hash con un SHA1 o algo más robusto. Un CRC-32 rápido superará en rendimiento a un hash criptográficamente seguro cualquier día.
xxhash se afirma como bastante rápido y fuerte, en cuanto a colisiones:
http://cyan4973.github.io/xxHash/
Hay una variante de 64 bits que se ejecuta "incluso más rápido" en procesadores de 64 bits que el 32, en general.
También se dice que http://code.google.com/p/crcutil es bastante rápido (y aprovecha las instrucciones de CRC de hardware donde están presentes, que probablemente sean muy rápidas, pero si no tiene hardware que las admita, no lo están). tan rápido). No sé si CRC32c es tan bueno como un hash (en términos de colisiones) como xxHash o no ...
https://code.google.com/p/cityhash/ parece similar y relacionado con Crcutil [en el sentido de que puede compilar para usar instrucciones de hardware CRC32c si se le indica].
Si "solo quieres la velocidad bruta más rápida" y no te importa tanto la calidad de la distribución aleatoria de la salida hash (por ejemplo, con conjuntos pequeños, o donde la velocidad es primordial), aquí se mencionan algunos algoritmos rápidos: http://www.sanmayce.com/Fastest_Hash/ (estos algoritmos de tipo de distribución "no del todo aleatorios" son, en algunos casos, "lo suficientemente buenos" y muy rápidos). Aparentemente FNV1A_Jesteress es el más rápido para cadenas "largas", otras posiblemente para cadenas pequeñas. http://locklessinc.com/articles/fast_hash/ también parece relacionado. No investigué para ver cuáles son las propiedades de colisión de estos.