c++ - tipo - Algoritmo hashing de cadena rápida con bajas tasas de colisión con entero de 32 bits
tipos de datos enteros (14)
Tengo muchas cosas con nombres no relacionados que me gustaría hacer búsquedas rápidas en contra. Un "oso hormiguero" es siempre un "oso hormiguero" en todas partes, por lo que mezclar el hilo y reutilizar el entero funcionaría bien para acelerar las comparaciones. El conjunto completo de nombres es desconocido (y cambia con el tiempo). ¿Qué es un algoritmo rápido de hash de cadenas que generará valores de bits pequeños (32 o 16) y tendrá una baja tasa de colisión?
Me gustaría ver una implementación optimizada específica para C / C ++.
¿Por qué no solo usas las bibliotecas de Boost? Su función de hashing es simple de usar y la mayoría de las cosas en Boost pronto formarán parte del estándar de C ++. Algo de eso ya es.
Boost hash es tan fácil como
#include <boost/functional/hash.hpp>
int main()
{
boost::hash<std::string> string_hash;
std::size_t h = string_hash("Hash me");
}
Puedes encontrar boost en boost.org
Aquí se describe una forma sencilla de implementarlo usted mismo: http://www.devcodenote.com/2015/04/collision-free-string-hashing.html
Un fragmento de la publicación:
si digamos que tenemos un conjunto de caracteres de letras inglesas capitales, entonces la longitud del juego de caracteres es 26, donde A podría representarse por el número 0, B por el número 1, C por el número 2 y así sucesivamente hasta Z por el número 25. Ahora, cada vez que queremos asignar una cadena de este conjunto de caracteres a un número único, llevamos a cabo la misma conversión que hicimos en el caso del formato binario
Eche un vistazo a GNU gperf .
Hay una buena discusión en esta pregunta anterior
Y una buena descripción general de cómo elegir funciones hash, así como estadísticas sobre la distribución de varias comunes here
Nunca es tarde para un buen tema y estoy seguro de que la gente estaría interesada en mis hallazgos.
Necesitaba una función hash y, después de leer esta publicación y hacer un poco de investigación sobre los enlaces que se dan aquí, se me ocurrió esta variación del algoritmo de Daniel J Bernstein, que solía hacer una prueba interesante:
unsigned long djb_hashl(const char *clave)
{
unsigned long c,i,h;
for(i=h=0;clave[i];i++)
{
c = toupper(clave[i]);
h = ((h << 5) + h) ^ c;
}
return h;
}
Esta cadena de hashes de variación ignora la carcasa, lo que se adapta a mi necesidad de hash de credenciales de inicio de sesión de los usuarios. ''clave'' es ''clave'' en español. Lo siento por el español, pero es mi lengua materna y el programa está escrito en él.
Bueno, escribí un programa que generará nombres de usuario de ''test_aaaa'' a ''test_zzzz'', y -para hacer las cadenas más largas- les agregué un dominio aleatorio en esta lista: ''cloud-nueve.com'', ''yahoo.com '','' gmail.com ''y'' hotmail.com ''. Por lo tanto, cada uno de ellos se vería así:
[email protected], [email protected], [email protected], [email protected] and so on.
Aquí está el resultado de la prueba -''Colision entre XXX y XXX ''significa'' Colisión de XXX y XXX ''. ''palabras'' significa ''palabras'' y ''Total'' es el mismo en ambos idiomas-.
Buscando Colisiones... Colision entre ''[email protected]'' y ''[email protected]'' (1DB903B7) Colision entre ''[email protected]'' y ''[email protected]'' (2F5BC088) Colision entre ''[email protected]'' y ''[email protected]'' (51FD09CC) Colision entre ''[email protected]'' y ''[email protected]'' (52F5480E) Colision entre ''[email protected]'' y ''[email protected]'' (74FF72E2) Colision entre ''[email protected]'' y ''[email protected]'' (7FD70008) Colision entre ''[email protected]'' y ''[email protected]'' (9BD351C4) Colision entre ''[email protected]'' y ''[email protected]'' (A86953E1) Colision entre ''[email protected]'' y ''[email protected]'' (BA6B0718) Colision entre ''[email protected]'' y ''[email protected]'' (D0523F88) Colision entre ''[email protected]'' y ''[email protected]'' (DEE08108) Total de Colisiones: 11 Total de Palabras : 456976
Eso no está mal, 11 colisiones de 456,976 (por supuesto, utilizando los 32 bits completos como longitud de la mesa).
Ejecutar el programa con 5 caracteres, es decir, de ''test_aaaaa'' a ''test_zzzzz'', se queda sin memoria creando la tabla. Debajo está la salida. ''No hay memoria para insertar XXXX (insertadas XXX)'' significa ''No queda memoria para insertar XXX (XXX insertado)''. Básicamente malloc () falló en ese punto.
No hay memoria para insertar ''test_epjcv'' (insertadas 2097701). Buscando Colisiones... ...451 ''colision'' strings... Total de Colisiones: 451 Total de Palabras : 2097701
Lo que significa solo 451 colisiones en 2.097.701 cuerdas. Tenga en cuenta que en ninguna de las ocasiones, hubo más de 2 colisiones por código. Lo cual confirmo que es un gran hash para mí, ya que lo que necesito es convertir el ID de inicio de sesión en una identificación única de 40 bits para indexar. Así que utilizo esto para convertir las credenciales de inicio de sesión a un hash de 32 bits y uso los 8 bits adicionales para manejar hasta 255 colisiones por código, lo que indica que los resultados de la prueba serían casi imposibles de generar.
Espero que sea útil para alguien.
EDITAR:
Al igual que el cuadro de prueba es AIX, lo ejecuto usando LDR_CNTRL = MAXDATA = 0x20000000 para darle más memoria y se ejecuta más tiempo, los resultados están aquí:
Buscando Colisiones ... Total de Colisiones: 2908 Total de Palabras: 5366384
¡Eso es 2908 después de 5,366,384 intentos!
MUY IMPORTANTE : compilar el programa con -maix64 (por lo que unsigned long es de 64 bits), ¡el número de colisiones es 0 para todos los casos!
Otra solución que podría ser incluso mejor dependiendo de su caso de uso es cadenas internas . Así es como funcionan los símbolos, por ejemplo, en Lisp.
Una cadena interna es un objeto de cadena cuyo valor es la dirección de los bytes de cadena reales. Entonces usted crea un objeto de cadena interna ingresando en una tabla global: si la cadena está ahí, inicializa la cadena interna a la dirección de esa cadena. Si no, lo inserta, y luego inicializa su cadena interna.
Esto significa que dos cadenas internas construidas a partir de la misma cadena tendrán el mismo valor, que es una dirección. Entonces, si N es el número de cadenas internas en su sistema, las características son:
- Construcción lenta (búsqueda de necesidades y posiblemente asignación de memoria)
- Requiere datos globales y sincronización en el caso de hilos concurrentes
- Compare es O (1), porque está comparando direcciones, no bytes de cadenas reales (esto significa que la ordenación funciona bien, pero no será alfabética).
Aclamaciones,
Carl
Para un conjunto de cadenas fijo usa gperf.
Si su conjunto de cadenas cambia, tiene que elegir una función de hash. Ese tema ha sido discutido antes:
¿Cuál es el mejor algoritmo hash para usar en una cadena stl cuando se usa hash_map?
Puede ver lo que .NET usa en el método String.GetHashCode () usando Reflector.
Me atrevería a suponer que Microsoft pasó un tiempo considerable optimizando esto. También han impreso en toda la documentación de MSDN que está sujeta a cambios todo el tiempo. Claramente está en su "radar de ajuste de rendimiento" ;-)
Sería bastante trivial para portar a C ++ también, lo habría pensado.
También hay un buen artículo en eternallyconfuzzled.com .
El hash One-to-A-Time de Jenkins para cadenas debería verse más o menos así:
#include <stdint.h>
uint32_t hash_string(const char * s)
{
uint32_t hash = 0;
for(; *s; ++s)
{
hash += *s;
hash += (hash << 10);
hash ^= (hash >> 6);
}
hash += (hash << 3);
hash ^= (hash >> 11);
hash += (hash << 15);
return hash;
}
Una de las variantes de FNV debe cumplir con sus requisitos. Son rápidos y producen salidas bastante uniformemente distribuidas.
Bob Jenkins tiene muchas funciones de hash disponibles , todas las cuales son rápidas y tienen bajas tasas de colisión.
CRC-32 . Hay alrededor de un billón de enlaces en google para ello.
murmurhash.googlepages.com es bastante agradable.