¿Qué algoritmo de hash es mejor para la unicidad y la velocidad?

1388

¿Qué algoritmo de hash es mejor para la unicidad y la velocidad? Los ejemplos (buenos) usos incluyen diccionarios hash.

Sé que hay cosas como SHA-256 y similares, pero estos algoritmos están diseñados para ser seguros , lo que generalmente significa que son más lentos que los algoritmos que son menos únicos . Quiero un algoritmo hash diseñado para ser rápido, pero que siga siendo bastante único para evitar colisiones.

Earlz
fuente
99
¿Con qué propósito, seguridad u otro?
Orbling
19
@Orbling, para la implementación de un diccionario hash. Por lo tanto, las colisiones deben mantenerse al mínimo, pero no tiene ningún propósito de seguridad.
Earlz
44
Tenga en cuenta que tendrá que esperar al menos algunas colisiones en su tabla hash, de lo contrario, la tabla tendrá que ser enorme para poder manejar incluso un número relativamente pequeño de claves ...
Dean Harding
19
¡Buena publicación! ¿Podrías comprobar también xxHash de Yann Collet (creador o LZ4), que es el doble de rápido que Murmur? Página de inicio: code.google.com/p/xxhash Más información: fastcompression.blogspot.fr/2012/04/…
24
@zvrba Depende del algoritmo. bcrypt está diseñado para ser lento.
Izkata

Respuestas:

2461

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

Usé tres conjuntos de teclas diferentes:

Para cada corpus, se registró el número de colisiones y el tiempo promedio empleado en el hashing.

Probé:

Resultados

Cada resultado contiene el tiempo promedio de hash 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 :

¿Las colisiones suceden realmente?

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

Colisiones FNV-1

  • creamwove choca con quists

Colisiones FNV-1a

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

Murmurio2 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 colisiones

  • haggadot choca con loathsomenesses
  • adorablenesses choca con rentability
  • playwright choca 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
  • ... corta 79 colisiones ...
  • night choca con vigil
  • nights choca con vigils
  • finks choca con vinic

Aleatorización

La otra medida subjetiva es la distribución aleatoria de los hashes. La asignación 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:

Ingrese la descripción de la imagen aquí

O como un mapa de Hilbert ( XKCD siempre es relevante ):

Ingrese la descripción de la imagen aquí

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

SDBM :

Ingrese la descripción de la imagen aquí

DJB2a :

Ingrese la descripción de la imagen aquí

FNV-1 :

Ingrese la descripción de la imagen aquí

Todos excepto FNV-1a , que todavía me parecen bastante aleatorios:

Ingrese la descripción de la imagen aquí

De hecho, Murmur2 parece tener una aleatoriedad aún mejor con Numbersque FNV-1a:

Ingrese la descripción de la imagen aquí

Cuando miro el FNV-1amapa de "números", creo que veo sutiles patrones verticales. Con Murmur no veo ningún patrón en absoluto. ¿Qué piensas?


El extra *en la tabla denota cuán mala es la aleatoriedad. Con FNV-1aser el mejor y DJB2xser el peor:

      Murmur2: .
       FNV-1a: .
        FNV-1: ▪
         DJB2: ▪▪
        DJB2a: ▪▪
         SDBM: ▪▪▪
SuperFastHash: .
          CRC: ▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪
     Loselose: ▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪
                                        ▪
                                 ▪▪▪▪▪▪▪▪▪▪▪▪▪
                        ▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪
          ▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪

Originalmente escribí este programa para decidir si incluso tenía que preocuparme por colisiones: lo hago.

Y luego se convirtió en asegurarse de que las funciones hash fueran lo suficientemente aleatorias.

Algoritmo FNV-1a

El hash FNV1 viene en variantes que devuelven hashes de 32, 64, 128, 256, 512 y 1024 bits.

El algoritmo FNV-1a es:

hash = FNV_offset_basis
for each octetOfData to be hashed
    hash = hash xor octetOfData
    hash = hash * FNV_prime
return hash

Donde las constantes FNV_offset_basisy FNV_primedependen del tamaño de hash de retorno que desee:

Hash Size  
===========
32-bit
    prime: 2^24 + 2^8 + 0x93 = 16777619
    offset: 2166136261
64-bit
    prime: 2^40 + 2^8 + 0xb3 = 1099511628211
    offset: 14695981039346656037
128-bit
    prime: 2^88 + 2^8 + 0x3b = 309485009821345068724781371
    offset: 144066263297769815596495629667062367629
256-bit
    prime: 2^168 + 2^8 + 0x63 = 374144419156711147060143317175368453031918731002211
    offset: 100029257958052580907070968620625704837092796014241193945225284501741471925557
512-bit
    prime: 2^344 + 2^8 + 0x57 = 35835915874844867368919076489095108449946327955754392558399825615420669938882575126094039892345713852759
    offset: 9659303129496669498009435400716310466090418745672637896108374329434462657994582932197716438449813051892206539805784495328239340083876191928701583869517785
1024-bit
    prime: 2^680 + 2^8 + 0x8d = 5016456510113118655434598811035278955030765345404790744303017523831112055108147451509157692220295382716162651878526895249385292291816524375083746691371804094271873160484737966720260389217684476157468082573
    offset: 1419779506494762106872207064140321832088062279544193396087847491461758272325229673230371772250864096521202355549365628174669108571814760471015076148029755969804077320157692458563003215304957150157403644460363550505412711285966361610267868082893823963790439336411086884584107735010676915

Vea la página principal de FNV para más detalles.

Todos mis resultados son con la variante de 32 bits.

FNV-1 mejor que FNV-1a?

No. FNV-1a es mucho mejor. Hubo más colisiones con FNV-1a al usar la palabra inglesa corpus:

Hash    Word Collisions
======  ===============
FNV-1   1
FNV-1a  4

Ahora compare minúsculas y mayúsculas:

Hash    lowercase word Collisions  UPPERCASE word collisions
======  =========================  =========================
FNV-1   1                          9
FNV-1a  4                          11

En este caso, FNV-1a no es "400%" peor que FN-1, solo 20% peor.

Creo que lo más importante es que hay dos clases de algoritmos cuando se trata de colisiones:

  • Colisiones raras : FNV-1, FNV-1a, DJB2, DJB2a, SDBM
  • colisiones comunes : SuperFastHash, Loselose

Y luego está la distribución uniforme de los hashes:

  • distribución sobresaliente: Murmur2, FNV-1a, SuperFastHas
  • Excelente distribución: FNV-1
  • buena distribución: SDBM, DJB2, DJB2a
  • distribución horrible: Loselose

Actualizar

¿Murmullo? Seguro Por qué no


Actualizar

@whatshisname se preguntó cómo funcionaría un CRC32 , agregó números a la tabla.

CRC32 es bastante bueno . Pocas colisiones, pero más lentas, y la sobrecarga de una tabla de búsqueda de 1k.

Recorte todas las cosas erróneas sobre la distribución de CRC - my bad


Hasta hoy iba a usar FNV-1a como mi algoritmo de hash de tabla hash de facto . Pero ahora me estoy cambiando a Murmur2:

  • Más rápido
  • Mejor aleatorización de todas las clases de entrada.

Y realmente, realmente espero que haya algo mal con el SuperFastHashalgoritmo que encontré ; Es una pena ser tan popular como es.

Actualización: desde la página de inicio de MurmurHash3 en Google :

(1) - SuperFastHash tiene propiedades de colisión muy pobres, que se han documentado en otros lugares.

Así que supongo que no soy solo yo.

Actualización: me di cuenta de por qué Murmures más rápido que los demás. MurmurHash2 opera en cuatro bytes a la vez. La mayoría de los algoritmos son byte a byte :

for each octet in Key
   AddTheOctetToTheHash

Esto significa que a medida que las teclas se alargan, Murmur tiene la oportunidad de brillar.


Actualizar

Los GUID están diseñados para ser únicos, no aleatorios

Una publicación oportuna de Raymond Chen reitera el hecho de que los GUID "aleatorios" no deben usarse para su aleatoriedad. Ellos, o un subconjunto de ellos, no son adecuados como una clave hash:

Incluso no se garantiza que el algoritmo GUID de la Versión 4 sea impredecible, porque el algoritmo no especifica la calidad del generador de números aleatorios. El artículo de Wikipedia para GUID contiene investigaciones primarias que sugieren que los GUID futuros y anteriores pueden predecirse basándose en el conocimiento del estado del generador de números aleatorios, ya que el generador no es criptográficamente fuerte.

Aleatoriedad no es lo mismo que evitar colisiones; por eso sería un error intentar inventar su propio algoritmo de "hashing" tomando algún subconjunto de un guid "aleatorio":

int HashKeyFromGuid(Guid type4uuid)
{
   //A "4" is put somewhere in the GUID.
   //I can't remember exactly where, but it doesn't matter for
   //the illustrative purposes of this pseudocode
   int guidVersion = ((type4uuid.D3 & 0x0f00) >> 8);
   Assert(guidVersion == 4);

   return (int)GetFirstFourBytesOfGuid(type4uuid);
}

Nota : Nuevamente, pongo "GUID aleatorio" entre comillas, porque es la variante "aleatoria" de GUID. Una descripción más precisa sería Type 4 UUID. Pero nadie sabe qué son los tipos 4 o 1, 3 y 5. Por lo tanto, es más fácil llamarlos GUID "aleatorios".

Todas las palabras inglesas reflejan

Ian Boyd
fuente
41
Sería realmente interesante ver cómo se compara SHA, no porque sea un buen candidato para un algoritmo de hash aquí, sino que sería realmente interesante ver cómo se compara cualquier hash criptográfico con estos algoritmos de velocidad.
Michael
8
Un nuevo hash con el nombre de 'xxHash', de Yann Collet, estaba haciendo las rondas recientemente. Siempre sospecho de un nuevo hash. Sería interesante ver que en su comparación, (si no está cansado de la gente que sugieren hash aleatorias que han escuchado de que se añade ...)
th_in_gs
77
En efecto. Los números de rendimiento anunciados por la página del proyecto xxHash parecen impresionantes, tal vez demasiado para ser verdad. Bueno, al menos, es un proyecto de código abierto: code.google.com/p/xxhash
ATTracker
99
Hola Ian, mi implementación Delphi de SuperFastHash es correcta. Al implementar, creé un conjunto de pruebas en C y Delphi para comparar los resultados de mi implementación y la implementación de referencia. No hay diferencias Entonces, lo que ves es la maldad real del hash ... (Es por eso que también publiqué una implementación de MurmurHash : landman-code.blogspot.nl/2009/02/… )
Davy Landman
19
¿El cartel es consciente de que esta no es solo una respuesta asombrosa: este es el recurso de referencia de facto del mundo sobre el tema? Cada vez que necesito lidiar con hashes, eso resuelve mi problema tan rápido y con autoridad que nunca necesito nada más.
MaiaVictor
59

Si desea crear un mapa hash a partir de un diccionario que no cambia, puede considerar el hashing 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 dado, que no habrá colisiones.

Damien
fuente
2
Aquí hay más sobre (mínimo) Perfect Hashing burtleburtle.net/bob/hash/perfect.html, incluidos los datos de rendimiento, aunque no utiliza el procesador más reciente, etc.
Ellie Kesselman
44
Es bastante obvio, pero vale la pena señalar que para garantizar que no haya colisiones, las claves deberían tener el mismo tamaño que los valores, a menos que haya restricciones en los valores que el algoritmo puede capitalizar.
devios1
1
@ 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, indexada por el resultado de la función que se ha diseñado para que todos los índices sean únicos.
Jim Balter
1
@MarcusJ El hashing perfecto generalmente se usa con menos de 100 teclas, pero eche un vistazo a cmph.sourceforge.net ... aún muy por debajo de su rango.
Jim Balter
1
@DavidCary Nada en su enlace respalda su reclamo. Posiblemente haya confundido O (1) con "sin colisiones", pero no son lo mismo. Por supuesto, el hashing perfecto no garantiza colisiones, pero requiere que todas las claves se conozcan de antemano y que sean relativamente pocas. (Pero vea el enlace a cmph arriba.)
Jim Balter
34

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

Si solo desea tener una buena función hash, y no puede esperar, djb2es una de las mejores funciones hash de cadenas que conozco. Tiene una excelente distribución y velocidad en muchos juegos diferentes de llaves y tamaños de mesa.

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;
}
Dean Harding
fuente
66
En realidad, djb2 es cero sensible, como la mayoría de las funciones hash simples, por lo que puede romper fácilmente estos 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 no lo usaría con acceso publico.
rurban
2
DJB es bastante malo desde el punto de vista del rendimiento y la distribución. No lo usaría hoy.
Conrad Meyer
@ConradMeyer Apuesto a que DJB puede acelerarse por un factor de tres al igual que en esta pregunta mía y luego probablemente superaría a la mayoría de los algoritmos utilizables. En cuanto a la distribución, estoy de acuerdo. Un hash que produce colisiones incluso para cadenas de dos letras no puede ser realmente bueno.
maaartinus
28

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

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

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

Acerca del soporte de 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 el código de 32 bits.

Vipin Parakkat
fuente
11
¿CityHash se pronuncia similar a "City Sushi"?
Eric
2
Eche un vistazo a SipHash también, está destinado a reemplazar MurmurHash / CityHash / etc. : 131002.net/siphash
Török Edwin
3
También vea FarmHash, un sucesor de CitHash. code.google.com/p/farmhash
stevendaniels
77
xxHash afirma ser 5 veces más rápido que CityHash.
Clay Bridges
plain C portel enlace está roto
makerj
20

He trazado una comparación de velocidad corta de diferentes algoritmos de hash cuando hashing archivos.

Las parcelas individuales solo difieren ligeramente en el método de lectura y pueden ignorarse aquí, ya que todos los archivos se almacenaron en un archivo tmpfs. Por lo tanto, el punto de referencia no estaba sujeto a IO si se está preguntando.

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 juntas. Hay que tener en cuenta que Cityhash puede ser más rápido en las CPU con la CRCinstrucción SSE 4.2 , que mi CPU no tiene. SpookyHash estuvo en mi caso siempre un poquito antes de CityHash.
  • MD5 parece ser una buena compensación cuando se utilizan funciones hash criptográficas, aunque SHA256 puede ser más seguro frente a las 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 bloque. (Quería ver si el método de lectura marca la diferencia, para que pueda comparar los valores más correctos).
  • SHA256 fue más lento que SHA512.
  • No investigué la aleatoriedad de las funciones hash. Pero aquí hay 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 las parcelas:

Sahib
fuente
1
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.
Craig McQueen
18

Los algoritmos SHA (incluido SHA-256) están diseñados para ser rápidos .

De hecho, su velocidad puede ser un problema a veces. En particular, una técnica común para almacenar un token derivado de contraseña es ejecutar un algoritmo de hash rápido estándar 10.000 veces (almacenar 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

Salida:

Rehearsal ------------------------------------
   1.480000   0.000000   1.480000 (  1.391229)
--------------------------- total: 1.480000sec

       user     system      total        real
   1.400000   0.000000   1.400000 (  1.382016)
Yfeldblum
fuente
57
Es relativamente rápido, seguro, para un algoritmo de cifrado criptográfico . Pero el OP solo quiere almacenar valores en una tabla hash, y no creo que una función hash criptográfica sea realmente apropiada para eso.
Dean Harding
66
La pregunta planteada (tangencialmente, ahora parece) es el tema de las funciones hash criptográficas. Eso es lo que estoy respondiendo.
yfeldblum
15
Solo para alejar a la gente de la idea de "En particular, una técnica común para almacenar un token derivado de contraseña es ejecutar un algoritmo de hash rápido estándar 10,000 veces", aunque es común, eso es simplemente estúpido. Hay algoritmos diseñados para estos escenarios, por ejemplo, bcrypt. Usa las herramientas adecuadas.
TC1
3
Los hash criptográficos están diseñados para tener un alto rendimiento, pero eso a menudo significa que tienen altos .rodatacostos de instalación, desmontaje y / o estado. 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 una cuenta criptográfica. Yo uso un Jenkins modificado uno por uno.
mirabilos
1
@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, para que los datos no se agrupen en el mismo cubo cada vez .
Mentira Ryan
14

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

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

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

Lo que significa que una función hash no criptográfica puede tener menos colisiones que una criptográfica para un "buen" conjunto de datos: conjuntos de datos para los que fue diseñada.

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

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

Plugging 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 las pruebas de números consecutivos. La probabilidad de elegir al azar 216,553 números de 32 bits y obtener colisiones cero 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, están dispersando entradas mínimamente diferentes 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 "le parecen aleatorios" en el conjunto de datos de números se puede refutar a partir de sus propios datos. Cero colisiones en un conjunto de datos de ese tamaño, para 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 claves de 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 donde la prevención de colisiones en entradas probables gana sobre el comportamiento aleatorio.

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

  • CRC está diseñado para detectar errores resultantes de canales de comunicación ruidosos , que probablemente sean un pequeño número de cambios de bits;
  • Los cifrados hash están diseñados para detectar modificaciones realizadas por atacantes maliciosos , a los que 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, este es un no-no!

sacundim
fuente
10

Usa SipHash . Tiene muchas propiedades deseables:

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

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

    • No es necesario preocuparse de que las sondas de la tabla hash se conviertan en tiempo lineal debido a colisiones. Con SipHash, sabe que obtendrá un rendimiento promedio de caso en promedio, independientemente de las entradas.

    • Inmunidad a los 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 mensaje). 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 ha sido alterado desde entonces.

Demi
fuente
1
¿No es excesivo 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 posibilidad de colisión.
bryc
@bryc La diferencia es que SipHash continuará comportándose bien, incluso con entradas maliciosas. Una tabla hash basada en SipHash puede usarse 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.
Demi
9

Depende de los datos que esté procesando. Algunos hash funcionan mejor con datos específicos como texto. Algunos algoritmos de hash se diseñaron 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. :)

usuario712092
fuente
6

Java utiliza este algoritmo simple de multiplicar y agregar:

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, nes la longitud de la cadena e ^indica exponenciación. (El valor hash de la cadena vacía es cero).

Probablemente hay muchos mejores, pero esto está bastante extendido y parece ser una buena compensación entre velocidad y singularidad.

biziclop
fuente
12
No usaría exactamente el mismo que se usa aquí, ya que todavía es relativamente fácil producir colisiones con esto. Es sin duda no es terrible, pero hay otros mucho mejores por ahí. Y si no hay ninguna razón de peso para que sea compatible con Java, debería no ser elegido.
Joachim Sauer el
44
Si aún elige esta forma de hash por alguna razón, al menos podría usar un cebador mejor como 92821 como multiplicador. Eso reduce mucho las colisiones. stackoverflow.com/a/2816747/21499
Hans-Peter Störr
1
También podría usar FNV1a en su lugar. También es un hash simple basado en multiplicación, pero usa un multiplicador más grande, que dispersa mejor el hash.
bryc
4

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

En cuanto a los algoritmos de hash reales, mi favorito personal es FNV. 1

Aquí hay 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;
}

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