algorithm - son - ¿Qué es una buena función hash?

tipos de funciones 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 general para evitar colisiones, mi profesor dijo que:

function Hash(key)
  return key mod PrimeNumber
end

(mod es el operador% en C e idiomas similares)

con el número primo para ser del 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

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

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 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 2

Hay dos propósitos principales de las funciones hash:

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

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

Si solo estás creando una tabla hash en un programa, entonces no tienes que preocuparte por cuán reversible o pirateable es el algoritmo ... SHA-1 o AES son completamente innecesarios para esto, estarías mejor usando una variación de 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), entonces debe usar uno de los principales algoritmos de hash examinados por el escrutinio público. El Hash Function Lounge es un buen lugar para comenzar.

Answer 3

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 necesitas:

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 por Bob Jenkins (en realidad, yo soy el primero que recomienda búsquedas2). También prueba MurmurHash, es rápido (mira esto: .16 cpb )

Answer 4

No existe una "buena función hash" para hashes universales (ed. Sí, sé que existe algo así como "hashing 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 considerar toda la información que un tipo posee por igual. 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 tener en cuenta todos los caracteres, excepto cuando se sabe de antemano que los tres primeros 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 The Art of Hashing de Julienne Walker.

Answer 5

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 te preocupa la seguridad criptográfica o cualquier otra cosa más avanzada, entonces YMMV. 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 6

Una buena función hash tiene las siguientes propiedades:

1. Dado un algoritmo hash de un mensaje, es computacionalmente inviable para un atacante encontrar otro mensaje de modo que sus hashes sean idénticos.

2. Dado un par de mensajes, m ''ym, no es factible computacionalmente encontrar dos tales que h (m) = h (m'')

Los dos casos no son lo mismo. En el primer caso, hay un hash preexistente para el que está intentando encontrar una colisión. En el segundo caso, estás tratando de encontrar dos mensajes que chocan. 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 segura de hash. 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 use 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 7

Yo diría que la principal regla empírica no es hacer tu propia. Intente usar algo que haya sido probado exhaustivamente, por ejemplo, SHA-1 o algo similar.