¿Cuál es la mejor función hash de 32 bits para cadenas relativamente cortas?¿Cuál es la mejor función hash de 32 bits para cadenas cortas (nombres de etiqueta)?
Las cadenas son nombres de etiquetas que consisten en letras inglesas, números, espacios y algunos caracteres adicionales (#, $, ., ...). Por ejemplo: Unit testing, C# 2.0.
Estoy buscando el "mejor" como en "colisiones mínimas", el rendimiento no es importante para mis objetivos.
Si el rendimiento no es importante, simplemente tome un hash seguro como MD5 o SHA1, y trunque su salida a 32 bits. Esto le dará una distribución de códigos hash que es indistinguible de forma aleatoria.
MD5 es perfecto para este escenario –
MD4 (ver http://tools.ietf.org/html/rfc1320) puede ser aún mejor, ya que es un poco más sencillo de implementar que MD5. Tenga en cuenta que ni MD4 ni MD5 son indistinguibles de los aleatorios (ambos estaban "criptográficamente rotos") pero todavía están lo suficientemente cerca para el propósito en cuestión. –
¿Crees que tendría menos colisiones que la respuesta de Nick D?Estoy algo indeciso sobre qué aprobar/usar. –
no estoy seguro de si es la mejor opción, pero aquí es una función hash para cadenas: (. Las 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 31 y 37 tienen probadas como buenas opciones para el multiplicador
en una función hash para cadenas ASCII.
Sí utilizamos esta función hash exacta con el multiplicador = 37 para las cadenas y caminos. Funciona bien para nosotros y todavía no he encontrado un problema de colisión incluso después de 2 años (por supuesto, no hay garantía de que no lo haremos) – zebrabox
Esto definitivamente parece bastante simple. ¿Alguna idea de por qué se creó FNV si funciona un enfoque mucho más simple? –
@Andrey Shchekin, utilizo hash FNV cuando trato con bytes brutos (blobs). Quizás, la función anterior produce mejores resultados específicamente con cadenas. No estoy seguro. –
Puedes echar un vistazo a murmurhash2. Es rápido, también para cuerdas pequeñas, y tiene un buen paso final de mezcla, por lo que incluso se mezcla bien para cuerdas muy pequeñas.
Si es raro que los usuarios agreguen nuevas etiquetas, entonces puede usar un hash perfecto (http://en.wikipedia.org/wiki/Perfect_hash_function) que se vuelve a calcular cada vez que se agrega una nueva etiqueta. Por supuesto, sin saber el problema que realmente está tratando de resolver, es una suposición averiguar qué podría hacer.
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 www.amsoftware.narod.ru/algo2.html para MaFastPrime, MaRushPrime, etc pruebas.
Si su programa necesita comunicarse con otro sistema, es mejor utilizar un algoritmo que es bien conocido. La manera rápida & es usando primero Varios caracteres de md5 hash. No necesita pasar horas o días para inventar ruedas en su proyecto.
La desventaja es obtener muchas más posibilidades de colisiones. Sin embargo, si su hash es para una sesión con sello de tiempo o una tarea de ciclo de vida corta. No hay problema para usar eso.
Eso depende de su hardware. En hardware moderno, es decir, Intel/AMD con SSE4.2 o arm7, debe utilizar los intrínsecos internos _mm_crc32_uxx, ya que son óptimos para cadenas cortas. (Para las claves largas también, pero mejor utilice la versión con hebra de Adler, como en zlib)
En hardware antiguo o desconocido, sonda de tiempo de ejecución para la característica SSE4.2 o CRC32 o simplemente use una si el hash simple bueno funciones. P.ej.Murmur2 o Ciudad
Una visión general de la calidad y el rendimiento es aquí: https://github.com/rurban/smhasher#smhasher
También hay 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 conoce las claves de antelación, utilice un hash perfecta , no una función hash. P.ej. gperf o mi phash: https://github.com/rurban/Perfect-Hash#name
generación de hash perfecta Hoy en día a través de un compilador de C es tan rápido, incluso se puede crear sobre la marcha, y que dynaload.
Actualización: Murmur2 y City ya no se pueden llamar simples funciones de hash buenas. Lo más rápido sería FNV1 o CRC32-C, mejor sería Metro o Farmhash. – rurban
Lo siento por la muy tardía respuesta sobre este. A principios de este año compuse una página titulada Hashing Short Strings que podría ser útil en esta discusión. En resumen, encontré que CRC-32 y FNV-1a son superiores para hash cadenas cortas. Son eficientes y produjeron hashes ampliamente distribuidos y sin colisiones en mis pruebas. Me sorprendió descubrir que MD5, SHA-1 y SHA-3 producían pequeñas cantidades de colisiones cuando la salida era doblada hasta 32 bits.
posible duplicado http://stackoverflow.com/questions/251346/best-hashing-algorithm-in-terms-of-hash-collisions-and-performance –
No completamente así, porque mi pregunta es más específica en términos de tamaño hash e ignora el rendimiento. Además, no estoy buscando solo la función _a_ hash, estoy buscando una opción significativa: sé que hay CRC32 y FNV32, pero ¿cuál es mejor para mi dominio? –
¿Su lista de etiquetas está fijada a un conjunto de cadenas o crecerá dinámicamente con el tiempo? –