¿Cuál es la mejor de 32 bits, la función de hash para cadenas cortas (los nombres de las etiquetas)?

¿Cuál es la mejor de 32 bits, la función de hash para relativamente corto cuerdas?

Cadenas son los nombres de las etiquetas que consisten en inglés, letras, números, espacios y algunos caracteres adicionales (#, $, ., …). Por ejemplo: Unit testing, C# 2.0.

Estoy buscando ‘mejor’ como en ‘un mínimo de colisiones’, el rendimiento no es importante para mis objetivos.

  • es posible duplicar stackoverflow.com/questions/251346/…
  • No completamente, de manera que, porque mi pregunta es más específica en términos de hash de tamaño y omite el rendimiento. También no solo estoy buscando una función hash, estoy buscando una elección significativa … sé que hay CRC32 y FNV32, pero que es mejor para mi dominio?
  • Es su etiqueta de lista fijada a un conjunto de cadenas o va a crecer de forma dinámica a lo largo del tiempo?
  • Las etiquetas se agregan por las personas, así que no se puede predecir (pero no son la longitud y el límite de caracteres).
  • ¿Cuáles son los límites?
  • Longitud máxima: 20, conjunto de caracteres actual: [A-Za-z\d\.#[email protected]\-\ ] (este puede crecer un poco si veo algo útil de símbolo que me perdí).
  • La siguiente página tiene varias implementaciones de propósito general de las funciones de hash que son eficientes y presentan un mínimo de colisiones: partow.net/programming/hashfunctions/index.html

8 Kommentare

  1. 23

    Si el rendimiento no es importante, simplemente tome un seguro de hash como MD5 o SHA1, y truncar su salida de 32 bits. Esto le dará una distribución de códigos hash que es indistinguible de azar.

    • md5 es perfecto para este escenario
    • MD4 (ver tools.ietf.org/html/rfc1320 ) puede ser incluso mejor, ya que es ligeramente más sencillo de implementar que el MD5. Tenga en cuenta que ni MD4 ni MD5 es indistinguible de azar (ambos fueron «criptográficamente roto»), pero que todavía están lo suficientemente cerca para el propósito en la mano.
    • ¿Crees que habría menos colisiones de Nick D la respuesta? Estoy un poco indeciso sobre qué aprobar/uso.
    • MD5 es rota en el sentido de que se puede crear un hash de la colisión de dos plaintexts que producen el mismo valor hash. Eso no quiere decir que la salida de MD5 es distinguible de azar – no hay preimagen ataque contra MD5. Que es más fácil de implementar es irrelevante, demasiado – él casi seguro que tiene un pre-hechos MD5 o SHA1 la implementación en su idioma de elección.
    • Secure hash como SHA1 y MD5 tener la menor cantidad de colisiones teóricamente posible. Más rápido los hash como el Nick sugiere son excelentes, donde la velocidad es importante, pero hay más colisiones. Su idioma de elección casi seguro que tiene un pre-hechos de la implementación de MD5 o SHA1, demasiado.
    • los ataques en MD5 se basan en un diferencial de ruta. Mediante la aplicación de la entrada de la diferencia en un MD5 de entrada, usted tiene un pequeño pero superiores al azar la probabilidad de encontrar la diferencia esperada en la salida. Esto no conduce a una preimagen de ataque, pero hace MD5 distinguible de un azar de oracle. En el caso de MD4, esto fue demostrado ser (académicamente) explotable cuando se utiliza en HMAC (donde las colisiones son por sí mismos que no hay que preocuparse).
    • Acepto la corrección. Yo no sabía que MD4 estaba roto, incluso para los Hmac – resultado interesante!
    • He probado MD5, Sha1 y nomal CRC32, y tienen casi la misma tasa de colisión, todo acerca de 0.23%. Así MD5 y SHA1 ello nada mejor aquí. Es mejor hash de md5 y sha1?

  2. 25

    No estoy seguro de si es la mejor opción, pero aquí es una función de hash para las cadenas:

    la Práctica de La Programación (TABLAS HASH, pg. 57)

    /* hash: compute hash value of string */
    unsigned int hash(char *str)
    {
       unsigned int h;
       unsigned char *p;
    
       h = 0;
       for (p = (unsigned char*)str; *p != '\0'; p++)
          h = MULTIPLIER * h + *p;
       return h; //or, h % ARRAY_SIZE;
    }

    Empíricamente, los valores de 31 y 37 han demostrado ser buenas opciones para el multiplicador en función hash para cadenas de caracteres ASCII.

    • Sí utilizamos este exacto de la función de hash con el MULTIPLICADOR = 37 para las cadenas y las rutas de acceso. Funciona bien para nosotros, y aún tengo que encontrar una colisión problema incluso después de 2 años ( por supuesto, no hay garantía de que no vamos, sin embargo )
    • Esto sin duda se ve bastante simple. Alguna idea de por qué FNV fue creado si enfoque mucho más simple funciona?
    • Shchekin, yo uso hash FNV, cuando trato con raw bytes (blob). Tal vez, la función anterior, se obtienen mejores resultados específicamente con cadenas. No estoy seguro.
    • Nick D – Principal motivo por el que usamos el algoritmo anterior es para la velocidad. Sé que el rendimiento no era una prioridad para Andrey así que puede no ser relevante. También he utilizado FNV32 pero más hash de datos binarios como Nick D mencionadas. Realmente no puedo comparar igual por igual, a pesar de que podría ser vale la pena probar ambos y ver cuál tiene la menor tasa de colisión
    • Tomo nota de que el Perl del algoritmo de hash que se utiliza el MULTIPLICADOR=33, y hace un paso adicional en la final: h += (h >> 5) mejorar la distribución de los bits de orden inferior.
    • Esto fue muy útil.
    • Este algoritmo es una de las variantes discutido en cse.yorku.ca/~oz/hash.html. Desgraciadamente, es propenso a la básica hash-colisión de ataques (ver [ocert.org/advisories/ocert-2011-003.html]), ya que es trivial para el uso de substring (ver la referencia de papel) colisión de cálculo; pero puede funcionar bien si no se usa nunca con el exterior-siempre teclas.

  3. 16

    Lo siento por la muy tardía respuesta sobre esto. A principios de este año he compuesto una página titulada Hash Cadenas Cortas que podría ser útil en esta discusión. En resumen, me encontré con que el CRC-32 y FNV-1a son superiores para la mezcla cadenas cortas. Son eficientes y producen ampliamente distribuida y sin colisiones de hash en mis pruebas. Me sorprendí al encontrar que MD5, SHA-1 y SHA-3 produce un pequeño número de colisiones cuando la salida era doblado hasta 32 bits.

    • CRC32 es todavía la mejor respuesta aquí
    • Yo también creo que el CRC32 debe ser el mejor clasificado de respuesta
    • En realidad, CRC32 de distribución es bastante terrible en comparación con otras alternativas. Para 32 bits hash, incluso ingenua de un algoritmo como el producto de la rotación podría producir una mejor distribución de <8byte cadenas, y potencialmente mucho más rápido. Hablando de lo cual, xxHash hace exactamente eso, pero con mucho mejor distribución, y específicamente optimizado para los procesadores modernos (muy a diferencia de CRC32). Para la mezcla de un gran número de pequeñas cadenas, con un menor número de colisiones (como cuando gramatical), DJB2 es probablemente la mejor opción.
  4. 1

    Usted puede comprobar fuera de murmurhash2. Es rápido, también para las pequeñas cadenas, y tiene una buena mezcla de último paso por lo que es incluso una buena mezcla para muy pequeñas cadenas.

  5. 1

    Eso depende de tu hardware.
    En hardware moderno, es decir, Intel/AMD con SSE4.2 o arm7 debe utilizar la interna _mm_crc32_uxx de las características intrínsecas, como son óptimas para cadenas cortas. (No por mucho tiempo las teclas también, pero, a continuación, un mejor uso de Adler de la versión de rosca, como en zlib)

    De edad o desconocido de hardware, ya sea en tiempo de ejecución de la sonda para la SSE4.2 o CRC32 característica o simplemente usar uno si el simple buen funciones de hash. E. g. Murmur2 o de la Ciudad

    Una visión general de la calidad y el rendimiento está aquí:
    https://github.com/rurban/smhasher#smhasher

    Hay también todas las implementaciones. Favorecidos son https://github.com/rurban/smhasher/blob/master/crc32_hw.c y https://github.com/rurban/smhasher/blob/master/MurmurHash2.cpp

    Si usted sabe las claves de antemano, el uso de un perfecto hash, no de una función hash. E. g. gperf o mi phash: https://github.com/rurban/Perfect-Hash#name

    Hoy en día perfecto hash través de la generación de un compilador de c es tan rápido, incluso se puede crear sobre la marcha, y dynaload ella.

    • Actualización: Murmur2 y la Ciudad no puede ser llamado simple buen funciones de hash más. Más rápido sería FNV1 o CRC32-C, sería mejor Metro o Farmhash.
    • SpookyHash64 todavía tiene las mejores cayendo en avalanchas/el más bajo de la colisión de las tasas de todas las funciones de hash que he encontrado, que sería altamente consejo de usarlo por robin hood hash mapas, a menos que usted haya encontrado empíricamente que otras funciones de hash mejor/más rápido. Para las pequeñas entradas recomiendo FNV1A o DJB2. SpookyHash tiene un muy alto costo de instalación con ~30 ciclos. Metro/Granja/Soplo/Ciudad/xxHash/muchos otros son grandes para un rápido, de propósito general de hash, con menores tiempos de instalación, pero la subida de las tasas de colisiones. Yo no los uso cuando bajas las tasas de colisión son importantes.
  6. 0

    Si es raro que los usuarios añadir nuevas etiquetas, entonces usted puede utilizar un perfecto hash (http://en.wikipedia.org/wiki/Perfect_hash_function) que se vuelve a calcular cada vez que una nueva etiqueta se agrega. Por supuesto, sin conocer el problema que usted está realmente tratando de resolver, es adivinar para averiguar lo que usted podría hacer.

  7. 0

    Si el programa necesita comunicarse con otro sistema, es mejor utilizar un algoritmo, el cual es bien conocido. El quick & sucio es el uso de Varios de los personajes de hash md5. Usted no necesita pasar horas o días para inventar ruedas en su proyecto.

    La desventaja es conseguir mucho más alta probabilidad de colisiones. Sin embargo, si el hash es para una marca de tiempo de la sesión, o de corta vida circule tarea. No hay ningún problema para usarlo.

  8. 0

    Uso MaPrime2c función hash:

    static const unsigned char sTable[256] =
    {
      0xa3,0xd7,0x09,0x83,0xf8,0x48,0xf6,0xf4,0xb3,0x21,0x15,0x78,0x99,0xb1,0xaf,0xf9,
      0xe7,0x2d,0x4d,0x8a,0xce,0x4c,0xca,0x2e,0x52,0x95,0xd9,0x1e,0x4e,0x38,0x44,0x28,
      0x0a,0xdf,0x02,0xa0,0x17,0xf1,0x60,0x68,0x12,0xb7,0x7a,0xc3,0xe9,0xfa,0x3d,0x53,
      0x96,0x84,0x6b,0xba,0xf2,0x63,0x9a,0x19,0x7c,0xae,0xe5,0xf5,0xf7,0x16,0x6a,0xa2,
      0x39,0xb6,0x7b,0x0f,0xc1,0x93,0x81,0x1b,0xee,0xb4,0x1a,0xea,0xd0,0x91,0x2f,0xb8,
      0x55,0xb9,0xda,0x85,0x3f,0x41,0xbf,0xe0,0x5a,0x58,0x80,0x5f,0x66,0x0b,0xd8,0x90,
      0x35,0xd5,0xc0,0xa7,0x33,0x06,0x65,0x69,0x45,0x00,0x94,0x56,0x6d,0x98,0x9b,0x76,
      0x97,0xfc,0xb2,0xc2,0xb0,0xfe,0xdb,0x20,0xe1,0xeb,0xd6,0xe4,0xdd,0x47,0x4a,0x1d,
      0x42,0xed,0x9e,0x6e,0x49,0x3c,0xcd,0x43,0x27,0xd2,0x07,0xd4,0xde,0xc7,0x67,0x18,
      0x89,0xcb,0x30,0x1f,0x8d,0xc6,0x8f,0xaa,0xc8,0x74,0xdc,0xc9,0x5d,0x5c,0x31,0xa4,
      0x70,0x88,0x61,0x2c,0x9f,0x0d,0x2b,0x87,0x50,0x82,0x54,0x64,0x26,0x7d,0x03,0x40,
      0x34,0x4b,0x1c,0x73,0xd1,0xc4,0xfd,0x3b,0xcc,0xfb,0x7f,0xab,0xe6,0x3e,0x5b,0xa5,
      0xad,0x04,0x23,0x9c,0x14,0x51,0x22,0xf0,0x29,0x79,0x71,0x7e,0xff,0x8c,0x0e,0xe2,
      0x0c,0xef,0xbc,0x72,0x75,0x6f,0x37,0xa1,0xec,0xd3,0x8e,0x62,0x8b,0x86,0x10,0xe8,
      0x08,0x77,0x11,0xbe,0x92,0x4f,0x24,0xc5,0x32,0x36,0x9d,0xcf,0xf3,0xa6,0xbb,0xac,
      0x5e,0x6c,0xa9,0x13,0x57,0x25,0xb5,0xe3,0xbd,0xa8,0x3a,0x01,0x05,0x59,0x2a,0x46
    };
    
    
    #define PRIME_MULT 1717
    
    
    unsigned int
    maPrime2cHash (unsigned char *str, unsigned int len)
    {
      unsigned int hash = len, i;
    
    
      for (i = 0; i != len; i++, str++)
        {
    
          hash ^= sTable[( *str + i) & 255];
          hash = hash * PRIME_MULT;
        }
    
      return hash;
    }

    y mirar http://www.amsoftware.narod.ru/algo2.html para MaFastPrime, MaRushPrime, etc pruebas.

Kommentieren Sie den Artikel

Bitte geben Sie Ihren Kommentar ein!
Bitte geben Sie hier Ihren Namen ein

Pruebas en línea