Tratando de mejorar el rendimiento de una función que compara cadenas, decidí compararlas comparando sus valores hash. Entonces, ¿hay una garantía si el hash de 2 cadenas muy largas son iguales entre sí, entonces las cadenas también son iguales entre sí?Comparando cadenas largas por sus valores hash
Si bien se garantiza que 2 cadenas idénticas le darán hashes iguales, al revés no es cierto: para un hash dado, siempre hay varias cadenas posibles que producen el mismo hash. Esto es cierto debido a PigeonHole principle.
Dicho esto, las posibilidades de que 2 cadenas diferentes produzcan el mismo hash se pueden hacer infinitesimales, hasta el punto de considerarse equivalentes a nulas.
Un ejemplo bastante clásico de tal hash es MD5, que tiene una distribución casi perfecta de 128 bits. Lo que significa que tiene una posibilidad en 2^128 que 2 cadenas diferentes produzcan el mismo hash. Bueno, básicamente, casi lo mismo que imposible.
Curiosamente, MD5 se ha roto: un atacante puede _intencionalmente_ crear una cadena que haste a cualquier valor dado. Simplemente no hay suficientes bits, por lo que SHA se ha convertido en el estándar actual en criptografía. –
Sí, esa es la gran diferencia entre obtener una "colisión aleatoria" y obtener una "colisión intencional". En el frente aleatorio, MD5 sigue siendo lo suficientemente bueno. Ahora, si el sistema debe tener en cuenta el riesgo de colisión intencional (que no siempre es necesario), entonces sí, MD5 ya no es lo suficientemente bueno. – Cyan
¿cómo la generación y comparación de hashes MD5 puede ser más rápida que la comparación de cadenas originales?!? – Aprillion
No estoy seguro, si su rendimiento será mejorado. Ambos: construir hash + comparar enteros y simplemente comparar cadenas usando iguales tienen la misma complejidad, que se establece en O (n), donde n es el número de caracteres.
En el caso común simple donde se deben comparar dos cadenas largas para determinar si son idénticas o no, una comparación simple sería muy preferible a un hash, por dos razones. Primero, como lo señala @wildplasser, el hash requiere que todos los bytes de ambas cadenas se atraviesen para calcular los dos valores hash, mientras que la comparación simple es rápida, y solo necesita recorrer bytes hasta que se encuentre la primera diferencia, que puede ser mucho menor que la longitud completa de la cuerda. Y en segundo lugar, se garantiza una simple comparación para detectar cualquier diferencia, mientras que el hash solo da una alta probabilidad de que sean idénticos, como lo señalan @AdamLiss y @Cyan.
Hay, sin embargo, varios casos interesantes donde la comparación de hash se puede emplear con gran ventaja. Como lo menciona @Cyan si la comparación debe hacerse más de una vez, o debe almacenarse para su uso posterior, entonces el hash puede ser más rápido. Un caso no mencionado por otros es si las cadenas están en diferentes máquinas conectadas a través de una red local o Internet. Pasar una pequeña cantidad de datos entre las dos máquinas generalmente será mucho más rápido. El primer control más simple es comparar el tamaño de los dos, si es diferente, ya está hecho. De lo contrario, calcule el hash, cada uno en su propia máquina (suponiendo que pueda crear el proceso en la máquina remota) y nuevamente, si es diferente, termine. Si los valores hash son los mismos, y si debe tener certeza absoluta, no hay un acceso directo fácil para esa certeza. El uso de compresión sin pérdida en ambos extremos permitirá que se transfieran menos datos para la comparación. Y, por último, si las dos cadenas están separadas por el tiempo, como alude @Cyan, si desea saber si un archivo ha cambiado desde ayer, y ha almacenado el hash de la versión de ayer, puede comparar el hash de hoy con él .
Espero que esto ayude a estimular algunas ideas "listas para usar" para alguien.
Creo que sí. Los hash son representaciones absolutas de los datos que contienen. Por lo tanto, las cadenas iguales deben tener hashes iguales. – Jeremy1026
¿Por qué no comparar las cuerdas en primer lugar? El cálculo de los hash te obligará a inspeccionar cada carácter de ambas cadenas. También lo hace comparándolos (pero eso puede devolver "desigual" en el primer desequilibrio) – wildplasser
@ Jeremy1026: Eso simplemente no es cierto. Supongamos que utiliza un hash de 4 bits. 4 bits pueden contener 2^4 = 16 valores diferentes, por lo que nunca se puede distinguir entre más de 16 cadenas con ese hash. En la práctica, los hash son generalmente cientos de bits, pero siempre hay un límite en la cantidad de elementos que pueden distinguir.Por supuesto, las colisiones son extremadamente improbables con un hash suficientemente largo, pero nunca hay una garantía de que las diferentes cadenas tengan hashes diferentes. –