¿Qué es una buena función hash?

Question

¿Qué es una buena función hash? Vi una gran cantidad de funciones de hash y aplicaciones en mis cursos de estructuras de datos en la universidad, pero en general me di cuenta de que es bastante difícil hacer una buena función de hash. Como regla de oro para evitar colisiones mi profesor dijo que:

function Hash(key) 
    return key mod PrimeNumber 
end 

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

con el número primo a ser el tamaño de la tabla hash. Entiendo que es una función algo buena para evitar colisiones y una rápida, pero ¿cómo puedo hacer una mejor? ¿Hay mejores funciones hash para las teclas de cadena frente a las teclas numéricas?

Answer 1

Para realizar búsquedas de tablas hash "normales" básicamente en cualquier tipo de datos, este de Paul Hsieh es el mejor que he usado.

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

Si se preocupan por criptográficamente seguro o cualquier otra cosa más avanzado, a continuación, tu caso es distinto. Si solo quieres una función hash de propósito general kick ass para una búsqueda de tabla hash, entonces esto es lo que estás buscando.

Answer 2

Diría que la principal regla empírica es no hacer las suyas propias. Intente usar algo que haya sido probado minuciosamente, por ejemplo, SHA-1 o algo parecido.

Answer 3

No existe la "buena función hash" para hash universales (ed. Sí, sé que existe el hash universal, pero eso no es lo que quise decir). Dependiendo del contexto, diferentes criterios determinan la calidad de un hash. Dos personas ya mencionaron SHA. Este es un hash criptográfico y no es para nada bueno para las tablas hash que probablemente quiera decir.

Las tablas hash tienen requisitos muy diferentes. Pero aún así, encontrar una buena función hash universalmente es difícil porque diferentes tipos de datos exponen información diferente que puede ser hash. Como regla general, es bueno tener en cuenta toda la información de que un tipo posee igualmente. Esto no siempre es fácil o incluso posible. Por razones de estadísticas (y, por lo tanto, de colisión), también es importante generar una buena dispersión sobre el espacio problemático, es decir, todos los objetos posibles. Esto significa que al mezclar números entre 100 y 1050 no es bueno dejar que el dígito más significativo juegue un papel importante en el hash porque para ~ 90% de los objetos, este dígito será 0. Es mucho más importante dejar que los tres últimos los dígitos determinan el hash.

De forma similar, cuando se trata de cadenas, es importante considerar todos los caracteres, excepto cuando se sabe de antemano que los primeros tres caracteres de todas las cadenas serán los mismos; 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 The Art of Computer Programming, vol. 3. Otra buena lectura es Julienne Walker's The Art of Hashing.

Answer 4

Una función de hash buena tiene las siguientes propiedades:

1. dado un hash de un mensaje que es computacionalmente imposible para un atacante para encontrar otro mensaje de tal manera que sus valores hash son idénticos.

2. Dado un par de mensaje, m 'y m, es computacionalmente imposible encontrar dos de tal manera que que h (m) = h (M')

Los dos casos son no lo mismo. En el primer caso, hay un hash preexistente para el que está intentando encontrar una colisión. En el segundo caso, está tratando de encontrar cualquier dos mensajes que colisionan. La segunda tarea es significativamente más fácil debido a la "paradoja" del cumpleaños.

Donde el rendimiento no es un gran problema, siempre debe usar una función de hash segura.Hay ataques muy inteligentes que se pueden realizar forzando colisiones en un hash. Si utilizas algo fuerte desde el principio, te protegerás de esto.

No utilice MD5 o SHA-1 en nuevos diseños. La mayoría de los criptógrafos, incluido yo, los considerarían rotos. La principal fuente de debilidad en ambos diseños es que la segunda propiedad, que describí anteriormente, no es válida para estas construcciones. Si un atacante puede generar dos mensajes, my m ', ambos hash al mismo valor pueden usar estos mensajes en su contra. SHA-1 y MD5 también sufren ataques de extensión de mensajes, que pueden debilitar fatalmente su aplicación si no tiene cuidado.

Un hash más moderno como Whirpool es una mejor opción. No sufre estos ataques de extensión de mensajes y utiliza las mismas matemáticas que usa AES para probar la seguridad contra una variedad de ataques.

Espero que ayude!

Answer 5

Hay dos propósitos principales de funciones hash:

• para dispersar uniformemente los puntos de datos en n bits.
• para identificar de forma segura los datos de entrada.

Es imposible recomendar un hash sin saber para qué lo está utilizando.

Si solo está haciendo una tabla hash en un programa, entonces no tiene que preocuparse de cuán reversible o hackable es el algoritmo ... SHA-1 o AES son completamente innecesarios para esto, usted será mejor usar un variation of FNV. FNV logra una mejor dispersión (y, por lo tanto, menos colisiones) que un mod primo simple como usted mencionó, y es más adaptable a diferentes tamaños de entrada.

Si está utilizando los valores hash para ocultar y autenticar la información pública (como el uso de una contraseña o un documento), debe utilizar uno de los principales algoritmos hash examinados por el escrutinio público. The Hash Function Lounge es un buen lugar para comenzar.

Answer 6

Este es un ejemplo de uno bueno y también un ejemplo de por qué nunca querría escribir uno. Es una Fowler/Noll/Vo (FNV) Hash, que es a partes iguales genio de la informática y el vudú pura:

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 his site el algoritmo FVN-1A sobre el algoritmo original FVN-1: el algoritmo mejorado dispersa mejor el último byte en el hash. Ajusté el algoritmo en consecuencia.

Answer 7

Lo que estás diciendo aquí es que quieres tener uno que use tiene resistencia a la colisión. Intenta usar SHA-2.O intente utilizar un (bueno) cifrado de bloque en una función de compresión unidireccional (nunca antes lo había intentado), como AES en el modo Miyaguchi-Preenel. El problema con eso es que necesita:

1) tener un IV. Intenta usar los primeros 256 bits de las partes fraccionarias de la constante de Khinchin o algo así. 2) tienen un esquema de relleno. Fácil. Barrow de un hash como MD5 o SHA-3 (Keccak [pronunciado 'ket-chak']). Si no te importa la seguridad (algunos otros dijeron esto), mira FNV o lookup2 de Bob Jenkins (en realidad, yo soy el primero que recomienda la búsqueda2) También prueba MurmurHash, es rápido (mira esto: .16 cpb).