Algoritmo hashing de cadenas rápidas con bajas tasas de colisión con entero de 32 bits

Question

Tengo muchas cosas con nombres no relacionados que me gustaría hacer búsquedas rápidas. 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++.

Answer 1

Uno de los FNV variants debe cumplir con sus requisitos. Son rápidos y producen salidas bastante uniformemente distribuidas.

Answer 2

Eche un vistazo a GNU gperf.

Answer 3

CRC-32. Hay alrededor de un billón de enlaces en google para ello.

Answer 4

Para un conjunto de cuerdas fijo use gperf.

Si sus conjuntos de cadenas cambian, tiene que elegir una función de hash. Ese tema se ha discutido antes:

What's the best hashing algorithm to use on a stl string when using hash_map?

Answer 5

Murmur Hash es bastante agradable.

Answer 6

Otra solución que podría ser aún mejor dependiendo de su caso de uso es interned strings. Así es como funcionan los símbolos, p. en Lisp.

Una cadena interna es un objeto de cadena cuyo valor es la dirección de los bytes de serie 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. Así que si N es el número de cadenas internadas en su sistema, las características son:

• construcción lenta (necesita operaciones de búsqueda y posiblemente la asignación de memoria)
• requiere datos globales y de 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).

Cheers,

Carl

Answer 7

La función hash Hsieh es bastante bueno, y tiene algunos puntos de referencia/comparaciones, como una función hash en general en C. En función de lo que quiere (no es completamente obvio) es posible que desee considerar algo como cdb en su lugar.

Answer 8

Hay algunas buenas discusión en este previous question

Y una buena visión general de cómo elegir las funciones de hash, así como estadísticas sobre la distribución de varias de las más comunes here

Answer 9

¿Por qué no sólo tiene que utilizar Boost libraries? 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"); 
} 

puede encontrar impulso en boost.org

Answer 10

Bob Jenkins has many hash functions available, todos los cuales son rápidos y tienen tasas bajas de colisión.

Answer 11

Puede ver lo que .NET usa en el método String.GetHashCode() usando Reflector.

Supongo 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. Así que claramente está en su "radar de ajuste de rendimiento" ;-)

Sería bastante trivial para portar a C++ también, lo hubiera pensado.

Answer 12

También hay un nice article en eternallyconfuzzled.com.

Jenkins' hash de una en-un-tiempo para las cadenas debería ser algo como esto:

#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; 
} 

Answer 13

Nunca es tarde para un buen tema y estoy seguro que la gente estaría interesada en mis conclusiones.

que necesitaba una función hash y después de leer este post y hacer un poco de investigación sobre los vínculos que se dan aquí, me ocurrió con esta variación del algoritmo de Daniel J. Bernstein, que yo 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 variante hashes de cadenas ignorando el caso, que se adapta a mi necesidad de hashing 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 alargar las cadenas- 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 sería el resultado:

 

test_aaaa@cloud-nueve.com, test_aaab@yahoo.com, 
test_aaac@gmail.com, test_aaad@hotmail.com and so on. 

Aquí está la salida 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 'test_phiz@hotmail.com' y 'test_juxg@cloud-nueve.com' (1DB903B7) 
    Colision entre 'test_rfhh@hotmail.com' y 'test_fpgo@yahoo.com' (2F5BC088) 
    Colision entre 'test_wxuj@hotmail.com' y 'test_pugy@cloud-nueve.com' (51FD09CC) 
    Colision entre 'test_sctb@gmail.com' y 'test_iohw@cloud-nueve.com' (52F5480E) 
    Colision entre 'test_wpgu@cloud-nueve.com' y 'test_seik@yahoo.com' (74FF72E2) 
    Colision entre 'test_rfll@hotmail.com' y 'test_btgo@yahoo.com' (7FD70008) 
    Colision entre 'test_wcho@cloud-nueve.com' y 'test_scfz@gmail.com' (9BD351C4) 
    Colision entre 'test_swky@cloud-nueve.com' y 'test_fqpn@gmail.com' (A86953E1) 
    Colision entre 'test_rftd@hotmail.com' y 'test_jlgo@yahoo.com' (BA6B0718) 
    Colision entre 'test_rfpp@hotmail.com' y 'test_nxgo@yahoo.com' (D0523F88) 
    Colision entre 'test_zlgo@yahoo.com' y 'test_rfdd@hotmail.com' (DEE08108) 
    Total de Colisiones: 11 
    Total de Palabras : 456976 

Eso no es malo, 11 colisiones de cada 456.976 (por supuesto usando el pleno de 32 bits como longitud de la tabla).

Ejecutando el programa usando 5 caracteres, que es de 'test_aaaaa' a 'test_zzzzz', se está quedando 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 cadenas. 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 esto sea útil para alguien.

EDIT:

Al igual que la caja de prueba es AIX, lo corro usando LDR_CNTRL = MAXDATA = 0x20000000 para darle más memoria y más largo plazo, 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: La compilación del programa con -maix64 (por lo que unsigned long es de 64 bits), el número de colisiones es 0 para todos los casos !!!

Answer 14

descrito aquí es una forma sencilla de implementar por sí mismo: http://www.devcodenote.com/2015/04/collision-free-string-hashing.html

Un fragmento del mensaje:

si decir que tenemos un conjunto de caracteres de las letras inglesas de capital, entonces la longitud del conjunto 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, siempre que queramos asignar una cadena de este juego de caracteres a un número único, realizamos la misma conversión que en el caso del formato binario