algorithm - porque - ¿Cuál es la mejor función de hash de 32 bits para cadenas cortas(nombres de etiqueta)?
porque los tipos de hash crean un hash de longitud diferente (8)
¿Cuál es la mejor función hash de 32 bits para cadenas relativamente cortas?
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 ''lo mejor'' como en ''colisiones mínimas'', el rendimiento no es importante para mis objetivos.
Eso depende de tu hardware. En hardware moderno, es decir, Intel / AMD con SSE4.2 o arm7, debe usar los intrínsecos internos _mm_crc32_uxx , ya que son óptimos para cadenas cortas. (Para claves largas también, pero mejor use la versión enhebrada de Adler, como en zlib)
En hardware antiguo o desconocido, ya sea sonda en tiempo de ejecución para la característica SSE4.2 o CRC32 o simplemente use una si las funciones de hash simples son buenas. Ej. Murmur2 o Ciudad
Una visión general de la calidad y el rendimiento está 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 teclas por adelantado, use un hash perfecto , no una función hash. Por ejemplo, gperf o mi phash : https://github.com/rurban/Perfect-Hash#name
Hoy en día la generación de hash perfecta a través del compilador de ca es tan rápida que incluso puedes crearlos sobre la marcha y dinamizarlos.
No estoy seguro de si es la mejor opción, pero aquí hay una función hash para cadenas:
La práctica de la programación (HASH TABLES, página 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 han demostrado ser buenas elecciones para el
multiplicador en una función hash para cadenas ASCII.
Perdón por la respuesta tardía sobre esto. 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 se doblaba a 32 bits.
Puede consultar 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 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.
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.
Si su programa necesita comunicarse con otro sistema, es mejor usar un algoritmo que es bien conocido. La manera rápida y sucia es usar 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.
Utilice la función hash MaPrime2c:
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 mira www.amsoftware.narod.ru/algo2.html para las pruebas MaFastPrime, MaRushPrime, etc.