uuidgen - ¿El hash de un GUID es único?

uuid generator

Question

Creo un GUID (como una cadena) y obtengo el hash del mismo. ¿Puedo considerar este hash como único?

Answer 1

Ninguna función hash que reduzca un bloque de datos de tamaño arbitrario a un número de bits de tamaño fijo producirá una correspondencia de 1 a 1 entre los dos. Siempre existirá la posibilidad de que se reduzcan dos bloques de datos diferentes a la misma secuencia de bits en el hash.

Los buenos algoritmos de hash minimizan la probabilidad de que esto ocurra, y, en general, mientras más bits haya en el hash, menor será la probabilidad de una colisión.

Answer 2

No está garantizado , debido a las colisiones hash . El GUID en sí mismo está casi garantizado.

Por razones prácticas, probablemente pueda asumir que un hash es único, pero ¿por qué no usar el GUID?

Answer 3

Nop.

Vea aquí, si quiere un mini GUID: http://blogs.msdn.com/oldnewthing/archive/2008/06/27/8659071.aspx

Answer 4

Si usa hash criptográfico (MD5, SHA1, RIPEMD160), el hash será único (colisiones de módulo que son muy improbables: SHA1 se utiliza, por ejemplo, para firmas digitales, y MD5 también es resistente a colisiones en entradas aleatorias ). Sin embargo, ¿por qué quieres hash un GUID?

Answer 5

En una palabra, no.

Supongamos que su hash tiene menos bits que el GUID, por el principio del pozo de paloma, debe existir más de un mapeo de GUID -> hash simplemente porque hay menos hashes que GUIDS.

Si suponemos que el hash tiene un número de bits mayor que el GUID, existe una posibilidad muy pequeña, pero finita, de una colisión, suponiendo que está utilizando una buena función hash.

Answer 6

No es tan confiablemente único como el GUID en sí, no.

Solo para expandir, estás reduciendo tu unicidad en un factor de 4, pasando de 16 bytes a 4 bytes de combinaciones posibles.

Como se señaló en los comentarios, el tamaño de hash hará la diferencia. La cosa de 4 bytes fue una suposición, horrible en el mejor de los casos, sé que se puede usar en .NET, donde el tamaño de hash predeterminado es de 4 bytes (int). Así que puedes reemplazar lo que dije arriba con cualquier tamaño de byte que tu hash pueda ser.

Answer 7

No, y no asumiría la singularidad de ningún valor hash. Eso no debería importar porque los valores de hash no necesitan ser únicos, solo necesitan distribuirse uniformemente en todo su rango. Cuanto más pareja sea la distribución, menos colisiones tendrá lugar (en la tabla hash). Menos colisiones significan mejor rendimiento de hashtable.

fyi Para una buena descripción de cómo funcionan las tablas hash, lea la respuesta aceptada a ¿Qué son hashtables y hashmaps y sus casos de uso típicos?