¿Qué es una buena Función Hash?

https://stackoverflow.com/questions/34595

09-06-2019
|

Pregunta

¿Qué es una buena función Hash?Vi un montón de función hash y aplicaciones en mi estructuras de datos de los cursos en la universidad, pero sobre todo me tengo que es bastante difícil hacer una buena función hash.Como una regla de oro para evitar colisiones mi profesor dijo que:

function Hash(key)
  return key mod PrimeNumber
end

(mod es el operador % en C y lenguajes similares)

con el primer número sea el tamaño de la tabla hash.Me sale que es un poco buena función para evitar colisiones y rápido, pero ¿cómo puedo hacer mejor?Hay mejor las funciones de hash para la cadena de las claves con las teclas numéricas?

Solución

Para hacer "normal" de la tabla hash búsquedas en básicamente cualquier tipo de datos - por Pablo Hsieh es la mejor que he usado nunca.

http://www.azillionmonkeys.com/qed/hash.html

Si usted se preocupa por criptográficamente seguro o cualquier otra cosa más avanzadas, luego de YMMV.Si lo que desea es una patada en el culo de propósito general de la función hash de una búsqueda de la tabla hash, entonces esto es lo que estás buscando.

Otros consejos

No hay tal cosa como una "buena función hash" para universal hashes (ed.sí, sé que no hay tal cosa como "universal hash" pero eso no es a lo que me refería).Dependiendo del contexto, los diferentes criterios que determinan la calidad de un hash.Dos personas ya se mencionó SHA.Este es un hash criptográfico y no es en absoluto bueno para tablas de hash, que probablemente significa.

Las tablas Hash tienen requisitos muy diferentes.Pero aún así, la búsqueda de una buena función hash universal es difícil debido a que los diferentes tipos de datos exponer distinta información que puede ser de hash.Como regla general, es bueno tener en cuenta todos la información que un tipo tiene igual.Esto no es siempre fácil, ni siquiera posible.Por razones de estadísticas (y por lo tanto el choque), también es importante generar una buena repartidas en el espacio del problema, es decir,todos los objetos posibles.Esto significa que cuando hash números entre 100 y 1050 no es bueno dejar que el dígito más significativo juegan un papel importante en el hash, porque para ~ 90% de los objetos, esta cifra será de 0.Es mucho más importante que los tres últimos dígitos determinar el hash.

Del mismo modo, cuando las cadenas de hash es importante tener en cuenta que todos los personajes – excepto cuando se sabe de antemano que los tres primeros caracteres de todas las cadenas será el mismo;teniendo en cuenta estos entonces es un desperdicio.

Este es en realidad uno de los casos en los que aconsejo leer lo que Knuth tiene que decir en El Arte de la Programación de computadoras, vol.3.Otra buena lectura es Juliana Walker El Arte de la mezcla.

Hay dos propósitos principales de las funciones de hash:

para dispersar a los puntos de datos de manera uniforme en n bits.
para identificar de forma segura los datos de entrada.

Es imposible recomendar un hash sin saber de lo que usted lo está utilizando para.

Si sólo estás haciendo una tabla hash en un programa, entonces usted no necesita preocuparse acerca de cómo reversible o hackeable el algoritmo es...SHA-1 o AES es completamente innecesario para esto, sería mejor usar un variación de la FNV.FNV, logra una mejor dispersión (y por lo tanto menos colisiones) que un simple primer mod como usted ha mencionado, y es más adaptable a diferentes tamaños de entrada.

Si usted está usando el hash para ocultar y autenticar la información pública (tales como el hash de una contraseña, o un documento), entonces usted debe utilizar uno de los principales algoritmos de hash investigados por el escrutinio público. La Función De Hash, Salón es un buen lugar para empezar.

Este es un ejemplo de una buena y también un ejemplo de por qué usted nunca querría escribir una.Es un Fowler / Noll / Vo (FNV) Hash que es a partes iguales de ciencias de la computación genio y puro vudú:

unsigned fnv_hash_1a_32 ( void *key, int len ) {
    unsigned char *p = key;
    unsigned h = 0x811c9dc5;
    int i;

    for ( i = 0; i < len; i++ )
      h = ( h ^ p[i] ) * 0x01000193;

   return h;
}

unsigned long long fnv_hash_1a_64 ( void *key, int len ) {
    unsigned char *p = key;
    unsigned long long h = 0xcbf29ce484222325ULL;
    int i;

    for ( i = 0; i < len; i++ )
      h = ( h ^ p[i] ) * 0x100000001b3ULL;

   return h;
}

Editar:

Landon Curt Noll recomienda en su sitio la FVN-1A algoritmo sobre el original FVN-1 algoritmo:El algoritmo mejorado mejor dispersa el último byte en el hash.He ajustado el algoritmo en consecuencia.

Yo diría que la principal regla de oro es no rodar su propio.Trate de usar algo que ha sido probado a fondo, por ejemplo, SHA-1, o algo a lo largo de esas líneas.

Una buena función hash tiene las siguientes propiedades:

Dado un hash de un mensaje es computacionalmente inviable que un atacante para encontrar otro mensaje de que sus guiones son idénticos.
Le da un par de mensajes, m' y m, es computacionalmente imposible encontrar a dos tal que h(m) = h(m')

Los dos casos son no la misma.En el primer caso, no es un pre-existentes hash que usted está tratando de encontrar una colisión para.En el segundo caso, usted está tratando de encontrar cualquier dos de los mensajes que entran en colisión.La segunda tarea es mucho más fácil debido a que el cumpleaños de "la paradoja."

Donde el rendimiento no es tan grande de un problema, usted siempre debe usar una función de hash seguro.Hay muy inteligente ataques que se pueden realizar por obligando a las colisiones de hash.Si usas algo fuerte desde el principio, vas a proteger a ti mismo en contra de estos.

No utilizar MD5 o SHA-1 en los nuevos diseños.La mayoría de los codificadores, los que me incluyo, de considerar que rota.El principio de la fuente de debilidad en ambos de estos diseños es que la segunda propiedad, que he descrito, no se sostiene que estas construcciones.Si un atacante puede generar dos mensajes, m y m', que tanto hash para el mismo valor que puede utilizar estos mensajes en contra de usted.SHA-1 y MD5 también sufren de mensaje de la extensión de los ataques, que pueden fatalmente debilitar su solicitud si usted no es cuidadoso.

Una más moderna hash tales como bañera de Hidromasaje es una mejor opción.No sufren de estos mensaje de la extensión de los ataques y utiliza las mismas matemáticas como AES utiliza para probar la seguridad contra una variedad de ataques.

Espero que ayude!

Lo que estamos diciendo aquí es que quieres tener uno que utiliza tiene resistencia al choque.Trate de usar SHA-2.O trate de usar un buen sistema de cifrado de bloque en una función de compresión (nunca trató de que antes), como AES en Miyaguchi-Preenel modo.El problema con esto es que usted necesita:

1) tener un IV.Trate de usar los primeros 256 bits de las partes fraccionarias de Khinchin constante o algo por el estilo.2) tener un esquema de relleno.Fácil.Barrow es un hash como MD5 o SHA-3 (Keccak [se pronuncia 'cy-chak']).Si usted no se preocupan por la seguridad (un par de otros, dijo que este), mirar FNV o lookup2 por Bob Jenkins (en realidad, yo soy el primero que reccomends lookup2) También intenta MurmurHash, es rápido (verifique esto:.16 cpb).

Licenciado bajo: CC-BY-SA con atribución

No afiliado a StackOverflow