¿Por qué los códigos hash generados por esta función no son únicos?
https://stackoverflow.com/questions/63897
-
09-06-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
Estoy probando la función VB a continuación que obtuve de una búsqueda en Google.Planeo usarlo para generar códigos hash para una comparación rápida de cadenas.Sin embargo, hay ocasiones en las que dos cadenas diferentes tienen el mismo código hash.Por ejemplo, estas cadenas
"Tamaño de montón 122Gen 1 (memoria .NET CLR w3wp): mccsmtpteweb025.20833333333333E-02"
"Tamaño del montón 122Gen 2 (memoria .NET CLR w3wp): mccsmtpteweb015.20833333333333E-02"
tiene el mismo código hash de 237117279.
Por favor dígame:- ¿Qué tiene de malo la función?- ¿Cómo puedo arreglarlo?
Gracias
martín
Private Declare Sub CopyMemory Lib "kernel32" Alias "RtlMoveMemory" (dest As Any, src As Any, ByVal bytes As Long)
Private Function HashCode(Key As String) As Long
On Error GoTo ErrorGoTo
Dim lastEl As Long, i As Long
' copy ansi codes into an array of long'
lastEl = (Len(Key) - 1) \ 4
ReDim codes(lastEl) As Long
' this also converts from Unicode to ANSI'
CopyMemory codes(0), ByVal Key, Len(Key)
' XOR the ANSI codes of all characters'
For i = 0 To lastEl - 1
HashCode = HashCode Xor codes(i) 'Xor'
Next
ErrorGoTo:
Exit Function
End Function
Solución
Apuesto a que hay más que simples "ocasiones" en las que dos cadenas generan el mismo hash usando su función.De hecho, probablemente suceda con más frecuencia de lo que cree.
Algunas cosas para darse cuenta:
Primero, habrá colisiones de hash.Sucede.Incluso con espacios realmente grandes como MD5 (128 bits), todavía hay dos cadenas que pueden generar el mismo hash resultante.Tienes que lidiar con esas colisiones creando depósitos.
En segundo lugar, un número entero largo no es realmente un gran espacio hash.Obtendrás más colisiones que si usaras más bits.
En tercer lugar, hay bibliotecas disponibles en Visual Basic (como .NET System.Security.Cryptography espacio de nombres) que hará un trabajo de hash mucho mejor que la mayoría de los simples mortales.
Otros consejos
Las dos cadenas tienen los mismos caracteres.(Tenga en cuenta el '2' y el '1' que están invertidos)
Por eso el valor hash es el mismo.
Asegúrese de que la función hash tenga en cuenta el orden de los caracteres.
Las funciones hash no garantizan la unicidad de los valores hash.Si el rango de valores de entrada (a juzgar por las cadenas de muestra) es mayor que el rango de valores de salida (por ejemplo, un entero de 32 bits), entonces la unicidad es físicamente imposible.
Si el mayor problema es que no tiene en cuenta la posición de los bytes, puedes solucionarlo así:
Private Function HashCode(Key As String) As Long
On Error GoTo ErrorGoTo
Dim lastEl As Long, i As Long
' copy ansi codes into an array of long'
lastEl = (Len(Key) - 1) \ 4
ReDim codes(lastEl) As Long
' this also converts from Unicode to ANSI'
CopyMemory codes(0), ByVal Key, Len(Key)
' XOR the ANSI codes of all characters'
For i = 0 To lastEl - 1
HashCode = HashCode Xor (codes(i) + i) 'Xor'
Next
ErrorGoTo:
Exit Function
End Function
La única diferencia es que agrega la posición de los caracteres a su valor de byte antes del XOR.
Ninguna función hash puede garantizar la unicidad.Hay ~4 mil millones de enteros de 32 bits, por lo que incluso la mejor función hash generará duplicados cuando se presente con ~4 mil millones y 1 cadenas (y probablemente mucho antes).
Pasar a hashes de 64 bits o incluso de 128 bits no es realmente la solución, aunque reduce la probabilidad de una colisión.
Si desea una mejor función hash, puede mirar los hashes criptográficos, pero sería mejor reconsiderar su algoritmo y decidir si puede lidiar con las colisiones de otra manera.
El Sistema.Seguridad.Criptografía El espacio de nombres contiene varias clases que pueden realizar hash por usted (como MD5) que probablemente los triturará mejor que usted mismo y requerirá mucho menos esfuerzo.
No siempre es necesario reinventar la rueda.
XOR simple es un mal hash:Encontrarás muchas cuerdas que chocan.El hash no depende del orden de las letras en la cadena, por un lado.
Intenta usar el hash FNV http://isthe.com/chongo/tech/comp/fnv/
Esto es realmente sencillo de implementar.Cambia el código hash después de cada XOR, por lo que las mismas letras en un orden diferente producirán un hash diferente.
Las funciones hash no están destinadas a devolver valores distintos para cadenas distintas.Sin embargo, una buena función hash debería devolver valores diferentes para cadenas que parecen iguales.Las funciones hash se utilizan para buscar por muchos motivos, incluida la búsqueda en una colección grande.Si la función hash es buena y devuelve valores del rango [0,N-1], entonces una gran colección de M objetos se dividirá en N colecciones, cada una de las cuales tendrá aproximadamente M/N elementos.De esta manera, necesita buscar solo en una matriz de M/N elementos en lugar de buscar en una matriz de M elementos.
Pero, si sólo tienes 2 cuerdas, es no ¡Más rápido para calcular el valor hash para esos!Es mejor para simplemente comparar las dos cadenas.
Una función hash interesante podría ser:
unsigned int hash(const char* name) {
unsigned mul=1;
unsigned val=0;
while(name[0]!=0) {
val+=mul*((unsigned)name[0]);
mul*=7; //you could use an arbitrary prime number, but test the hash dispersion afterwards
name++;
}
return val;
}
Le arreglé el resaltado de sintaxis.
Además, para aquellos que no estaban seguros del entorno o sugerían un hash más seguro:Es VB clásico (pre-.Net), porque .Net requeriría paréntesis para la llamada a CopyMemory.
IIRC, no hay hashes seguros integrados para Classic VB.Tampoco hay mucho en la web, por lo que esta puede ser su mejor opción.
No veo muy bien el entorno en el que trabajas.¿Es este código .Net?Si realmente desea buenos códigos hash, le recomendaría buscar hashes criptográficos (algoritmos probados) en lugar de intentar escribir los suyos propios.
Por cierto, ¿podrías editar tu publicación y pegar el código como muestra de código (ver barra de herramientas)?Esto facilitaría la lectura.
"No hagas eso."
Escribir su propia función hash es un gran error, porque su lenguaje ciertamente ya tiene una implementación de SHA-1, que es una función hash perfectamente buena.Si solo necesita 32 bits (en lugar de los 160 que proporciona SHA-1), simplemente use los últimos 32 bits de SHA-1.
Este hash particular funciona XOR todos los caracteres de una cadena.Desafortunadamente XOR es asociativo:
(a XOR b) XOR c = a XOR (b XOR c)
Por lo tanto, cualquier cadena con los mismos caracteres de entrada dará como resultado el mismo código hash.Las dos cadenas proporcionadas son iguales, excepto por la ubicación de dos caracteres, por lo que deben tener el mismo código hash.
Es posible que necesite encontrar un algoritmo mejor; MD5 sería una buena opción.
La operación XOR es conmutativa;es decir, cuando se aplica XOR a todos los caracteres de una cadena, el orden de los caracteres no importa.Todos los anagramas de una cadena producirán el mismo hash XOR.
En su ejemplo, su segunda cadena se puede generar a partir de la primera intercambiando el "1" después de "...Gen" con el primer "2" a continuación.
No hay nada malo con tu función.Todas las funciones hash útiles a veces generarán colisiones y su programa debe estar preparado para resolverlas.
Se produce una colisión cuando una entrada cambia a un valor ya identificado con una entrada anterior.Si un algoritmo hash no pudiera generar colisiones, los valores hash tendrían que ser tan grandes como los valores de entrada.Un algoritmo hash de este tipo sería de uso limitado en comparación con simplemente almacenar los valores de entrada.
-Alabama.
Aquí hay una implementación visual básica del hash MD5.
