Probé algunos algoritmos diferentes, midiendo la velocidad y el número de colisiones .

Usé tres conjuntos de claves diferentes:

• Una lista de 216,553 palabras en inglés ^{🕗  archivo} (en minúsculas)
• Los números "1" a "216553" (piense en los códigos postales y cómo un hash deficiente acabó con msn.com ^{🕗  archivo} )
• 216,553 » GUID aleatorios «(es decir, tipo 4 uuid )

Para cada corpus, el número de colisiones y el tiempo medio empleado en el hash fue grabado.

Probé:

• DJB2
• DJB2a (variante que usa xor en lugar de +)
• FNV-1 (32 bits)
• FNV-1a (32 bits)
• SDBM
• CRC32
• Murmur2 (32 bits)
• SuperFastHash

Resultados

Cada resultado contiene el tiempo hash promedio y el número de colisiones

Hash Lowercase Random UUID Numbers ============= ============= =========== ============== Murmur 145 ns 259 ns 92 ns 6 collis 5 collis 0 collis FNV-1a 152 ns 504 ns 86 ns 4 collis 4 collis 0 collis FNV-1 184 ns 730 ns 92 ns 1 collis 5 collis 0 collis▪ DBJ2a 158 ns 443 ns 91 ns 5 collis 6 collis 0 collis▪▪▪ DJB2 156 ns 437 ns 93 ns 7 collis 6 collis 0 collis▪▪▪ SDBM 148 ns 484 ns 90 ns 4 collis 6 collis 0 collis** SuperFastHash 164 ns 344 ns 118 ns 85 collis 4 collis 18742 collis CRC32 250 ns 946 ns 130 ns 2 collis 0 collis 0 collis LoseLose 338 ns - - 215178 collis 

Notas :

• El El algoritmo LoseLose (donde hash = hash + carácter) es realmente horrible . Todo choca en los mismos 1375 cubos
• SuperFastHash es rápido, y las cosas se ven bastante dispersas; Dios mío, el número colisiones. Espero que el tipo que lo transfirió se haya equivocado; es bastante malo
• CRC32 es bastante bueno . Más lento y una tabla de búsqueda de 1k

¿Se producen realmente las colisiones?

Sí. Comencé a escribir mi programa de prueba para ver si las colisiones hash realmente ocurren, y no son solo una construcción teórica.De hecho, ocurren:

Colisiones FNV-1

• creamwove choca con quists

FNV -1a colisiones

• costarring colisiona con liquid
• declinate choca con macallums
• altarage choca con zinke
• altarages choca con zinkes

Murmur2 colisiones

• cataract choca con periti
• roquette choca con skivie
• shawl choca con stormbound
• dowlases choca con tramontane
• cricketings choca con twanger
• longans choca con whigs

colisiones DJB2

• hetairas choca con mentioner
• heliotropes choca con neurospora
• depravement choca con serafins
• stylist choca con subgenera
• joyful choca con synaphea
• redescribed choca con urites
• dram choca con vivency

DJB2a collisions

• haggadot choca con loathsomenesses
• adorablenesses colisiona con rentability
• playwright colisiona con snush
• playwrighting choca con snushing
• treponematoses choca con waterbeds

colisiones CRC32

• codding choca con gnu
• exhibiters choca con schlager

colisiones SuperFastHash

• dahabiah choca con drapability
• encharm choca con enclave
• grahams choca con gramary
• … snip 79 colisiones …
• night choca con vigil
• choca con vigils
• finks choca con vinic

Aleatoriedad

La otra medida subjetiva es la distribución aleatoria de los hashes. El mapeo de las HashTables resultantes muestra cuán uniformemente se distribuyen los datos. Todas las funciones hash muestran una buena distribución al mapear la tabla linealmente:

O como Hilbert Map ( XKCD siempre es relevante ):

Excepto cuando se procesan cadenas de números ("1", "2", …, "216553") (por ejemplo, códigos postales ), donde comienzan los patrones para emerger en la mayoría de los algoritmos hash:

SDBM :

DJB2a :

FNV-1 :

Todos excepto

Si desea crear un mapa hash a partir de un diccionario que no cambia, puede considerar el hash perfecto https://en.wikipedia.org/wiki/Perfect_hash_function : durante la construcción de la función hash y la tabla hash, puede garantizar, para un conjunto de datos determinado, que no habrá colisiones.

Comentarios

• Aquí ‘ s más sobre (mínimo) Perfect Hashing burtleburtle.net/bob/hash/perfect.html incluidos los datos de rendimiento, aunque no ‘ no utiliza el procesador más actual, etc.
• Es ‘ bastante obvio, pero vale la pena señalar que para garantizar que no haya colisiones, las claves tendrían que ser del mismo tamaño que los valores, a menos que Hay restricciones sobre los valores que el algoritmo puede aprovechar.
• @ devios1 Su declaración no tiene sentido. Primero, los valores en una tabla hash, perfectos o no, son independientes de las claves. En segundo lugar, una tabla hash perfecta es solo una matriz lineal de valores, indexados por el resultado de la función que ha sido diseñada para que todos los índices sean únicos.
• @MarcusJ El hash perfecto se usa generalmente con menos de 100 claves, pero eche un vistazo a cmph.sourceforge.net … todavía muy por debajo de su rango.
• @DavidCary Nada en su enlace apoya su reclamo. Posiblemente haya confundido O (1) con » sin colisiones «, pero no son ‘ t en todo lo mismo. Por supuesto, el hash perfecto garantiza que no haya colisiones, pero requiere que todas las claves se conozcan de antemano y que sean relativamente pocas. (Pero vea el enlace a cmph arriba.)

Aquí hay una lista de funciones hash, pero la versión corta es:

Si solo desea tener una buena función hash , y no puedo esperar, djb2 es una de las mejores funciones de hash de cadenas que conozco. Tiene una excelente distribución y velocidad en muchos conjuntos diferentes de claves y tamaños de tabla

unsigned long hash(unsigned char *str) { unsigned long hash = 5381; int c; while (c = *str++) hash = ((hash << 5) + hash) + c; /* hash * 33 + c */ return hash; } 

Comentarios

• En realidad, djb2 es sensible a cero, como la mayoría de las funciones hash simples, por lo que puede romper fácilmente dichos hash.Tiene un sesgo incorrecto, demasiadas colisiones y una mala distribución, se rompe en la mayoría de las pruebas de calidad de smhasher: consulte github.com/rurban/smhasher/blob/master/doc/bernstein Su base de datos cdb lo usa, pero yo no ‘ no lo usaría con acceso público.
• DJB es bastante malo desde el punto de vista de rendimiento y distribución. Yo no ‘ no lo usaría hoy.
• @ConradMeyer Apuesto ‘, DJB puede acelerarse si un factor de tres como en esta pregunta mía y luego ‘ probablemente superará a la mayoría de los algoritmos utilizables. En cuanto a la distribución, estoy de acuerdo. Un hash que produzca colisiones incluso para cadenas de dos letras no puede ‘ ser realmente bueno.
• Chicos, tengo dudas. Estás diciendo que djb2 es malo, pero los resultados de la prueba de la respuesta aceptada muestran que es bueno.
• Al menos podrías usar un primo sensible que produzca menos colisiones en lugar de 33. stackoverflow.com/a/2816747/21499

CityHash de Google es el algoritmo que está buscando. No es bueno para la criptografía, pero es bueno para generar hash únicos.

Lea el blog para obtener más detalles y el El código está disponible aquí .

CityHash está escrito en C ++. También hay un puerto C simple .

Acerca de la compatibilidad con 32 bits:

Todas las funciones de CityHash están ajustadas para procesadores de 64 bits. Dicho esto, se ejecutarán (excepto los nuevos que usan SSE4.2) en código de 32 bits. Sin embargo, no serán muy rápidos. Es posible que desee utilizar Murmur o algo más en código de 32 bits.

Comentarios

• ¿CityHash se pronuncia de forma similar a » City Sushi? »
• Tiene un mire también SipHash, está destinado a reemplazar MurmurHash / CityHash / etc.: 131002.net/siphash
• Consulte también FarmHash, un sucesor de CitHash. code.google.com/p/farmhash
• xxHash afirma ser 5 veces más rápido que CityHash.
• plain C port enlace roto

He trazado una comparación de velocidad corta de diferentes algoritmos de hash al hacer hash de archivos.

Los gráficos individuales solo difieren ligeramente en el método de lectura y se pueden ignorar aquí, ya que todos los archivos se almacenaron en un tmpfs. Por lo tanto, el punto de referencia no estaba limitado por IO si se lo estaba preguntando.

• Escala lineal
• Escala logarítmica

Los algoritmos incluyen: SpookyHash, CityHash, Murmur3, MD5, SHA{1,256,512}.

Conclusiones:

• Las funciones hash no criptográficas como Murmur3, Cityhash y Spooky están bastante próximas. Se debe tener en cuenta que Cityhash puede ser más rápido en CPU con instrucción SSE 4.2s CRC, que mi CPU no tiene. SpookyHash fue en mi caso siempre un poquito antes que CityHash.
• MD5 parece ser una buena compensación cuando se usan funciones de hash criptográficas, aunque SHA256 puede ser más seguro para vulnerabilidades de colisión de MD5 y SHA1.
• La complejidad de todos los algoritmos es lineal, lo que realmente no es sorprendente, ya que funcionan en bloques. (Quería ver si el método de lectura hace una diferencia, para que pueda comparar los valores más a la derecha).
• SHA256 era más lento que SHA512.
• No investigué la aleatoriedad de las funciones hash. Pero aquí es una buena comparación de las funciones hash que faltan en la respuesta de Ian Boyds . Esto señala que CityHash tiene algunos problemas en casos de esquina.

La fuente utilizada para los gráficos:

• https://github.com/sahib/rmlint/tree/gh-pages/plots (perdón por el código feo)

Comentarios

• El gráfico de escala lineal corta la etiqueta del eje y que dice qué cantidad está trazando. Supongo que probablemente sería » tiempo en segundos «, igual que la escala logarítmica. Vale la pena arreglarlo ‘.

Sé que hay cosas como SHA-256 y cosas así, pero estos algoritmos están diseñados para ser seguros , lo que normalmente significa que son más lentos que los algoritmos que son menos únicos .

La suposición de que las funciones de hash criptográficas son más únicas es incorrecta y, de hecho, se puede demostrar que a menudo es al revés en la práctica. En realidad:

1. Las funciones de hash criptográficas idealmente deberían ser indistinguibles de ;
2. Pero con funciones hash no criptográficas, es deseable que interactúen favorablemente con las posibles entradas .

Lo que significa que una función hash no criptográfica puede tener menos colisiones que una criptográfico para un conjunto de datos «bueno»: conjuntos de datos para los que fue diseñado.

De hecho, podemos demostrar esto con los datos de la respuesta de Ian Boyd y un poco de matemáticas: el Problema de cumpleaños . La fórmula para el número esperado de pares en colisión si eliges n enteros al azar del conjunto [1, d] es la siguiente (tomada de Wikipedia):

n - d + d * ((d - 1) / d)^n 

Conectando n = 216,553 y d = 2 ^ 32 obtenemos aproximadamente 5.5 colisiones esperadas . Las pruebas de Ian muestran principalmente resultados en ese vecindario, pero con una excepción dramática: la mayoría de las funciones obtuvieron cero colisiones en el pruebas de números consecutivos. La probabilidad de elegir 216,553 números de 32 bits al azar y obtener cero colisiones es de aproximadamente 0,43%. Y eso es solo para una función: aquí tenemos cinco familias distintas de funciones hash con cero ¡colisiones!

Entonces, lo que estamos viendo aquí es que los hash que Ian probó están interactuando favorablemente con el conjunto de datos de números consecutivos, es decir, «se están dispersando mínimamente diferentes entradas más ampliamente de lo que lo haría una función hash criptográfica ideal. (Nota al margen: esto significa que la evaluación gráfica de Ian de que FNV-1a y MurmurHash2 «parecen aleatorios» para él en el conjunto de datos numéricos puede refutarse a partir de sus propios datos. Cero colisiones en un conjunto de datos de ese tamaño, por ambas funciones hash, ¡es sorprendentemente no aleatorio!)

Esto no es una sorpresa porque es un comportamiento deseable para muchos usos de las funciones hash. Por ejemplo, las teclas de la tabla hash son a menudo muy similares; La respuesta de Ian menciona un problema que MSN tuvo una vez con las tablas hash de código postal . Este es un uso en el que la prevención de colisiones en entradas probables gana sobre el comportamiento similar al azar.

Otra comparación instructiva aquí es el contraste en los objetivos de diseño entre CRC y funciones hash criptográficas:

• CRC está diseñado para detectar errores resultantes de canales de comunicación ruidosos , que probablemente una pequeña cantidad de cambios de bits;
• Los hash de cifrado están diseñados para detectar modificaciones realizadas por atacantes maliciosos , a quienes se les asignan recursos computacionales limitados pero arbitrariamente mucha inteligencia.

Entonces, para CRC nuevamente es bueno tener menos colisiones que aleatorias en entradas mínimamente diferentes. Con cripto hashes, ¡esto es un no-no!

Los algoritmos SHA (incluido SHA-256) son diseñado para ser rápido .

De hecho, su velocidad a veces puede ser un problema. En particular, una técnica común para almacenar un token derivado de una contraseña es ejecutar un algoritmo hash rápido estándar 10,000 veces (almacenando el hash del hash del hash del hash de la … contraseña).

#!/usr/bin/env ruby require "securerandom" require "digest" require "benchmark" def run_random_digest(digest, count) v = SecureRandom.random_bytes(digest.block_length) count.times { v = digest.digest(v) } v end Benchmark.bmbm do |x| x.report { run_random_digest(Digest::SHA256.new, 1_000_000) } end 

Resultado:

Rehearsal ------------------------------------ 1.480000 0.000000 1.480000 ( 1.391229) --------------------------- total: 1.480000sec user system total real 1.400000 0.000000 1.400000 ( 1.382016) 

Comentarios

• Es ‘ relativamente rápido, seguro, para un algoritmo hash criptográfico . Pero el OP solo quiere almacenar valores en una tabla hash, y yo ‘ no creo que una función hash criptográfica sea realmente apropiada para eso.
• La pregunta que surgió (tangencialmente, ahora aparece) el tema de las funciones hash criptográficas. Esa ‘ es la parte a la que estoy respondiendo.
• Solo para disuadir a la gente de la idea de » En particular , una técnica común para almacenar un token derivado de una contraseña es ejecutar un algoritmo hash rápido estándar 10,000 veces » – aunque es común, que ‘ s simplemente estúpido. Hay algoritmos diseñados para estos escenarios, p. Ej., bcrypt. Use las herramientas adecuadas.
• Los hash criptográficos están diseñados para tener un alto rendimiento, pero eso a menudo significa que tienen altos costos de configuración, desmontaje, .rodata y / o estatales .Cuando desea un algoritmo para una tabla hash, generalmente tiene claves muy cortas y muchas de ellas, pero no necesita las garantías adicionales de un criptográfico. Yo mismo utilizo un Jenkins modificado de uno en uno.
• @ChrisMorgan: en lugar de usar un hash criptográficamente seguro, HashTable DoS se puede resolver de manera mucho más eficiente usando la aleatorización de hash, de modo que cada ejecución de los programas o incluso en cada tabla hash, por lo que los datos no ‘ no se agrupan en el mismo grupo cada vez.

Utilice SipHash . Tiene muchas propiedades deseables:

• Rápido. Una implementación optimizada toma alrededor de 1 ciclo por byte.

• Seguro. SipHash es un PRF fuerte (función pseudoaleatoria). Esto significa que es indistinguible de una función aleatoria (a menos que conozca la clave secreta de 128 bits). Por lo tanto:

  • No hay necesidad de preocuparse de que las sondas de su tabla hash se conviertan en tiempo lineal debido a las colisiones. Con SipHash, sabe que obtendrá un rendimiento promedio de casos en promedio, independientemente de las entradas.

  • Inmunidad a ataques de denegación de servicio basados en hash.

  • Puede usar SipHash (especialmente la versión con una salida de 128 bits) como MAC (Código de autenticación de mensajes). Si recibe un mensaje y una etiqueta SipHash, y la etiqueta es la misma que la de ejecutar SipHash con su clave secreta, entonces sabe que quien creó el hash también estaba en posesión de su clave secreta, y que ni el mensaje ni el hash se han modificado desde entonces.

Comentarios

• Isn ‘ t ¿Exceso de SipHash a menos que necesite seguridad? Requiere una clave de 128 bits que es solo una semilla hash glorificada. Sin mencionar que MurmurHash3 tiene una salida de 128 bits y SipHash solo tiene una salida de 64 bits. Obviamente, el resumen más grande tiene una menor probabilidad de colisión.
• @bryc La diferencia es que SipHash seguirá comportándose bien, incluso con entradas maliciosas. Una tabla hash basada en SipHash se puede usar para datos de fuentes potencialmente hostiles y puede usar un algoritmo como el sondeo lineal que es muy sensible a los detalles de la función hash.
• Siphash (y prng más reciente relacionado funciones de estilo) es mi opción predeterminada para la seguridad. En rendimiento, xxhash es difícil de superar. Hay toneladas de malos consejos sobre hash en Internet, incluso en los debates aquí. Un buen rendimiento en entradas aleatorias o semi aleatorias no tiene sentido. ¿Cuál es el peor rendimiento de caso, con entradas del mundo real? ¿Cuál es el resultado con entradas maliciosas? Su tabla hash eventualmente se convertirá en un vector de ataque.

Depende de los datos que esté hash. Algunos hash funcionan mejor con datos específicos como texto. Algunos algoritmos de hash fueron diseñados específicamente para ser buenos para datos específicos.

Paul Hsieh una vez hizo hash rápido . Enumera el código fuente y las explicaciones. Pero ya estaba vencido. 🙂

Java usa este simple multiplicar -y-agregar algoritmo:

El código hash para un objeto String se calcula como

 s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1] 

usando aritmética int, donde s[i] es el i ​ -ésimo carácter de la cadena, n es la longitud de la cadena y ^ indica exponenciación. (El valor hash de la cadena vacía es cero.)

Probablemente haya otros mucho mejores, pero esto está bastante extendido y parece ser un buen equilibrio entre velocidad y singularidad.

Comentarios

• Yo no ‘ t usaría exactamente el mismo uno usado aquí, ya que ‘ sigue siendo relativamente fácil producir colisiones con esto. ‘ s definitivamente no es terrible, pero hay mucho mejores por ahí. Y si ‘ no hay una razón importante para ser compatible con Java, no debe elegirse.
• Si aún elige esta forma de hash por alguna razón, al menos podría usar un número primo mejor como 92821 como multiplicador. Eso reduce mucho las colisiones. stackoverflow.com/a/2816747/21499
• También puede usar FNV1a en su lugar. También ‘ es un hash simple basado en la multiplicación, pero utiliza un multiplicador más grande, que dispersa mejor el hash.
• No ‘ no quiero hacer s[0]*31^3 + s[1]*31^2 + s[2]*31 + s[3]. Evite el operador de energía (^) y hágalo de esta manera: ((s[0]*31 + s[1])*31 + s[2])*31 + s[3].
• @LeopoldoSanczyk Sí, en el código se hace (y debería) hacerse iterativamente, era más fácil de entender en una fórmula cerrada.

En primer lugar, ¿por qué necesita implementar su propio hash? Para la mayoría de las tareas, debería obtener buenos resultados con estructuras de datos de una biblioteca estándar, asumiendo que hay una implementación disponible (a menos que solo esté haciendo esto para su propia educación).

En lo que respecta a los algoritmos hash reales, mi favorito personal es FNV. 1

A continuación, se muestra un ejemplo de implementación de la versión de 32 bits en C:

unsigned long int FNV_hash(void* dataToHash, unsigned long int length) { unsigned char* p = (unsigned char *) dataToHash; unsigned long int h = 2166136261UL; unsigned long int i; for(i = 0; i < length; i++) h = (h * 16777619) ^ p[i] ; return h; } 

Comentarios

• La variante FNV-1a es ligeramente mejor con aleatoriedad. Cambia el orden de * y ^: h = (h * 16777619) ^ p[i] == > h = (h ^ p[i]) * 16777619